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.5281595e-05
Overall Rank
7,362 | 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,307 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.6581902e-05
6,557 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7298671e-05
7,769 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4391973e-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.0010688884
38 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00047300197
50 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.00042977538
81 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00036224963
170 Combining Fuzzy Information from Multiple Systems 1996 PODS 0.0002707332
180 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00026534482
292 ObjectRank: Authority-Based Keyword Search in Databases 2004 VLDB 0.00021888861
294 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021884041
412 XSEarch: A Semantic Search Engine for XML 2003 VLDB 0.00018712693
505 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00017162373
511 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017061618
744 Covering Indexes for Branching Path Queries 2002 SIGMOD 0.00014275788
926 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00013025014
941 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012938573
1,100 Minimization of Tree Pattern Queries 2001 SIGMOD 0.00012005004
1,555 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.0001023212
2,193 Probabilistic Optimization of Top N Queries 1999 VLDB 8.8828694e-05
3,793 Supporting Ad-hoc Ranking Aggregates 2006 SIGMOD 6.9967739e-05
4,219 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.7141046e-05
7,022 FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources 2007 SIGMOD 5.6035207e-05
7,521 Boolean + Ranking: Querying a Database by K-Constrained Optimization 2006 SIGMOD 5.4881075e-05
7,937 AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering 2006 VLDB 5.4060062e-05
8,017 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 5.390745e-05
13,260 A Multi-Similarity Algebra 1998 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,080 Distributed Evaluation of Top-k Temporal Joins 2016 SIGMOD
2 2,739 Weighted Hypertree Decompositions and Optimal Query Plans 2004 PODS
3 6,557 Ranked Enumeration of Join Queries with Projections 2022 VLDB
4 3,578 Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions 2007 SIGMOD
5 12,648 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD
6 2,602 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB
7 7,459 Efficient Computation of Quantiles over Joins 2023 PODS
8 9,943 Fast Optimal Twig Joins 2010 VLDB
9 2,625 Evaluating Rank Joins with Optimal Cost 2008 PODS
10 7,637 Processing Top-k Join Queries 2010 VLDB