Abstract
This paper studies the problem of processing supergraph queries, that is, given a database containing a set of graphs, find all the graphs in the database of which the query graph is a supergraph. Existing works usually construct an index and performs a filtering-and-verification process, which still requires many subgraph isomorphism testings. There are also significant overheads in both index construction and maintenance. In this paper, we design a graph querying system that achieves both fast indexing and efficient query processing. The index is constructed by a simple but fast method of extracting the commonality among the graphs, which does not involve any costly operation such as graph mining. Our query processing has two key techniques, direct inclusion and filtering. Direct inclusion allows partial query answers to be included directly without candidate verification. Our filtering technique further reduces the candidate set by operating on a much smaller projected database. Experimental results show that our method is significantly more efficient than the existing works in both indexing and query processing, and our index has a low maintenance cost.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and issues in data stream systems. In: PODS, pp. 1–16. (2002)
Chen, C., Yan, X., Yu, P.S., Han, J., Zhang, D.-Q., Gu X.: Towards graph containment search and indexing. In: VLDB, pp. 926–937. (2007)
Cheng, J., Ke, Y., Ng, W., Lu, A.: Fg-index: towards verification-free query processing on graph databases. In: SIGMOD Conference, pp. 857–872. (2007)
Golab L., Özsu M.T.: Issues in data stream management. SIGMOD Rec. 32(2), 5–14 (2003)
He, H., Singh, A.K.: Closure-tree: an index structure for graph queries. In: ICDE, pp. 38. (2006)
Huan, J., Wang, W., Bandyopadhyay, D., Snoeyink, J., Prins, J., Tropsha A.: Mining protein family specific residue packing patterns from protein structure graphs. In: RECOMB, pp. 308–315. (2004)
Huan, J., Wang, W., Prins, J., Yang, J.: Spin: mining maximal frequent subgraphs from graph databases. In: KDD, pp. 581–586. (2004)
Inokuchi, A., Washio, T., Motoda, H.: An apriori-based algorithm for mining frequent substructures from graph data. In: PKDD, pp. 13–23. (2000)
James C.A., Weininger D., Delany J.: Daylight theory manual daylight version 4.82. Daylight Chemical Information Systems Inc., Irvine, CA (2003)
Jiang, H., Wang, H., Yu, P.S., Zhou, S.: Gstring: a novel approach for efficient search in graph databases. In: ICDE, pp. 566–575. (2007)
Koren, Y., North, S.C., Volinsky, C.: Measuring and extracting proximity in networks. In: KDD, pp. 245–255. (2006)
Shang, H., Zhang, Y., Lin, X., Yu, J.X.: Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. In: VLDB, (2008)
Shasha, D., Wang, J.T.-L., Giugno, R.: Algorithmics and applications of tree and graph searching. In: PODS, pp.39–52. (2002)
Tong, H., Faloutsos, C.: Center-piece subgraphs: problem definition and fast solutions. In: KDD, pp. 404–413. (2006)
Urhan T., Franklin M.J.: Xjoin: a reactively-scheduled pipelined join operator. IEEE Data Eng. Bull. 23(2), 27–33 (2000)
Williams, D.W., Huan, J., Wang, W.: Graph database indexing using structured graph decomposition. In: ICDE, pp. 976–985. (2007)
Xin, D., Han, J., Yan, X., Cheng, H.: Mining compressed frequent-pattern sets. In: VLDB, pp. 709–720. (2005)
Yan, X., Han, J.: gspan: graph-based substructure pattern mining. In: ICDM, pp. 721–724. (2002)
Yan, X., Han, J.: Closegraph: mining closed frequent graph patterns. In: KDD, pp. 286–295. (2003)
Yan X., Yu P.S., Han J.: Graph indexing based on discriminative frequent structure analysis. ACM Trans. Database Syst. 30(4), 960–993 (2005)
Zhang, S., Hu, M., Yang, J.: Treepi: a novel graph indexing method. In: ICDE, pp. 966–975. (2007)
Zhang, S., Li, J., Gao, H., Zou, Z.: A novel approach for efficient supergraph query processing on graph databases. In: EDBT, pp. 204–215. (2009)
Zhao, P., Yu, J.X., Yu, P.S.: Graph indexing: tree + delta >= graph. In: VLDB, pp. 938–949. (2007)
Zou, L., 0002, L.C., Yu, J.X., Lu, Y.: A novel spectral coding in a large graph database. In: EDBT, pp. 181–192. (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported in part by the AcRF Tier-1 Grant (M52020092) from Ministry of Education of Singapore, the RGC Research Direct Grant of the CUHK Projects 2050421 and 2150472, the CUHK Postdoctoral Fellowship Grant 2008-2009, and the RGC of the Hong Kong SAR, CUHK No. 419008. Part of this research was conducted when the first author was a postdoctoral fellow in the Department of Computer Science and Engineering at CUHK.
Rights and permissions
About this article
Cite this article
Cheng, J., Ke, Y., Fu, A.WC. et al. Fast graph query processing with a low-cost index. The VLDB Journal 20, 521–539 (2011). https://doi.org/10.1007/s00778-010-0212-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-010-0212-8