DBScholar

Back to papers

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.00014363536
Overall Rank
736 | 95.06%
DOI
-

Incoming Non-self Citations Over Time

Authors

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
288 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00021969641
355 On Graph Query Optimization in Large Networks 2010 VLDB 0.00020124083
438 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018286607
490 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017438618
657 Efficient Subgraph Matching by Postponing Cartesian Products 2016 SIGMOD 0.0001505607
712 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014578373
783 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014021799
1,100 CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching 2019 SIGMOD 0.00012013426
1,133 Comparing Stars: On Approximating Graph Edit Distance 2009 VLDB 0.00011898162
1,181 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.00011627329
1,374 Neighborhood Based Fast Graph Search in Large Networks 2011 SIGMOD 0.00010880336
1,419 Fast and Exact Top-k Search for Random Walk with Restart 2012 VLDB 0.00010728945
1,900 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.4059063e-05
2,702 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.1177147e-05
3,369 Connected Substructure Similarity Search 2010 SIGMOD 7.3698379e-05
3,506 Performance and Scalability of Indexed Subgraph Query Processing Methods 2015 VLDB 7.2501249e-05
4,075 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8188389e-05
4,824 VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework 2013 CIDR 6.3934185e-05
5,218 Efficient Streaming Subgraph Isomorphism with Graph Neural Networks 2021 VLDB 6.2231041e-05
5,477 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 6.1155396e-05
5,478 Towards Proximity Pattern Mining in Large Graphs 2010 SIGMOD 6.1142386e-05
5,844 Graph-Aware, Workload-Adaptive SPARQL Query Caching 2015 SIGMOD 5.9730023e-05
6,504 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.7617085e-05
9,043 GBLENDER: Towards Blending Visual Query Formulation and Query Processing in Graph Databases 2010 SIGMOD 5.2315718e-05
9,313 Processing Proximity Relations in Road Networks 2010 SIGMOD 5.1961681e-05
10,232 Graph Exploration: From Users to Large Graphs 2017 SIGMOD 5.0568888e-05
10,740 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 4.9793485e-05
11,978 MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces 2021 SIGMOD 4.9793485e-05
12,532 A Direct Mining Approach To Efficient Constrained Graph Pattern Discovery 2013 SIGMOD 4.9793485e-05
12,666 iGraph in Action: Performance Analysis of Disk-Based Graph Indexing Techniques 2011 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

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.00029294114
176 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00026700508
192 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00025659453
1,216 A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures 2003 VLDB 0.00011490695
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,290 Effective Indexing for Dynamic Structural Graph Clustering 2022 VLDB
2 3,369 Connected Substructure Similarity Search 2010 SIGMOD
3 7,086 Indexing for Subtree Similarity-Search using Edit Distance 2013 SIGMOD
4 6,973 A Scalable Index for Top-k Subtree Similarity Queries 2019 SIGMOD
5 8,644 Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs 2025 SIGMOD
6 6,760 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,376 Towards Graph Containment Search and Indexing 2007 VLDB