Fg-index: towards verification-free query processing on graph databases. Graphs are prevalently used to model the relationships between objects in various domains. With the increasing usage of graph databases, it has become more and more demanding to efficiently process graph queries. Querying graph databases is costly since it involves subgraph isomorphism testing, which is an NP-complete problem. In recent years, some effective graph indexes have been proposed to first obtain a candidate answer set by filtering part of the false results and then perform verification on each candidate by checking subgraph isomorphism. Query performance is improved since the number of subgraph isomorphism tests is reduced. However, candidate verification is still inevitable, which can be expensive when the size of the candidate answer set is large. In this paper, we propose a novel indexing technique that constructs a nested inverted-index, called FG-index, based on the set of Frequent subGraphs (FGs). Given a graph query that is an FG in the database, FG-index returns the exact set of query answers without performing candidate verification. When the query is an infrequent graph, FG-index produces a candidate answer set which is close to the exact answer set. Since an infrequent graph means the graph occurs in only a small number of graphs in the database, the number of subgraph isomorphism tests is small. To ensure that the index fits into the main memory, we propose a new notion of δ-Tolerance Closed Frequent Graphs (δ-TCFGs), which allows us to flexibly tune the size of the index in a parameterized way. Our extensive experiments verify that query processing using FG-index is orders of magnitude more efficient than using the state-of-the-art graph index.
Keywords for this software
References in zbMATH (referenced in 9 articles )
Showing results 1 to 9 of 9.
- Pal, Dipali; Rao, Praveen; Slavov, Vasil; Katib, Anas: Fast processing of graph queries on a large database of small and medium-sized data graphs (2016)
- Yuan, Ye; Wang, Guoren; Chen, Lei; Ning, Bo: Efficient pattern matching on big uncertain graphs (2016)
- Lee, Chun-Hee; Chung, Chin-Wan: Efficient search in graph databases using cross filtering (2014)
- Zheng, Weiguo; Zou, Lei; Lian, Xiang; Zhang, Huaming; Wang, Wei; Zhao, Dongyan: SQBC: an efficient subgraph matching method over large and dense graphs (2014)
- Takigawa, Ichigaku; Mamitsuka, Hiroshi: Efficiently mining (\delta)-tolerance closed frequent subgraphs (2011)
- Zhang, Shuo; Gao, Xiaofeng; Wu, Weili; Li, Jianzhong; Gao, Hong: Efficient algorithms for supergraph query processing on graph databases (2011)
- Zhu, Linhong; Ng, Wee Keong; Cheng, James: Structure and attribute index for approximate graph matching in large graphs (2011) ioport
- Cheng, James; Ke, Yiping; Ng, Wilfred: Effective elimination of redundant association rules (2008) ioport
- Cheng, James; Ke, Yiping; Ng, Wilfred: Effective elimination of redundant association rules. (2008) ioport