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: 12623
Venue: VLDB
Year: 2022
Pagerank: 4.2777144e-05
Overall Rank: 9,801 | 31.89%
DOI: 10.14778/3510397.3510407

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,782	PG-Schema: Schemas for Property Graphs	2023	SIGMOD	0.00010557905
5,527	Representing Paths in Graph Database Pattern Matching	2023	VLDB	5.4573655e-05
8,947	Towards Theory for Real-World Data	2022	PODS	4.4216375e-05
10,864	Exploring Exploratory Querying	2025	VLDB	4.1905499e-05
10,973	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
51	Including Group-By in Query Optimization	1994	VLDB	0.00067060283
196	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00035240105
249	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00030773137
469	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00022397468
551	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310856
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
657	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018581389
673	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018325667
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
1,207	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001327437
1,255	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013011216
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
1,507	Overview of Data Exploration Techniques	2015	SIGMOD	0.00011594294
2,173	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3767985e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
3,923	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	6.6232068e-05
5,076	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	5.709895e-05
5,379	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5375923e-05
8,786	Adding Counting Quantifiers to Graph Patterns	2016	SIGMOD	4.4467423e-05
9,888	SHARQL: Shape Analysis of Recursive SPARQL Queries	2020	SIGMOD	4.2576366e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,014	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.7982231e-05
7,966	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.6089395e-05
10,510	Relevance Queries for Interval Data	2025	SIGMOD	4.1905499e-05
2,316	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0513688e-05
8,883	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	4.4247207e-05
12,119	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1905499e-05
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
11,863	Range Thresholding on Streams	2016	SIGMOD	4.1905499e-05
1,805	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010479371
8,042	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	4.5956381e-05