Trade-Offs Computing Minimum Hub Cover Toward Optimized Labeled Graph Query Processing
Öz As techniques for graph query processing mature, the need for optimization is increasingly becoming an imperative. Indices are one of the key ingredients toward efficient query processing strategies via cost-based optimization. Due to the apparent absence of a common representation model, it is difficult to make a focused effort toward developing access structures, metrics to evaluate query costs, and choose alternatives. In this context, recent interests in covering-based graph matching appears to be a promising direction of research. In this paper, our goal is to formally introduce a new graph representation model, called Minimum Hub Cover, and demonstrate that this representation offers interesting strategic advantages, facilitates construction of candidate graphs from graph fragments, and helps leverage indices in novel ways for query optimization. However, like other covering problems, minimum hub cover is NP-hard, and thus is a natural candidate for optimization. We claim that computing the minimum hub cover leads to substantial cost reduction for graph query processing. We present a computational characterization of minimum hub cover based on integer programming to substantiate our claim and investigate its computational cost on various graph types.
Trade-Offs Computing Minimum Hub Cover Toward Optimized Labeled Graph Query Processing
___
- S. Abiteboul and J. V. den Bussche. Deep equality revisited. In DOOD, pages 213–228, 1995.
- S. Amin, J. Russell L. Finley, and H. M. Jamil. Top-k similar graph matching
using TraM in biological networks. ACM/IEEE TCBB, 2012.
http://doi.ieeecomputersociety.org/10.1109/TCBB.2012.90.
- Z. N. Azimi, P. Toth, and L. Galli. An electromagnetism metaheuristic for the unicost set covering
problem. European Journal of Operational Research, 205:290–300, 2010.
- S. Balaji, V. Swaminathan, and K. Kannan. Optimization of unweighted minimum vertex cover. World
Academy of Science, Engineering and Technology, 67:508–513, 2010.
- R. Bar-Yehuda and S. Even. A linear-time approximation algorithm for the weighted vertex cover
problem. Journal of Algorithms, 2:198–203, 1981.
- P. Boldi, M. Santini, and S. Vigna. A deeper investigation of page rank as a function of the damping
factor. In Web Information Retrieval and Linear Algebra Algorithms, 2007.
- A. Caprara, P. Toth, and M. Fischetti. Algorithms for the set covering problem. Annals of Operations
Research, 98:353–371, 2000.
- M. Caserta. Metaheuristics: progress in complex systems optimization, chapter 3, pages 43–
- Springer, Berlin, 2007.
- C. Chen, X. Yan, P. S. Yu, J. Han, D.-Q. Zhang, and X. Gu. Towards graph containment search and
indexing. In VLDB, pages 926–937, 2007.
- J. Chen and I. A. Kanj. On approximating minimum vertex cover for graphs with perfect matching.
Theor. Comput. Sci., 337(1-3):305–318, 2005.
- S. M. Chung. Indexed extendible hashing. Inf. Process. Lett., 44(1):1–6, 1992.
- L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. Performance evaluation of the vf graph matching
algorithm. In Image Analysis and Processing, pages 1172–1177, 1999.
- E. Dolan and J. More. Benchmarking optimization software with performance profiles.
Mathematical Programming, 91:201–213,2002.
- I. Evans. Evolutionary algorithms for vertex cover. In 7th Annual Conference Evolutionary
Programming, pages 377–386, New York, 1998.
- T. A. Feo and M. Resende. A probabilistic heuristic for a computationally difficult set covering
problem. Operations Research Letters, 8:67–71, 1989.
- F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens. Random-walk computation of similarities
between nodes of a graph with application to collaborative recommendation. TKDE, 19(3):355–
369, 2007.
- R. Giugno and D. Shasha. GraphGrep: A fast and universal method for querying graphs. In
ICPR, volume 2, pages 112–115, 2002.
- F. Gomes, C. Meneses, P. Pardalos, and G. Viana. Experimental analysis of approximation
algorithms for the veretx cover and set covering problems. Computers and Operations Research,
33:3520–3534, 2006.
- E. Halperin. Improved approximation algorithms for the vertex cover problem in graphs and
hypergraphs. SIAM Journal on Computing, 31:1608–1623, 2001.
- M. Haouari and J. S. Chaouachi. A probabilistic greedy search algorithm for combinatorial
optimization with application to the set covering problem. Journal of the Operational Research
Society, 53:792–799, 2002.
- H. He and A. Singh. Graphs-at-a-time: query language and access methods for graph databases. In
SIGMOD, pages 405–418, 2008.
- T. Imamura, K. Iwama, and T. Tsukiji. Approximated vertex cover for graphs with perfect
matchings. IEICE Transactions, 89-D (8):2405–2410, 2006.
- H. M. Jamil. Computing subgraph isomorphic queries using structural unification and minimum
graph structures. In ACM International Symposium on Applied Computing, pages 1053–1058,
Taichung, Taiwan, March 2011.
- H. M. Jamil. Design of declarative graph query languages: On the choice between value, pattern and
object-based representations for graphs. In ICDE Workshop on Graph Data Management, April
2012.
- H. M. Jamil. Pruning forests to find the trees. In Proceedings of the 28th International Conference on
Scientific and Statistical Database Management, SSDBM 2016, Budapest, Hungary, July 18-20, 2016,
pages 18:1–18:12, 2016.
- H. M. Jamil. A visual interface for querying heterogeneous phylogenetic databases.
IEEE/ACM Transactions on Computational Biology and Bioinformatics, pages 1–14, January 2016.
DOI10.1109/TCBB.2016.2520943.
- H. Kardes and M. H. Gu¨nes. Structural graph indexing for mining complex networks. In
ICDCS Workshops, pages 99–104, 2010.
- S. Khuri and T. Back. An evolutionary heuristic for the minimum vertex cover problem. In Workshop
18th Annual German Conference Artificial Intelligence, pages 86–90, Saarbrucken, Germany, 1994.
- Y. Kou, Y. Li, and X. Meng. Dsi: A method for indexing large graphs using distance set. In
WAIM, pages 297–308, 2010.
- G. Lan, G. W. DePuy, and G. E. Whitehouse. An effective and simple heuristic for the set covering
problem. European Journal of Operational Research, 176:1387–1403, 2007.
- N. Mamoulis. Efficient processing of joins on set-valued attributes. In SIGMOD Conference, pages 157–
168, 2003.
- M. Mongiov `ı, R. D. Natale, R. Giugno, A. Pulvirenti, A. Ferro, and R. Sharan. Sigma: a set-cover-based
inexact graph matching algorithm. J. Bioinformatics and Computational Biology, 8(2):199–218, 2010.
- M. Mongiov `ı, R. D. Natale, R. Giugno, A. Pulvirenti, A. Ferro, and R. Sharan. Sigma: a set-cover-based
inexact graph matching algorithm. J. Bioin. and Comp. Bio., 8(2):199–218, 2010.
- S. Poljak. A note on stable sets and coloring of graphs. Commun. Math. Univ. Carolinae, 15:307–309, 1974.
- Z. G. Ren, Z. R. Feng, L. J. Ke, and Z. J. Zhang. New ideas for applying ant colony optimization to the
set covering problem. Computers & Industrial Engineering, 58:774–784, 2010.
- C. R. Rivero and H. M. Jamil. On isomorphic matching of large disk-resident graphs using an xquery
engine. In Workshops Proceedings of the 30th International Conference on Data Engineering
Workshops, ICDE, Chicago, IL, USA, March 31 - April 4, pages 20–27, 2014.
- C. R. Rivero and H. M. Jamil. Efficient and scalable labeled subgraph matching using SG- Match.
Knowledge and Information Systems, 2016. DOI 10.1007/s10115-016-0968-2.
- M. Santo, P. Foggia, C. Sansone, and M. Vento. A large database of graphs and its use for benchmarking
graph isomorphism algorithms. Pattern Recognition Letters, 24:1067–1079, 2003.
- H. Shang, Y.Zhang, X. Lin, and J. X. Yu. Taming verification hardness: an efficient algorithm for testing
subgraph isomorphism. PVLDB, 1:364–375, 2008.
- M. Terrovitis, P. Bouros, P. Vassiliadis, T. K. Sellis, and N. Mamoulis. Efficient answering of set
containment queries for skewed item distributions. In EDBT, pages 225–236, 2011.
- Y. Tian and J. M. Patel. Tale: A tool for approximate large graph matching. ICDE, pages 963–972, 2008.
- S. Trißl. Cost-based optimization of graph queries. In Workshop on Innovative Database Research,
SIGMOD, 2007.
- S. Trißl and U. Leser. Fast and practical indexing and querying of very large graphs. In
SIGMOD Conference, pages 845–856, 2007.
- J. R. Ullmann. An algorithm for subgraph isomorphism. J. ACM, 23(1):31–42, 1976.
- M. Yagiura, M. Kishida, and T. Ibaraki. A 3-flip neighborhood local search for the set covering problem.
European Journal of Operational Research, 172:472–499, 2006.
- X. Yan, P. S. Yu, and J. Han. Graph indexing based on discriminative frequent structure analysis. ACM
Trans. Database Syst., 30(4):960–993, 2005.
- X. Yan, P. S. Yu, and J. Han. Graph indexing based on discriminative frequent structure analysis.
TODS, 30(4):960–993, 2005.
- B. Yelbay. Minimum hub cover problem: Solution methods and applications. Dissertation, Sabanci
University, Turkey, 2014.
- B. Yelbay, S. I. Birbil, K. Bu¨lbu¨l, and H. M. Jamil. Approximating the minimum hub cover problem on
planar graphs. Optimization Letters, 10(1):33–45, 2016.
- B. Yelbay, S¸.
˙I.Birbil, and K. Bu¨lbu¨l. The set covering problem revisited: An empirical
study of the value of dual information. Journal of Industrial and Management Optimization, 11(2):575–594,
2015. DOI 10.3934/jimo.2015.11.575.
- D. Yuan and P. Mitra. A lattice-based graph index for subgraph search. In WebDB, 2011.
- L. A. Zager and G. C. Verghese. Graph similarity scoring and matching. Appl. Math. Lett., 21(1):86–94,
2008.
- S. Zhang, J. Li, H. Gao, and Z. Zou. A novel approach for efficient supergraph query processing on
graph databases. In EDBT, pages 204–215, 2009.
- S. Zhang, S. Li, and J. Yang. Gaddi: distance index-based subgraph matching in biological networks.
In EDBT, pages 192–203, 2009.
- S. Zhang, S. Li, and J. Yang. Summa: subgraph matching in massive graphs. In CIKM, pages 1285–1288,
2010.
- S. Zhang, J. Yang, and W. Jin. Sapper: Subgraph indexing and approximate matching in large graphs.
PVLDB, 3(1):1185–1194, 2010.
- P. Zhao and J. Han. On graph query optimization in large networks. PVLDB, 3(1):340–351, 2010.
- K. Zhu, Y. Zhang, X. Lin, G. Zhu, and W. Wang. Nova: A novel and efficient framework for finding
subgraph isomorphism mappings in large graphs. In DASFAA (1), pages 140–154, 2010.
- L. Zou, L. Chen, H. Zhang, Y. Lu, and Q. Lou. Summarization graph indexing: Beyond frequent
structure-based approach. In DASFAA, pages 141–155, 2008.