Trade-Offs Computing Minimum Hub Cover Toward Optimized Labeled Graph Query Processing

Abstract

Trade-Offs Computing Minimum Hub Cover Toward Optimized Labeled Graph Query Processing

Abstract

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.

Keywords

• graph query processing
• minimum hub cover problem
• linear relaxation
• greedy algorithm
• subgraph isomorphism

References

1. 1. S. Abiteboul and J. V. den Bussche. Deep equality revisited. In DOOD, pages 213–228, 1995.
2. 2. 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.
3. 3. 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.
4. 4. S. Balaji, V. Swaminathan, and K. Kannan. Optimization of unweighted minimum vertex cover. World Academy of Science, Engineering and Technology, 67:508–513, 2010.
5. 5. R. Bar-Yehuda and S. Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2:198–203, 1981.
6. 6. 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.
7. 7. A. Caprara, P. Toth, and M. Fischetti. Algorithms for the set covering problem. Annals of Operations Research, 98:353–371, 2000.
8. 8.M. Caserta. Metaheuristics: progress in complex systems optimization, chapter 3, pages 43– 63. Springer, Berlin, 2007.

9. 9.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.
10. 10.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.
11. 11.S. M. Chung. Indexed extendible hashing. Inf. Process. Lett., 44(1):1–6, 1992.
12. 12.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.
13. 13.E. Dolan and J. More. Benchmarking optimization software with performance profiles. Mathematical Programming, 91:201–213,2002.
14. 14.I. Evans. Evolutionary algorithms for vertex cover. In 7th Annual Conference Evolutionary Programming, pages 377–386, New York, 1998.
15. 15.T. A. Feo and M. Resende. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8:67–71, 1989.
16. 16.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.
17. 17.R. Giugno and D. Shasha. GraphGrep: A fast and universal method for querying graphs. In ICPR, volume 2, pages 112–115, 2002.
18. 18.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.
19. 19.E. Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM Journal on Computing, 31:1608–1623, 2001.
20. 20.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.
21. 21.H. He and A. Singh. Graphs-at-a-time: query language and access methods for graph databases. In SIGMOD, pages 405–418, 2008.
22. 22.T. Imamura, K. Iwama, and T. Tsukiji. Approximated vertex cover for graphs with perfect matchings. IEICE Transactions, 89-D (8):2405–2410, 2006.
23. 23.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.
24. 24.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.
25. 25.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.
26. 26.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.
27. 27.H. Kardes and M. H. Gu¨nes. Structural graph indexing for mining complex networks. In ICDCS Workshops, pages 99–104, 2010.
28. 28.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.
29. 29.Y. Kou, Y. Li, and X. Meng. Dsi: A method for indexing large graphs using distance set. In WAIM, pages 297–308, 2010.
30. 30.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.
31. 31.N. Mamoulis. Efficient processing of joins on set-valued attributes. In SIGMOD Conference, pages 157– 168, 2003.
32. 32.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.
33. 33.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.
34. 34.S. Poljak. A note on stable sets and coloring of graphs. Commun. Math. Univ. Carolinae, 15:307–309, 1974.
35. 35.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.
36. 36.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.
37. 37.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.
38. 38.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.
39. 39.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.
40. 40.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.
41. 41.Y. Tian and J. M. Patel. Tale: A tool for approximate large graph matching. ICDE, pages 963–972, 2008.
42. 42.S. Trißl. Cost-based optimization of graph queries. In Workshop on Innovative Database Research, SIGMOD, 2007.
43. 43.S. Trißl and U. Leser. Fast and practical indexing and querying of very large graphs. In SIGMOD Conference, pages 845–856, 2007.
44. 44.J. R. Ullmann. An algorithm for subgraph isomorphism. J. ACM, 23(1):31–42, 1976
45. 45.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.
46. 46.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.
47. 47.X. Yan, P. S. Yu, and J. Han. Graph indexing based on discriminative frequent structure analysis. TODS, 30(4):960–993, 2005.
48. 48.B. Yelbay. Minimum hub cover problem: Solution methods and applications. Dissertation, Sabanci University, Turkey, 2014.
49. 49.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.
50. 50.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.
51. 51.D. Yuan and P. Mitra. A lattice-based graph index for subgraph search. In WebDB, 2011.
52. 52.L. A. Zager and G. C. Verghese. Graph similarity scoring and matching. Appl. Math. Lett., 21(1):86–94, 2008.
53. 53.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.
54. 54.S. Zhang, S. Li, and J. Yang. Gaddi: distance index-based subgraph matching in biological networks. In EDBT, pages 192–203, 2009.
55. 55.S. Zhang, S. Li, and J. Yang. Summa: subgraph matching in massive graphs. In CIKM, pages 1285–1288, 2010.
56. 56.S. Zhang, J. Yang, and W. Jin. Sapper: Subgraph indexing and approximate matching in large graphs. PVLDB, 3(1):1185–1194, 2010.
57. 57.P. Zhao and J. Han. On graph query optimization in large networks. PVLDB, 3(1):340–351, 2010.
58. 58.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.
59. 59.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.