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.5503022e-05
Overall Rank: 2,377 | 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.00011892544
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,971	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.3302434e-05
6,647	Mining and Indexing Graphs for Supergraph Search	2013	VLDB	5.7211358e-05
6,767	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.6860336e-05
9,847	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1206606e-05
12,101	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB	4.9769913e-05
12,456	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB	4.9769913e-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.0004311045
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
601	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00015725619
1,024	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012426975
2,210	Multi-Dimensional Regression Analysis of Time-Series Data Streams	2002	VLDB	8.8340718e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,628	An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis]	2026	SIGMOD
2	2,535	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
3	3,570	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
4	6,647	Mining and Indexing Graphs for Supergraph Search	2013	VLDB
5	6,767	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,651	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD
10	737	Graph Indexing: Tree + Delta >= Graph	2007	VLDB