DBScholar

Back to papers

Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs

Summary: Shows structured top-k twig queries on weighted graphs remain NP-hard and violate monotonicity required by ranked joins. Introduces sum-max monotonicity and the horizon-based, self-punctuating HR-Join operator for efficient ranked subresult merging. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
9794
Venue
VLDB
Year
2007
Pagerank
5.6755422e-05
Overall Rank
7,202 | 50.59%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{qi_vldb07,
        title = {{Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs}},
        author = {Qi, Yan and Candan, K. Selcuk and Sapino, Maria Luisa},
        journal = {PVLDB},
        series = {{VLDB} '07},
        pages = {507--518},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank Citing Paper Year Venue Pagerank
4,221 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.8233111e-05
6,412 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.8836116e-05
7,664 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.5720259e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 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
37 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00048017193
48 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.00044033592
77 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00037048607
170 Combining Fuzzy Information from Multiple Systems 1996 PODS 0.00027376361
175 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00027226333
285 ObjectRank: Authority-Based Keyword Search in Databases 2004 VLDB 0.00022365284
302 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021963347
399 XSEarch: A Semantic Search Engine for XML 2003 VLDB 0.00019177959
499 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017431827
509 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00017220967
718 Covering Indexes for Branching Path Queries 2002 SIGMOD 0.00014642961
897 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00013339862
973 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012874284
1,068 Minimization of Tree Pattern Queries 2001 SIGMOD 0.00012326498
1,523 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010502089
2,149 Probabilistic Optimization of Top N Queries 1999 VLDB 9.0821709e-05
3,706 Supporting Ad-hoc Ranking Aggregates 2006 SIGMOD 7.1819534e-05
4,113 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.8941988e-05
6,856 FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources 2007 SIGMOD 5.7530103e-05
7,352 Boolean + Ranking: Querying a Database by K-Constrained Optimization 2006 SIGMOD 5.6353412e-05
7,786 AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering 2006 VLDB 5.5449897e-05
7,836 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 5.5353696e-05
12,923 A Multi-Similarity Algebra 1998 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,759 Rank-aware Query Optimization 2004 SIGMOD
2 2,678 Weighted Hypertree Decompositions and Optimal Query Plans 2004 PODS
3 6,412 Ranked Enumeration of Join Queries with Projections 2022 VLDB
4 3,500 Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions 2007 SIGMOD
5 12,308 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD
6 2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB
7 7,286 Efficient Computation of Quantiles over Joins 2023 PODS
8 9,730 Fast Optimal Twig Joins 2010 VLDB
9 2,585 Evaluating Rank Joins with Optimal Cost 2008 PODS
10 7,550 Processing Top-k Join Queries 2010 VLDB