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.052396e-05
Overall Rank
10,192 | 31.69%
DOI
10.14778/3510397.3510407
PDF
Download (CC BY-NC-ND 4.0)

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,484 PG-Schema: Schemas for Property Graphs 2023 SIGMOD 0.00010498883
5,574 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.0628579e-05
9,210 Towards Theory for Real-World Data 2022 PODS 5.1930561e-05
9,397 Exploring Exploratory Querying 2025 VLDB 5.1672232e-05
11,581 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9605343e-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.0010688884
57 On Random Sampling over Joins 1999 SIGMOD 0.0003999751
73 Including Group-By in Query Optimization 1994 VLDB 0.00037420958
213 Eager Aggregation and Lazy Aggregation 1995 VLDB 0.00024695393
345 R* Optimizer Validation and Performance Evaluation for Distributed Queries 1986 VLDB 0.00020445813
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020048899
398 On Saying "Enough Already!" in SQL 1997 SIGMOD 0.00019117739
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
536 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.00016738841
793 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013903938
815 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013682594
848 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013463236
941 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012938573
1,220 Overview of Data Exploration Techniques 2015 SIGMOD 0.00011449992
1,568 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.00010178045
2,602 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2157154e-05
3,081 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 7.6515625e-05
5,254 Robust and Efficient Algorithms for Rank Join Evaluation 2009 SIGMOD 6.1964074e-05
5,512 Compressed Representations of Conjunctive Query Results 2018 PODS 6.0867282e-05
5,613 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.048773e-05
9,006 Adding Counting Quantifiers to Graph Patterns 2016 SIGMOD 5.2253856e-05
10,274 SHARQL: Shape Analysis of Recursive SPARQL Queries 2020 SIGMOD 5.0352713e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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