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: h24b3e46a664329ef
Venue: VLDB
Year: 2007
Pagerank: 0.00014357361
Overall Rank: 737 | 95.05%
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
289	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021960834
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020116134
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018278591
489	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017440023
659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015048943
713	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00014571507
784	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014015324
1,100	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012007739
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011892544
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011621825
1,374	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00010875727
1,420	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010724642
1,901	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	9.4014537e-05
2,701	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.114832e-05
3,369	Connected Substructure Similarity Search	2010	SIGMOD	7.3663492e-05
3,506	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	7.246695e-05
4,077	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	6.8156109e-05
4,826	VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework	2013	CIDR	6.3903931e-05
5,223	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB	6.2201582e-05
5,481	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.1126446e-05
5,483	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	6.1113443e-05
5,847	Graph-Aware, Workload-Adaptive SPARQL Query Caching	2015	SIGMOD	5.9701747e-05
6,506	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.758981e-05
9,051	GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases	2010	SIGMOD	5.2290958e-05
9,322	Processing Proximity Relations in Road Networks	2010	SIGMOD	5.1937083e-05
10,238	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	5.0544949e-05
10,750	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.9769913e-05
11,984	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	4.9769913e-05
12,538	A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery	2013	SIGMOD	4.9769913e-05
12,672	iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques	2011	SIGMOD	4.9769913e-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
141	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.0002928095
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026688651
193	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00025647819
1,217	A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures	2003	VLDB	0.00011485448

Semantically Similar Papers

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