DBScholar

Back to papers

Threshold Queries in Theory and in the Wild

Summary: Threshold queries (compute/count up to a bound) analyzed theoretically and empirically. They tighten asymptotic bounds for modern query evaluators, and real data show practical relevance where users want results only up to a threshold, independent of ranking. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hff3b5f0b54f94c9e
Venue
VLDB
Year
2022
Pagerank
5.0715586e-05
Overall Rank
10,153 | 31.74%
DOI
10.14778/3510397.3510407

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{bonifati_vldb22,
        title = {{Threshold Queries in Theory and in the Wild}},
        author = {Bonifati, Angela and Dumbrava, Stefania and Fletcher, George and Hidders, Jan and Hofer, Matthias and Martens, Wim and Murlak, Filip and Shinavier, Joshua and Staworko, Sławek and Tomaszuk, Dominik},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {5},
        pages = {1105--1118},
        doi = {10.14778/3510397.3510407},
        url = {https://doi.org/10.14778/3510397.3510407},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
1,482 PG-Schema: Schemas for Property Graphs 2023 SIGMOD 0.00010538703
5,557 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.085853e-05
9,176 Towards Theory for Real-World Data 2022 PODS 5.2127522e-05
9,362 Exploring Exploratory Querying 2025 VLDB 5.1868213e-05
11,526 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 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
57 On Random Sampling over Joins 1999 SIGMOD 0.00040108301
73 Including Group-By in Query Optimization 1994 VLDB 0.00037522101
213 Eager Aggregation and Lazy Aggregation 1995 VLDB 0.00024759805
344 R* Optimizer Validation and Performance Evaluation for Distributed Queries 1986 VLDB 0.00020461727
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020020639
396 On Saying "Enough Already!" in SQL 1997 SIGMOD 0.00019162218
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
540 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016726545
795 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013938779
812 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013729015
849 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013504405
961 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001282305
1,215 Overview of Data Exploration Techniques 2015 SIGMOD 0.00011492648
1,570 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.0001020855
2,591 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2468757e-05
3,073 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 7.6777283e-05
5,229 Robust and Efficient Algorithms for Rank Join Evaluation 2009 SIGMOD 6.2196057e-05
5,489 Compressed Representations of Conjunctive Query Results 2018 PODS 6.1095111e-05
5,601 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.0706976e-05
8,976 Adding Counting Quantifiers to Graph Patterns 2016 SIGMOD 5.2452044e-05
10,236 SHARQL: Shape Analysis of Recursive SPARQL Queries 2020 SIGMOD 5.0543689e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,006 IO-Top-k: Index-access Optimized Top-k Query Processing 2006 VLDB
2 11,194 Relevance Queries for Interval Data 2025 SIGMOD
3 8,449 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB
4 2,104 Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data 2004 VLDB
5 9,214 Threshold Query Optimization for Uncertain Data 2010 SIGMOD
6 12,599 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD
7 1,396 Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach 2008 SIGMOD
8 12,350 Range Thresholding on Streams 2016 SIGMOD
9 1,535 Top-k Query Evaluation with Probabilistic Guarantees 2004 VLDB
10 8,189 Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation 2011 VLDB