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.0691578e-05
Overall Rank
10,157 | 31.74%
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,483 PG-Schema: Schemas for Property Graphs 2023 SIGMOD 0.00010533714
5,559 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.082972e-05
9,185 Towards Theory for Real-World Data 2022 PODS 5.2102846e-05
9,371 Exploring Exploratory Querying 2025 VLDB 5.1843659e-05
11,532 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9769913e-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.0010679903
57 On Random Sampling over Joins 1999 SIGMOD 0.00040095727
73 Including Group-By in Query Optimization 1994 VLDB 0.0003750677
213 Eager Aggregation and Lazy Aggregation 1995 VLDB 0.00024753576
345 R* Optimizer Validation and Performance Evaluation for Distributed Queries 1986 VLDB 0.0002045459
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020013731
396 On Saying "Enough Already!" in SQL 1997 SIGMOD 0.00019153354
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
540 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.0001671863
795 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013934719
813 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013722638
849 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013498306
962 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012818013
1,216 Overview of Data Exploration Techniques 2015 SIGMOD 0.00011487268
1,570 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.0001020376
2,593 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2429717e-05
3,075 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 7.6742518e-05
5,233 Robust and Efficient Algorithms for Rank Join Evaluation 2009 SIGMOD 6.2167391e-05
5,492 Compressed Representations of Conjunctive Query Results 2018 PODS 6.1066968e-05
5,602 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.0678238e-05
8,986 Adding Counting Quantifiers to Graph Patterns 2016 SIGMOD 5.2427213e-05
10,242 SHARQL: Shape Analysis of Recursive SPARQL Queries 2020 SIGMOD 5.0519762e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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