Optimal Enumeration: Efficient Top-k Tree Matching

Summary: Lawler-based optimal enumeration for top-k tree pattern matching in directed graphs. Per-round O(n_T+log k); top-1 in O(m_R); total O(m_R + k(n_T+log k)); introduces a priority-based access method and extends to general graph-pattern matching with orders-of-magnitude speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11165
Venue: VLDB
Year: 2015
Pagerank: 4.6583829e-05
Overall Rank: 7,762 | 46.01%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
240	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031603463
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023598882
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234
764	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017018712
919	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015343179
1,414	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012118275
1,823	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010413508
2,248	The Complexity of XPath Query Evaluation	2003	PODS	9.2038466e-05
2,409	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.8776858e-05
2,938	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	7.8524059e-05
4,143	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.4129418e-05
4,807	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9092289e-05
7,240	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	4.792172e-05
7,584	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	4.7041255e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,521	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.6065919e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
6,208	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.1568586e-05
8,505	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.4958064e-05
2,409	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.8776858e-05
10,959	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD	4.1945683e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
4,807	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9092289e-05
4,143	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.4129418e-05