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.5490881e-05
Overall Rank
7,339 | 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.6827339e-05
6,545 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7515992e-05
7,752 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4595236e-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.0010679641
38 DISCOVER: Keyword Search in Relational Databases 2002 VLDB 0.00047394041
50 DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases 1997 VLDB 0.00043130126
81 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00036346781
172 Combining Fuzzy Information from Multiple Systems 1996 PODS 0.00026835705
178 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00026628894
290 ObjectRank: Authority-Based Keyword Search in Databases 2004 VLDB 0.00021955068
293 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021943678
410 XSEarch: A Semantic Search Engine for XML 2003 VLDB 0.00018778082
507 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017101297
524 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00016909926
740 Covering Indexes for Branching Path Queries 2002 SIGMOD 0.00014325275
921 APEX: An Adaptive Path Index for XML Data 2002 SIGMOD 0.00013069413
961 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001282305
1,096 Minimization of Tree Pattern Queries 2001 SIGMOD 0.00012050482
1,554 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010270419
2,181 Probabilistic Optimization of Top N Queries 1999 VLDB 8.9082736e-05
3,782 Supporting Ad-hoc Ranking Aggregates 2006 SIGMOD 7.0230959e-05
4,200 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.7395481e-05
7,002 FICSR: Feedback-based InConSistency Resolution and Query Processing on Misaligned Data Sources 2007 SIGMOD 5.624639e-05
7,497 Boolean + Ranking: Querying a Database by K-Constrained Optimization 2006 SIGMOD 5.5089205e-05
7,920 AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering 2006 VLDB 5.4264214e-05
7,995 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 5.4111901e-05
13,213 A Multi-Similarity Algebra 1998 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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