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
h4b9178b132437582
Venue
VLDB
Year
2007
Pagerank
5.5464639e-05
Overall Rank
7,342 | 50.66%
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,291 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.6795809e-05
6,547 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7488764e-05
7,756 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4570169e-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.0010679903
38 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00047373961
50 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.0004311045
81 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00036330407
172 Combining Fuzzy Information from Multiple Systems 1996 PODS 0.00026824625
179 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00026617591
290 ObjectRank: Authority-Based Keyword Search in Databases 2004 VLDB 0.00021944946
293 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021933539
411 XSEarch: A Semantic Search Engine for XML 2003 VLDB 0.00018769329
507 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017093562
524 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00016902116
741 Covering Indexes for Branching Path Queries 2002 SIGMOD 0.00014318553
922 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.0001306334
962 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012818013
1,096 Minimization of Tree Pattern Queries 2001 SIGMOD 0.00012044781
1,555 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010265572
2,183 Probabilistic Optimization of Top N Queries 1999 VLDB 8.9044171e-05
3,784 Supporting Ad-hoc Ranking Aggregates 2006 SIGMOD 7.0197908e-05
4,201 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.7363634e-05
7,003 FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources 2007 SIGMOD 5.621977e-05
7,502 Boolean + Ranking: Querying a Database by K-Constrained Optimization 2006 SIGMOD 5.5063128e-05
7,924 AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering 2006 VLDB 5.4238547e-05
8,000 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 5.4086285e-05
13,219 A Multi-Similarity Algebra 1998 SIGMOD 4.9769913e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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