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 |
|---|---|---|---|---|
| 951 | Comparing Stars: On Approximating Graph Edit Distance | 2009 | VLDB | 0.00015106325 |
| 2,409 | TreeSpan: Efficiently Computing Similarity All-Matching | 2012 | SIGMOD | 8.8776858e-05 |
| 2,525 | Connected Substructure Similarity Search | 2010 | SIGMOD | 8.5981082e-05 |
| 4,072 | Performance and Scalability of Indexed Subgraph Query Processing Methods | 2015 | VLDB | 6.4727847e-05 |
| 4,958 | Efficient Subgraph Search over Large Uncertain Graphs | 2011 | VLDB | 5.8031038e-05 |
| 6,406 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.0765917e-05 |
| 6,801 | Updating Graph Indices with a One-Pass Algorithm | 2015 | SIGMOD | 4.9226813e-05 |
| 9,580 | ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs | 2020 | VLDB | 4.3234342e-05 |
| 11,598 | IDAR: Fast Supergraph Search Using DAG Integration | 2020 | VLDB | 4.1945683e-05 |
| 11,961 | Leveraging Graph Dimensions in Online Graph Search | 2015 | VLDB | 4.1945683e-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.00064329285 |
| 171 | Algorithmics and Applications of Tree and Graph Searching | 2002 | PODS | 0.00038830709 |
| 203 | Graph Indexing: A Frequent Structure-based Approach | 2004 | SIGMOD | 0.00034889335 |
| 572 | Substructure Similarity Search in Graph Databases | 2005 | SIGMOD | 0.00019887011 |
| 993 | D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data | 2003 | SIGMOD | 0.00014765816 |
| 2,448 | Multi-Dimensional Regression Analysis of Time-Series Data Streams | 2002 | VLDB | 8.8032353e-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.1945683e-05 |
| 2,957 | Computing Label-Constraint Reachability in Graph Databases | 2010 | SIGMOD | 7.8198686e-05 |
| 3,862 | A Partition-Based Approach to Structure Similarity Search | 2014 | VLDB | 6.687769e-05 |
| 6,406 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.0765917e-05 |
| 6,801 | Updating Graph Indices with a One-Pass Algorithm | 2015 | SIGMOD | 4.9226813e-05 |
| 203 | Graph Indexing: A Frequent Structure-based Approach | 2004 | SIGMOD | 0.00034889335 |
| 2,525 | Connected Substructure Similarity Search | 2010 | SIGMOD | 8.5981082e-05 |
| 4,072 | Performance and Scalability of Indexed Subgraph Query Processing Methods | 2015 | VLDB | 6.4727847e-05 |
| 9,552 | Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs | 2025 | SIGMOD | 4.3254416e-05 |
| 900 | Graph Indexing: Tree + Delta >= Graph | 2007 | VLDB | 0.00015495155 |