Diversified Top-k Subgraph Querying in a Large Graph

Summary: Diversified top-k subgraph querying in large graphs: up to k isomorphic subgraphs maximize coverage. Proposes a level-based algorithm with early termination and a provable approximation; experiments on data show near-optimal results and ~10 ms queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5243
Venue: SIGMOD
Year: 2016
Pagerank: 5.3006473e-05
Overall Rank: 5,854 | 59.28%
DOI: 10.1145/2882903.2915216

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,152	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	5.183145e-05
8,159	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5729025e-05
9,106	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	4.3952103e-05
9,727	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	4.2942813e-05
9,847	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	4.2721228e-05
10,308	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1945683e-05
10,848	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	4.1945683e-05
10,851	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
203	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034889335
350	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026365067
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
764	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017018712
900	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015495155
1,208	Efficient Diversity-Aware Search	2011	SIGMOD	0.00013275712
1,454	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011913289
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
1,635	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001105793
2,000	DisC Diversity: Result Diversification based on Dissimilarity and Coverage	2013	VLDB	9.8229527e-05
2,007	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.8081235e-05
2,162	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	9.3964337e-05
2,480	Top-k Bounded Diversification	2012	SIGMOD	8.6899714e-05
2,551	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5572574e-05
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05
4,807	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9092289e-05
5,776	Capturing Topology in Graph Pattern Matching	2012	VLDB	5.3309758e-05
5,877	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	5.2916612e-05
6,801	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	4.9226813e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,958	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.8031038e-05
8,505	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.4958064e-05
11,570	Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query	2020	SIGMOD	4.1945683e-05
6,080	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD	5.2214553e-05
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05
4,807	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9092289e-05
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
10,308	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1945683e-05
3,187	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.4136521e-05
4,494	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1414196e-05