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
haab4be1d8edb917c
Venue
VLDB
Year
2015
Pagerank
5.4391973e-05
Overall Rank
7,769 | 47.93%
DOI
10.14778/2735479.2735486
PDF
Download (CC BY-NC-ND 3.0)

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,602 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2157154e-05
4,730 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4313418e-05
5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.0883761e-05
6,557 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7298671e-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.0010688884
180 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00026534482
192 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025740385
439 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018247958
456 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00017946233
485 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017479773
547 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016545689
786 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00013979657
1,148 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00011777466
1,577 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010155939
2,195 The Complexity of XPath Query Evaluation 2003 PODS 8.8817263e-05
2,705 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.0936619e-05
2,782 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 8.0054142e-05
3,992 Diversified Top-k Graph Pattern Matching 2013 VLDB 6.8567907e-05
4,307 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.6581902e-05
7,362 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.5281595e-05
7,793 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 5.4352151e-05
Previous Page 1 / 1 Next

Semantically Similar Papers