Optimal Enumeration: Efficient Top-k Tree Matching

Summary: Introduces a Lawler-based top-k twig/tree matching algorithm with optimal O(nT + log k) delay and optimal O(mR) top-1 cost. Priority-based edge access and extension to graph queries yield orders-of-magnitude gains over prior methods. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: haab4be1d8edb917c
Venue: VLDB
Year: 2015
Pagerank: 5.4595236e-05
Overall Rank: 7,752 | 47.89%
DOI: 10.14778/2735479.2735486

Incoming Non-self Citations Over Time

Authors

1. Lijun Chang (University of New South Wales)
2. Xuemin Lin (East China Normal University; University of New South Wales)
3. Wenjie Zhang (University of New South Wales)
4. Jeffrey Xu Yu (Chinese University of Hong Kong)
5. Ying Zhang (University of Technology Sydney)
6. Lu Qin (University of Technology Sydney)

BibTeX Citation

@article{chang_vldb15,
        title = {{Optimal Enumeration: Efficient Top-k Tree Matching}},
        author = {Chang, Lijun and Lin, Xuemin and Zhang, Wenjie and Yu, Jeffrey Xu and Zhang, Ying and Qin, Lu},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {5},
        doi = {10.14778/2735479.2735486},
        url = {https://doi.org/10.14778/2735479.2735486},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2468757e-05
4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.434561e-05
5,482	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.111411e-05
6,545	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.7515992e-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
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026628894
197	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025584127
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018286607
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017972038
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016607433
783	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014021799
1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011809728
1,585	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010163696
2,177	The Complexity of XPath Query Evaluation	2003	PODS	8.9153711e-05
2,702	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.1177147e-05
2,773	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0351713e-05
3,979	Diversified Top-k Graph Pattern Matching	2013	VLDB	6.8802947e-05
4,291	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.6827339e-05
7,339	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5490881e-05
7,768	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.4558207e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,320	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD
2	2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
3	6,045	PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration	2021	SIGMOD
4	8,662	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
5	10,788	Subgraph Enumeration: Beyond Tree Decomposition	2026	VLDB
6	2,702	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD
7	11,518	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD
8	5,477	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
9	3,979	Diversified Top-k Graph Pattern Matching	2013	VLDB
10	4,291	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD