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: 11166
Venue: VLDB
Year: 2015
Pagerank: 4.6543114e-05
Overall Rank: 7,761 | 46.07%
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,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
5,963	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2485815e-05
7,165	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.807833e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023592024
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
616	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00019068362
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
916	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015326675
1,419	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012072488
1,822	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010404349
2,250	The Complexity of XPath Query Evaluation	2003	PODS	9.1949563e-05
2,402	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.87387e-05
2,943	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	7.8463193e-05
4,143	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.4096394e-05
4,748	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9432853e-05
7,236	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	4.7877732e-05
7,588	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	4.6996269e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
2,527	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.5982912e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
6,207	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD	5.1519085e-05
8,504	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.491551e-05
2,402	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.87387e-05
10,962	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD	4.1905499e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
4,748	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9432853e-05
4,143	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.4096394e-05