Probabilistic Optimization of Top N Queries

Summary: Probabilistic Top-N optimization adds a probabilistic filter to prune results, risking a restart if too few answers remain. A cost-based framework quantifies restart risk and minimizes overall cost; experiments show Top-N time savings with modest overhead. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8587
Venue: VLDB
Year: 1999
Pagerank: 8.5540341e-05
Overall Rank: 2,552 | 82.27%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Donko Donjerkovic
2. Raghu Ramakrishnan

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
1,773	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010600438
1,805	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010479371
2,249	Rank-aware Query Optimization	2004	SIGMOD	9.1956569e-05
2,359	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.967267e-05
2,604	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.4628537e-05
2,664	Relaxed Currency and Consistency: How to Say "Good Enough" in SQL	2004	SIGMOD	8.3519232e-05
3,809	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.7413981e-05
5,547	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.4452585e-05
5,578	CliffGuard: A Principled Framework for Finding Robust Database Designs	2015	SIGMOD	5.4231783e-05
6,496	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0327729e-05
6,656	Supporting Ranking and Clustering as Generalized Order-By and Group-By	2007	SIGMOD	4.9691233e-05
7,133	Anytime Measures for Top-k Algorithms	2007	VLDB	4.8175888e-05
7,134	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	4.8174665e-05
7,236	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	4.7877732e-05
7,811	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	4.6411275e-05
7,966	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.6089395e-05
8,868	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	4.4278388e-05
11,222	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
439	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023183237
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
5,660	Query Refinement for Diverse Top-k Selection	2024	SIGMOD	5.3859487e-05
12,119	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1905499e-05
8,883	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	4.4247207e-05
1,996	Probabilistic Ranking of Database Query Results	2004	VLDB	9.8374939e-05
802	Evaluating Top-k Selection Queries	1999	VLDB	0.00016440813
3,547	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD	6.9810773e-05
7,625	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	4.6888879e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415