Efficient query processing on graph databases
ACM Transactions on Database SystemsPublished 1 April 2009
James Cheng, Yiping Ke, Wilfred Ng
Citations63
SJR quartileQ1
SJR score0.91
SNIP1.85
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An efficient index, FG*-index, which is dynamically constructed from the set of Frequently Asked non-FG-Queries (FAQs), and 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.
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.
Keywords
Computer Science
The complexity of theorem-proving procedures
6,107 Citations1971Stephen Cook
It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.
gSpan: graph-based substructure pattern mining
2,030 Citations2003Xifeng Yan, Jiawei Han
A novel algorithm called gSpan (graph-based substructure pattern mining), which discovers frequent substructures without candidate generation by building a new lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label.
Proceedings of the VLDB EndowmentApproximate frequency counts over data streams
1,195 Citations2012Gurmeet Singh Manku, Rajeev Motwani
DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases
1,147 Citations1997Roy Goldman, Jennifer Widom
The theoretical foundations of DataGuides are presented along with an algorithm for their creation and an overview of incremental maintenance, and performance results based on the implementation of dataGuides in the Lore DBMS for semistructured data are provided.
Lecture notes in computer scienceAn Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
1,029 Citations2000Akihiro Inokuchi, Takashi Washio +1 more
A novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set through the extended algorithm of the basket analysis is proposed.
ACM SIGMOD RecordIssues in data stream management
916 Citations2003Lukasz Golab, M. TAMER ÖZSU
The purpose of this paper is to review recent work in data stream management systems, with an emphasis on application requirements, data models, continuous query languages, and query evaluation.
CloseGraph
631 Citations2003Xifeng Yan, Jiawei Han
A closed graph pattern mining algorithm, CloseGraph, is developed by exploring several interesting pruning methods and shows that it not only dramatically reduces unnecessary subgraphs to be generated but also substantially increases the efficiency of mining, especially in the presence of large graph patterns.
Lecture notes in computer scienceIndex Structures for Path Expressions
602 Citations1999Tova Milo, Dan Suciu
In recent years there has been an increased interest in managing data that does not conform to traditional data models, like the relational or object oriented model, and the term semistructured data has been used to refer to such data.
Algorithmics and applications of tree and graph searching
385 Citations2002Dennis Shasha, Jason T. L. Wang +1 more
This paper surveys both algorithms and applications for generalizing keyword search to keytree and keygraph searching, because trees and graphs have many applications in next-generation database systems.
Fast discovery of connection subgraphs
360 Citations2004Christos Faloutsos, Kevin S. McCurley +1 more
This work defines a connection subgraph as a small subgraph of a large graph that best captures the relationship between two nodes, and presents a formal definition of this problem, and an ideal solution based on electricity analogues.
SPIN
326 Citations2004Jun Huan, Wei Wang +2 more
This paper proposes a new algorithm that mines only maximal frequent subgraphs, i.e. sub graphs that are not a part of any other frequent sub graph, and demonstrates that this algorithm can achieve a five-fold speed up over the current state-of-the-art subgraph mining algorithms.
Substructure similarity search in graph databases
317 Citations2005Xifeng Yan, Philip S. Yu +1 more
This paper investigates the issues of substructure similarity search using indexed features in graph databases, and develops a multi-filter composition strategy, where each filter uses a distinct and complementary subset of the features.
Covering indexes for branching path queries
307 Citations2002Raghav Kaushik, Philip Bohannon +2 more
This paper asks if the traditional relational query acceleration techniques of summary tables and covering indexes have analogs for branching path expression queries over tree- or graph-structured XML data and shows that the forward-and-backward index already proposed in the literature can be viewed as a structure analogous to a summary table or covering index.
Closure-Tree: An Index Structure for Graph Queries
296 Citations2006Huahai He, Ambuj K. Singh
The concept of a graph closure, a generalized graph that represents a number of graphs, is introduced and the indexing technique, called Closure-tree, organizes graphs hierarchically where each node summarizes its descendants by a graphclosure.
Center-piece subgraphs
265 Citations2006Hanghang Tong, Christos Faloutsos
Wall-clock timing results on the DBLP dataset show that the proposed approximation achieve good accuracy for about 6:1 speedup, and experiments confirm that the method naturally deals with multi-source queries and that the resulting subgraphs agree with the intuition.
Fg-index
259 Citations2007James Cheng, Yiping Ke +2 more
A novel indexing technique that constructs a nested inverted-index, called FG- index, based on the set of Frequent subGraphs (FGs), which returns the exact set of query answers without performing candidate verification and is orders of magnitude more efficient than using the state-of-the-art graph index.
Fast best-effort pattern matching in large attributed graphs
254 Citations2007Hanghang Tong, Christos Faloutsos +2 more
The G-Ray ("Graph X-Ray") method finds high-quality subgraphs in time linear on the size of the data graph, where nodes have attributes, such as a social network where the nodes are labelled with each person's job title.
D(k)-index
235 Citations2003Qun Chen, Andrew Lim +1 more
The D(k) index is introduced, an adaptive structural summary for general graph structured documents based on the concept of bisimilarity, and is shown to be a more effective structural summary than previous static ones, as a result of its query load sensitivity.
Knowledge Discovery and Data MiningSubstructure discovery in the SUBDUE system
217 Citations1994Lawrence B. Holder, Diane J. Cook +1 more
The SUBDUE system, which uses the minimum description length (MDL) principle to discover substructures that compress the database and represent structural concepts in the data, is described.
Very Large Data BasesGraph indexing: tree + delta <= graph
201 Citations2007Peixiang Zhao, Jeffrey Xu Yu +1 more
This study verifies that (Tree+Δ) is a better choice than graph for indexing purpose, denoted (Tree-Δ ≥Graph), to address the graph containment query problem and achieves an order of magnitude better performance in index construction.
TreePi: A Novel Graph Indexing Method
189 Citations2007Shijie Zhang, Meng Hu +1 more
A new algorithm which utilizes the location information of indexing structures is used to perform subgraph isomorphism tests and this method is applied on a wide range of real and synthetic data to demonstrate the usefulness and effectiveness of this approach.
GraphDB: Modeling and Querying Graphs in Databases
180 Citations1994Ralf Hartmut Güting
A data model and query language that integrates an explicit modeling and querying of graphs smoothly into a standard database environment and permits a natural representation and sophisticated querying of networks, in particular of spatially embedded networks like highways, public transport, etc.
Graph Database Indexing Using Structured Graph Decomposition
160 Citations2007Daniel Williams, Jun Huan +1 more
This work introduces a novel method of indexing graph databases in order to facilitate subgraph isomorphism and similarity queries and demonstrates its effectiveness in answering queries for two practical datasets.
Knowledge and Information SystemsA survey on algorithms for mining frequent itemsets over data streams
157 Citations2007James Cheng, Yiping Ke +1 more
This paper describes the efforts and main techniques for mining data streams and presents a comprehensive survey of a number of the state-of-the-art algorithms on mining frequent itemsets over data streams.
Elsevier eBooksFalse Positive or False NegativeMining Frequent Itemsets from High Speed Transactional Data Streams
149 Citations2004Jeffery Xu Yu, Zhihong Chong +2 more
GString: A Novel Approach for Efficient Search in Graph Databases
142 Citations2007Haoliang Jiang, Haixun Wang +2 more
A novel sequencing method is introduced to capture the semantics of the underlying graph data and it not only reduces the size of resulting sequences, but also enables semantic-based searching.
Measuring and extracting proximity in networks
136 Citations2006Yehuda Koren, Stephen C. North +1 more
A new way of measuring and extracting proximity in networks called "cycle free effective conductance"(CFEC) is proposed, which can handle more than two endpoints, directed edges, is statistically well-behaved, and produces an effectiveness score for the computed subgraphs.
Mining protein family specific residue packing patterns from protein structure graphs
110 Citations2004Jun Huan, Wei Wang +4 more
The results indicate that graphs based on both almost-Delaunay and Delaunay tessellations are sparser than the contact distance graphs; yet they are robust and efficient for mining protein spatial motifs.
ACM Transactions on Database SystemsGraph indexing based on discriminative frequent structure analysis
98 Citations2005Xifeng Yan, Philip S. Yu +1 more
This article proposes a novel indexing model based on discriminative frequent structures that are identified through a graph mining process and shows that the compact index built under this model can achieve better performance in processing graph queries.
Lecture notes in computer scienceXQzip: Querying Compressed XML Using Structural Indexing
86 Citations2004James Cheng, Wilfred Ng
This paper focuses on the problem of running queries on compressed XML data and some compressors proposed to address this problem have been proposed but are usually worse than that of XMill and that of the generic compressor gzip.
Proceedings\delta-Tolerance Closed Frequent Itemsets
49 Citations2006James Cheng, Yiping Ke +1 more
This paper proposes the (delta-Tolerance CFIs delta- TCFIs), a relaxation of the restrictive definition of CFIs and two algorithms to mine delta-TCFIs, which are significantly faster and consumes less memory than the algorithms of the state-of-the-art concise representations of FIs.
Journal of Intelligent Information SystemsMaintaining frequent closed itemsets over a sliding window
49 Citations2007James Cheng, Yiping Ke +1 more
The notion of semi-FCIs is proposed, which is to progressively increase the minimum support threshold for an itemset as it is retained longer in the window, thereby drastically reducing the number of itemsets that need to be maintained and processed.
Correlation search in graph databases
48 Citations2007Yiping Ke, James Cheng +1 more
This paper proposes a new problem of correlation mining from graph databases, called Correlated Graph Search (CGS), which adopts Pearson's correlation coefficient as a correlation measure to take into consideration the occurrence distributions of graphs.
FIX: feature-based indexing technique for XML documents
43 Citations2006Ning Zhang, M. TAMER ÖZSU +2 more
This paper proposes a feature-based indexing technique, called FIX, based on spectral graph theory, that could gain an order of magnitude performance improvement for many XPath queries over existing evaluation techniques.
Data Mining and Knowledge DiscoveryEffective elimination of redundant association rules
27 Citations2007James Cheng, Yiping Ke +1 more
A set of inference rules are devised, with which the set of δ-TARs is proved to be a non-redundant representation of ARs, and a compact tree structure is developed, which facilitates the efficient generation of theδ- TARs and derivation of other ARs.
Elsevier eBooksA Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures
26 Citations2003Srinath Srinivasa, Sujit Kumar
Design and implementation issues of AnMol including schema structure and performance results are discussed in this paper.
IEEE Transactions on Knowledge and Data EngineeringEfficient Correlation Search from Graph Databases
22 Citations2008Yiping Ke, James Cheng +1 more
This work proposes a new problem of correlation mining from graph databases, called correlated graph search (CGS), and devise an efficient algorithm that mines the candidate set from a much smaller projected database and thus a significantly smaller set of candidates is obtained.
Lecture notes in computer scienceAn Efficient Index Lattice for XML Query Evaluation
3 Citations2007Wilfred Ng, James Cheng
This paper imposes a lattice structure on the SIT and calls the structure a SIT-lattice in order to enhance the applicability of the index and demonstrates that SLEs are able to support effective querying over very large XML documents in memory-limited hand-held devices.