Graph Indexing: Tree + Delta >= Graph

Summary: Tree+Delta is a cost-effective graph index for subgraph containment that combines frequent tree-features (Tree) with on-demand discriminative graphs (Delta) to improve pruning. It yields a compact index, two orders of magnitude faster construction, and outperforms gIndex and C-Tree in containment queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9834
Venue: VLDB
Year: 2007
Pagerank: 0.00014565738
Overall Rank: 727 | 95.02%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Peixiang Zhao (Chinese University of Hong Kong)
2. Jeffrey Xu Yu (Chinese University of Hong Kong)
3. Philip S. Yu (IBM)

BibTeX Citation

@article{zhao_vldb07,
        title = {{Graph Indexing: Tree + Delta >= Graph}},
        author = {Zhao, Peixiang and Yu, Jeffrey Xu and Yu, Philip S.},
        journal = {PVLDB},
        series = {{VLDB} '07},
        pages = {938},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 30 of 30 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022253507
352	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020375193
431	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018577017
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017717377
659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015214062
776	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014110016
809	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00013874588
1,102	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012166591
1,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00012117375
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001179597
1,394	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.0001093153
1,414	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010848387
2,190	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	8.9804702e-05
2,650	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.2920414e-05
3,311	Connected Substructure Similarity Search	2010	SIGMOD	7.5353184e-05
3,477	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	7.3791229e-05
4,749	VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework	2013	CIDR	6.5250721e-05
4,983	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	6.4127092e-05
5,118	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB	6.3580186e-05
5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.2436385e-05
5,401	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	6.2318138e-05
5,716	Graph-Aware, Workload-Adaptive SPARQL Query Caching	2015	SIGMOD	6.1100964e-05
6,393	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.8879832e-05
8,884	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.3514928e-05
9,143	Processing Proximity Relations in Road Networks	2010	SIGMOD	5.3153925e-05
10,037	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	5.1729561e-05
10,558	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	5.093636e-05
11,671	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	5.093636e-05
12,241	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD	5.093636e-05
12,375	iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques	2011	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029877792
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026138589
1,196	A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures	2003	VLDB	0.00011714981

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,141	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB
2	3,311	Connected Substructure Similarity Search	2010	SIGMOD
3	6,947	Indexing for Subtree Similarity-Search using Edit Distance	2013	SIGMOD
4	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
5	8,477	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD
6	6,631	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD
7	326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD
8	177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
9	3,477	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB
10	2,328	Towards Graph Containment Search and Indexing	2007	VLDB