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: 12622
Venue: VLDB
Year: 2022
Pagerank: 4.2818172e-05
Overall Rank: 9,798 | 31.84%
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,785	PG-Schema: Schemas for Property Graphs	2023	SIGMOD	0.00010560236
5,517	Representing Paths in Graph Database Pattern Matching	2023	VLDB	5.4626107e-05
8,943	Towards Theory for Real-World Data	2022	PODS	4.4258797e-05
10,860	Exploring Exploratory Querying	2025	VLDB	4.1945683e-05
10,970	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1945683e-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
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
51	Including Group-By in Query Optimization	1994	VLDB	0.00067123727
196	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00035261496
248	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00030785339
470	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00022393068
552	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310903
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
674	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018327585
690	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.00018099792
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
1,259	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00012995821
1,262	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012986539
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
1,552	Overview of Data Exploration Techniques	2015	SIGMOD	0.00011408814
2,169	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3845975e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
3,922	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	6.6291079e-05
5,077	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	5.7153846e-05
5,373	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5425231e-05
8,866	Adding Counting Quantifiers to Graph Patterns	2016	SIGMOD	4.4323126e-05
9,889	SHARQL: Shape Analysis of Recursive SPARQL Queries	2020	SIGMOD	4.2617199e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,009	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.7977564e-05
10,501	Relevance Queries for Interval Data	2025	SIGMOD	4.1945683e-05
7,963	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.613363e-05
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05
8,882	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	4.4289641e-05
12,111	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1945683e-05
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
11,855	Range Thresholding on Streams	2016	SIGMOD	4.1945683e-05
1,808	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010486213
8,040	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	4.600049e-05