Diversified Top-k Graph Pattern Matching

Summary: Recasts simulation-based graph pattern matching as top-k retrieval for a designated output node, avoiding full match enumeration via early-terminating relevance-ranked algorithms. For diversified ranking, proves NP-completeness and provides a guaranteed approximation and early-terminating heuristic. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hfeed181b26cde2d4
Venue: VLDB
Year: 2013
Pagerank: 6.8802947e-05
Overall Rank: 3,979 | 73.25%
DOI: 10.14778/2536258.2536263

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; University of Edinburgh)
2. Xin Wang (University of Edinburgh)
3. Yinghui Wu (University of California Santa Barbara)

BibTeX Citation

@article{fan_vldb13,
        title = {{Diversified Top-k Graph Pattern Matching}},
        author = {Fan, Wenfei and Wang, Xin and Wu, Yinghui},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {13},
        pages = {1510--1521},
        doi = {10.14778/2536258.2536263},
        url = {https://doi.org/10.14778/2536258.2536263},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
960	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012836554
4,729	Interactive Summarization and Exploration of Top Aggregate Query Answers	2018	VLDB	6.4470592e-05
5,477	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.1155396e-05
7,752	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.4595236e-05
9,030	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	5.2340466e-05
9,296	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	5.1991444e-05
10,186	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0651993e-05
10,232	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	5.0568888e-05
10,513	Towards Selecting Informative Alternative Relational Query Plans for Database Education	2026	SIGMOD	4.9793485e-05
11,053	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.9793485e-05
11,432	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.9793485e-05
12,059	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.9793485e-05
12,154	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
81	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00036346781
1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011809728
1,476	Diversifying Top-K Results	2012	VLDB	0.00010551487
1,936	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	9.3387282e-05
2,262	Identifying Meaningful Return Information for XML Keyword Search	2007	SIGMOD	8.7333724e-05
4,291	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.6827339e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,291	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD
2	5,605	Capturing Topology in Graph Pattern Matching	2012	VLDB
3	5,277	Top-K Structural Diversity Search in Large Networks	2013	VLDB
4	1,317	Incremental Graph Pattern Matching	2011	SIGMOD
5	12,059	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
6	7,752	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB
7	12,065	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD
8	1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
9	5,477	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
10	11,053	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB