Towards Graph Containment Search and Indexing
Summary: Introduces cIndex, a contrast-subgraph index for containment search (q contains g). Shows NP-complete feature selection for indexing features with a 1-1/e greedy approximation, extends to hierarchical indexing using clustering and sampling to speed construction, achieving near-optimal pruning and gains over traditional graph-search indices. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Chen Chen
- 2. Xifeng Yan
- 3. Philip S. Yu
- 4. Jiawei Han
- 5. Dong-Qing Zhang
- 6. Xiaohui Gu
Incoming Citations (Sorted by Pagerank)
Showing 10 of 10 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 949 | Comparing Stars: On Approximating Graph Edit Distance | 2009 | VLDB | 0.0001510288 |
| 2,402 | TreeSpan: Efficiently Computing Similarity All-Matching | 2012 | SIGMOD | 8.87387e-05 |
| 2,524 | Connected Substructure Similarity Search | 2010 | SIGMOD | 8.5993622e-05 |
| 3,894 | Performance and Scalability of Indexed Subgraph Query Processing Methods | 2015 | VLDB | 6.6531173e-05 |
| 4,959 | Efficient Subgraph Search over Large Uncertain Graphs | 2011 | VLDB | 5.7992713e-05 |
| 6,386 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.0820608e-05 |
| 6,870 | Updating Graph Indices with a One-Pass Algorithm | 2015 | SIGMOD | 4.8974284e-05 |
| 9,523 | ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs | 2020 | VLDB | 4.3273374e-05 |
| 11,602 | IDAR: Fast Supergraph Search Using DAG Integration | 2020 | VLDB | 4.1905499e-05 |
| 11,969 | Leveraging Graph Dimensions in Online Graph Search | 2015 | VLDB | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 61 | DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases | 1997 | VLDB | 0.00064281097 |
| 172 | Algorithmics and Applications of Tree and Graph Searching | 2002 | PODS | 0.00038837872 |
| 202 | Graph Indexing: A Frequent Structure-based Approach | 2004 | SIGMOD | 0.00034881375 |
| 576 | Substructure Similarity Search in Graph Databases | 2005 | SIGMOD | 0.00019858777 |
| 993 | D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data | 2003 | SIGMOD | 0.00014759406 |
| 2,448 | Multi-Dimensional Regression Analysis of Time-Series Data Streams | 2002 | VLDB | 8.7935134e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,139 | An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis] | 2026 | SIGMOD | 4.1905499e-05 |
| 2,958 | Computing Label-Constraint Reachability in Graph Databases | 2010 | SIGMOD | 7.8126329e-05 |
| 3,864 | A Partition-Based Approach to Structure Similarity Search | 2014 | VLDB | 6.6813849e-05 |
| 6,386 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.0820608e-05 |
| 6,870 | Updating Graph Indices with a One-Pass Algorithm | 2015 | SIGMOD | 4.8974284e-05 |
| 202 | Graph Indexing: A Frequent Structure-based Approach | 2004 | SIGMOD | 0.00034881375 |
| 2,524 | Connected Substructure Similarity Search | 2010 | SIGMOD | 8.5993622e-05 |
| 3,894 | Performance and Scalability of Indexed Subgraph Query Processing Methods | 2015 | VLDB | 6.6531173e-05 |
| 9,552 | Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs | 2025 | SIGMOD | 4.3212967e-05 |
| 895 | Graph Indexing: Tree + Delta >= Graph | 2007 | VLDB | 0.00015498104 |