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: 5244
Venue: SIGMOD
Year: 2016
Pagerank: 5.2757528e-05
Overall Rank: 5,903 | 58.98%
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
8,163	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5685178e-05
9,106	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	4.3909979e-05
9,726	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	4.2901665e-05
9,847	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	4.2680295e-05
10,320	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1905499e-05
10,852	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	4.1905499e-05
10,855	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.1905499e-05
11,477	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	4.1905499e-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
202	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034881375
351	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026351742
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
502	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021528261
616	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00019068362
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
895	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015498104
1,204	Efficient Diversity-Aware Search	2011	SIGMOD	0.00013316893
1,444	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011941836
1,572	Query Preserving Graph Compression	2012	SIGMOD	0.00011296109
1,630	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011073047
1,984	DisC Diversity: Result Diversification based on Dissimilarity and Coverage	2013	VLDB	9.8645751e-05
2,021	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.7730473e-05
2,172	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	9.37776e-05
2,474	Top-k Bounded Diversification	2012	SIGMOD	8.6956353e-05
2,557	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5484449e-05
4,207	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3519481e-05
4,748	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9432853e-05
5,786	Capturing Topology in Graph Pattern Matching	2012	VLDB	5.3256482e-05
5,871	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	5.2912806e-05
6,870	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	4.8974284e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,959	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.7992713e-05
8,504	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.491551e-05
11,574	Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query	2020	SIGMOD	4.1905499e-05
6,085	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD	5.2165029e-05
4,207	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3519481e-05
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
4,748	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9432853e-05
10,320	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1905499e-05
3,119	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.5393376e-05
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05