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)
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,745 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB | 8.1747954e-05 |
| 5,593 | Beyond Equi-joins: Ranking, Enumeration and Factorization | 2021 | VLDB | 6.1552328e-05 |
| 5,601 | Optimal Join Algorithms Meet Top-k | 2020 | SIGMOD | 6.1540123e-05 |
| 6,412 | Ranked Enumeration of Join Queries with Projections | 2022 | VLDB | 5.8836116e-05 |
Previous
Page 1 / 1
Next
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.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 2,453 | Efficient Algorithms for Maximal k-Biplex Enumeration | 2022 | SIGMOD |
| 2 | 10,419 | A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] | 2026 | SIGMOD |
| 3 | 2,745 | Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries | 2020 | VLDB |
| 4 | 5,938 | PathEnum: Towards Real-Time Hop-Constrained s-t Path Enumeration | 2021 | SIGMOD |
| 5 | 8,493 | Top-K Nearest Keyword Search on Large Graphs | 2013 | VLDB |
| 6 | 2,650 | TreeSpan: Efficiently Computing Similarity All-Matching | 2012 | SIGMOD |
| 7 | 11,173 | Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee | 2024 | SIGMOD |
| 8 | 5,370 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD |
| 9 | 3,908 | Diversified Top-k Graph Pattern Matching | 2013 | VLDB |
| 10 | 4,221 | Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs | 2008 | SIGMOD |