Efficient query processing on graph databases

ABSTRACT

We study the problem of processing subgraph queries on a database that consists of a set of graphs. The answer to a subgraph query is the set of graphs in the database that are supergraphs of the query. In this article, we propose an efficient index, FG*-index, to solve this problem.

The cost of processing a subgraph query using most existing indexes mainly consists of two parts: the index probing cost and the candidate verification cost. Index probing is to find the query in the index, or to find the graphs from which we can generate a candidate answer set for the query. Candidate verification is to test whether each graph in the candidate set is indeed a supergraph of the query. We design FG*-index to minimize these two costs as follows.

FG*-index consists of three components: the FG-index, the feature-index, and the FAQ-index. First, the FG-index employs the concept of Frequent subGraph (FG) to allow the set of queries that are FGs to be answered without candidate verification. We call this set of queries FG-queries. We can enlarge the set of FG-queries so that more queries can be answered without candidate verification; however, a larger set of FG-queries implies a larger FG-index and hence the index probing cost also increases. We propose the feature-index to reduce the index probing cost. The feature-index uses features to filter false results that are matched in the FG-index, so that we can quickly find the truly matching graphs for a query. For processing non-FG-queries, we propose the FAQ-index, which is dynamically constructed from the set of Frequently Asked non-FG-Queries (FAQs). Using the FAQ-index, verification is not required for processing FAQs and only a small number of candidates need to be verified for processing non-FG-queries that are not frequently asked. Finally, a comprehensive set of experiments verifies that query processing using FG*-index is up to orders of magnitude more efficient than state-of-the-art indexes and it is also more scalable.

REFERENCES

• 1: Qun Chen , Andrew Lim , Kian Win Ong, D(k)-index: an adaptive structural summary for graph-structured data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872776]
• 2: James Cheng , Yiping Ke , Wilfred Ng, \delta-Tolerance Closed Frequent Itemsets, Proceedings of the Sixth International Conference on Data Mining, p.139-148, December 18-22, 2006 [doi>10.1109/ICDM.2006.1]
• 3: James Cheng , Yiping Ke , Wilfred Ng, Effective elimination of redundant association rules, Data Mining and Knowledge Discovery, v.16 n.2, p.221-249, April 2008 [doi>10.1007/s10618-007-0084-8]
• 4: James Cheng , Yiping Ke , Wilfred Ng, Maintaining frequent closed itemsets over a sliding window, Journal of Intelligent Information Systems, v.31 n.3, p.191-215, December 2008 [doi>10.1007/s10844-007-0042-3]
• 5: James Cheng , Yiping Ke , Wilfred Ng, A survey on algorithms for mining frequent itemsets over data streams, Knowledge and Information Systems, v.16 n.1, p.1-27, July 2008 [doi>10.1007/s10115-007-0092-4]
• 6: James Cheng , Yiping Ke , Wilfred Ng , An Lu, Fg-index: towards verification-free query processing on graph databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247574]
• 7: Cheng, J. and Ng, W. 2004. Xqzip: Querying compressed XML using structural indexing. In Proceedings of the International Conference on Extending Database Technology (EDBT'04), 219--236.
• 8: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 9: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 10: Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003 [doi>10.1145/776985.776986]
• 11: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 12: Ralf Hartmut Güting, GraphDB: Modeling and Querying Graphs in Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.297-308, September 12-15, 1994
• 13: Huahai He , Ambuj K. Singh, Closure-Tree: An Index Structure for Graph Queries, Proceedings of the 22nd International Conference on Data Engineering, p.38, April 03-07, 2006 [doi>10.1109/ICDE.2006.37]
• 14: Holder, L. B., Cook, D. J., and Djoko, S. 1994. Substucture discovery in the subdue system. In Proceedings of the Workshop at the International SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'94), 169--180.
• 15: Jun Huan , Wei Wang , Deepak Bandyopadhyay , Jack Snoeyink , Jan Prins , Alexander Tropsha, Mining protein family specific residue packing patterns from protein structure graphs, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.308-315, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974655]
• 16: Jun Huan , Wei Wang , Jan Prins , Jiong Yang, SPIN: mining maximal frequent subgraphs from graph databases, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014123]
• 17: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 18: James, C. A., Weininger, D., and Delany, J. 2003. Daylight theory manual daylight version 4.82. Daylight Chemical Information Systems, Inc.
• 19: Jiang, H., Wang, H., Yu, P. S., and Zhou, S. 2007. Gstring: A novel approach for efficient search in graph databases. In Proceedings of the International Conference on Data Engineering (ICDE'07), 566--575.
• 20: Raghav Kaushik , Philip Bohannon , Jeffrey F Naughton , Henry F Korth, Covering indexes for branching path queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564707]
• 21: Yiping Ke , James Cheng , Wilfred Ng, Correlation search in graph databases, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281236]
• 22: Yiping Ke , James Cheng , Wilfred Ng, Efficient Correlation Search from Graph Databases, IEEE Transactions on Knowledge and Data Engineering, v.20 n.12, p.1601-1615, December 2008 [doi>10.1109/TKDE.2008.86]
• 23: Yehuda Koren , Stephen C. North , Chris Volinsky, Measuring and extracting proximity in networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150432]
• 24: Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
• 25: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceedings of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 26: Ng, W. and Cheng, J. 2007. An efficient index lattice for xml query evaluation. In Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA'07), 753--767.
• 27: Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
• 28: Srinath Srinivasa , Sujit Kumar, A platform based on the multi-dimensional data modal for analysis of bio-molecular structures, Proceedings of the 29th international conference on Very large data bases, p.975-986, September 09-12, 2003, Berlin, Germany
• 29: Hanghang Tong , Christos Faloutsos, Center-piece subgraphs: problem definition and fast solutions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150448]
• 30: Hanghang Tong , Christos Faloutsos , Brian Gallagher , Tina Eliassi-Rad, Fast best-effort pattern matching in large attributed graphs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281271]
• 31: Williams, D. W., Huan, J., and Wang, W. 2007. Graph database indexing using structured graph decomposition. In Proceedings of the International Conference on Data Engineering (ICDE'07), 976--985.
• 32: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining, p.721, December 09-12, 2002
• 33: Xifeng Yan , Jiawei Han, CloseGraph: mining closed frequent graph patterns, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956784]
• 34: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing based on discriminative frequent structure analysis, ACM Transactions on Database Systems (TODS), v.30 n.4, p.960-993, December 2005 [doi>10.1145/1114244.1114248]
• 35: Xifeng Yan , Philip S. Yu , Jiawei Han, Substructure similarity search in graph databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066244]
• 36: Jeffery Xu Yu , Zhihong Chong , Hongjun Lu , Aoying Zhou, False positive or false negative: mining frequent itemsets from high speed transactional data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.204-215, August 31-September 03, 2004, Toronto, Canada
• 37: Ning Zhang , M. Tamer Özsu , Ihab F. Ilyas , Ashraf Aboulnaga, FIX: feature-based indexing technique for XML documents, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 38: Zhang, S., Hu, M., and Yang, J. 2007. Treepi: A novel graph indexing method. In Proceedings of the International Conference on Data Mining (ICDE'07), 966--975.
• 39: Peixiang Zhao , Jeffrey Xu Yu , Philip S. Yu, Graph indexing: tree + delta <= graph, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Graph databases, frequent subgraphs, graph indexing, graph query processing