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
12810
Venue
VLDB
Year
2022
Pagerank
5.1879626e-05
Overall Rank
9,961 | 31.66%
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,661 PG-Schema: Schemas for Property Graphs 2023 SIGMOD 0.00010079134
5,418 Representing Paths in Graph Database Pattern Matching 2023 VLDB 6.2255373e-05
9,012 Towards Theory for Real-World Data 2022 PODS 5.3323444e-05
11,084 Exploring Exploratory Querying 2025 VLDB 5.093636e-05
11,183 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 5.093636e-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.0010828372
54 On Random Sampling over Joins 1999 SIGMOD 0.00040810225
71 Including Group-By in Query Optimization 1994 VLDB 0.00038021159
206 Eager Aggregation and Lazy Aggregation 1995 VLDB 0.00025092273
342 R* Optimizer Validation and Performance Evaluation for Distributed Queries 1986 VLDB 0.00020673706
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
380 On Saying "Enough Already!" in SQL 1997 SIGMOD 0.00019563191
499 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017431827
509 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00017220967
530 An Analytical Study of Large SPARQL Query Logs 2018 VLDB 0.0001709169
802 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013907725
816 The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates 2017 SIGMOD 0.00013827772
860 Aggregation and Ordering in Factorised Databases 2013 VLDB 0.00013560445
973 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.00012874284
1,198 Overview of Data Exploration Techniques 2015 SIGMOD 0.00011706307
1,549 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.00010390168
2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.1747954e-05
3,137 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 7.7204167e-05
5,138 Robust and Efficient Algorithms for Rank Join Evaluation 2009 SIGMOD 6.3495536e-05
5,383 Compressed Representations of Conjunctive Query Results 2018 PODS 6.2374576e-05
5,461 HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings 2019 PODS 6.2090515e-05
8,809 Adding Counting Quantifiers to Graph Patterns 2016 SIGMOD 5.3655939e-05
10,043 SHARQL: Shape Analysis of Recursive SPARQL Queries 2020 SIGMOD 5.1703259e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,967 IO-Top-k: Index-access Optimized Top-k Query Processing 2006 VLDB
2 8,281 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB
3 10,776 Relevance Queries for Interval Data 2025 SIGMOD
4 2,062 Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data 2004 VLDB
5 9,044 Threshold Query Optimization for Uncertain Data 2010 SIGMOD
6 12,308 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD
7 1,363 Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach 2008 SIGMOD
8 12,056 Range Thresholding on Streams 2016 SIGMOD
9 1,519 Top-k Query Evaluation with Probabilistic Guarantees 2004 VLDB
10 8,029 Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation 2011 VLDB