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.4570169e-05
Overall Rank
7,756 | 47.88%
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,593 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2429717e-05
4,745 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4369578e-05
5,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1085184e-05
6,547 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7488764e-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.0010679903
179 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00026617591
197 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025572265
438 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018278591
453 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00017963727
489 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017440023
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016599925
784 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014015324
1,150 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00011804185
1,585 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010158887
2,179 The Complexity of XPath Query Evaluation 2003 PODS 8.9111534e-05
2,701 TreeSpan: Efficiently Computing Similarity All-Matching 2012 SIGMOD 8.114832e-05
2,774 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 8.0313907e-05
3,980 Diversified Top-k Graph Pattern Matching 2013 VLDB 6.87704e-05
4,291 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.6795809e-05
7,342 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.5464639e-05
7,777 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 5.4532403e-05
Previous Page 1 / 1 Next

Semantically Similar Papers