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: 9833
Venue: VLDB
Year: 2007
Pagerank: 8.745748e-05
Overall Rank: 2,328 | 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,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00012117375
2,650	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.2920414e-05
3,311	Connected Substructure Similarity Search	2010	SIGMOD	7.5353184e-05
3,477	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	7.3791229e-05
4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.4780097e-05
6,520	Mining and Indexing Graphs for Supergraph Search	2013	VLDB	5.8535203e-05
6,631	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.8190404e-05
9,665	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.2406724e-05
11,793	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB	5.093636e-05
12,159	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB	5.093636e-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
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026138589
591	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.0001603683
1,008	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012688008
2,171	Multi-Dimensional Regression Analysis of Time-Series Data Streams	2002	VLDB	9.0406168e-05

Semantically Similar Papers

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