Towards Graph Containment Search and Indexing

Summary: Studies reverse containment search—retrieving g where q contains g—and its distinct indexing requirements. cIndex selects redundancy-aware contrast subgraphs (NP-hard; greedy 1−1/e), extending to hierarchical indexes with near-optimal pruning. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: ha21171985db21642
Venue: VLDB
Year: 2007
Pagerank: 8.5543073e-05
Overall Rank: 2,376 | 84.03%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Chen Chen (University of Illinois Urbana-Champaign)
2. Xifeng Yan (IBM)
3. Philip S. Yu (IBM)
4. Jiawei Han (University of Illinois Urbana-Champaign)
5. Dong-Qing Zhang (Thomson Research)
6. Xiaohui Gu (IBM)

BibTeX Citation

@article{chen_vldb07,
        title = {{Towards Graph Containment Search and Indexing}},
        author = {Chen, Chen and Yan, Xifeng and Yu, Philip S. and Han, Jiawei and Zhang, Dong-Qing and Gu, Xiaohui},
        journal = {PVLDB},
        series = {{VLDB} '07},
        pages = {926--937},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011898162
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,969	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.3332415e-05
6,642	Mining and Indexing Graphs for Supergraph Search	2013	VLDB	5.7238453e-05
6,760	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.6887265e-05
9,840	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1230858e-05
12,095	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB	4.9793485e-05
12,450	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB	4.9793485e-05

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
50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00043130126
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
601	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00015732701
1,023	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012432693
2,208	Multi-Dimensional Regression Analysis of Time-Series Data Streams	2002	VLDB	8.8382452e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,617	An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis]	2026	SIGMOD
2	2,534	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
3	3,569	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
4	6,642	Mining and Indexing Graphs for Supergraph Search	2013	VLDB
5	6,760	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD
6	176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
7	3,369	Connected Substructure Similarity Search	2010	SIGMOD
8	3,506	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB
9	8,644	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD
10	736	Graph Indexing: Tree + Delta >= Graph	2007	VLDB