DBScholar

Back to papers

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
11353
Venue
VLDB
Year
2015
Pagerank
5.5720259e-05
Overall Rank
7,664 | 47.42%
DOI
10.14778/2735479.2735486

Incoming Non-self Citations Over Time

Authors

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.

Rank Cited Paper Year Venue Pagerank
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010828372
175 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00027226333
195 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025813775
431 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018577017
444 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00018350865
485 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017717377
546 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016734556
776 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014110016
1,128 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.0001206219
1,553 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.0001037809
2,132 The Complexity of XPath Query Evaluation 2003 PODS 9.119436e-05
2,650 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.2920414e-05
2,718 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 8.209788e-05
3,908 Diversified Top-k Graph Pattern Matching 2013 VLDB 7.0262215e-05
4,221 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.8233111e-05
7,202 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.6755422e-05
7,622 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 5.5806644e-05
Previous Page 1 / 1 Next

Semantically Similar Papers