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: 8586
Venue: VLDB
Year: 1999
Pagerank: 8.5465733e-05
Overall Rank: 2,556 | 82.22%
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.00027378328
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
1,784	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010567363
1,808	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010486213
2,356	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.9620762e-05
2,393	Rank-aware Query Optimization	2004	SIGMOD	8.9016542e-05
2,599	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.4702307e-05
2,660	Relaxed Currency and Consistency: How to Say "Good Enough" in SQL	2004	SIGMOD	8.3603587e-05
3,807	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.747576e-05
5,539	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.4503121e-05
5,581	CliffGuard: A Principled Framework for Finding Robust Database Designs	2015	SIGMOD	5.424205e-05
6,500	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.0381573e-05
6,653	Supporting Ranking and Clustering as Generalized Order-By and Group-By	2007	SIGMOD	4.9735307e-05
7,135	Anytime Measures for Top-k Algorithms	2007	VLDB	4.8221884e-05
7,136	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	4.8220711e-05
7,240	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	4.792172e-05
7,806	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	4.6459438e-05
7,963	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.613363e-05
8,868	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	4.4320869e-05
11,220	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.1945683e-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
438	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023199245
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
12,111	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1945683e-05
8,882	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	4.4289641e-05
5,649	Query Refinement for Diverse Top-k Selection	2024	SIGMOD	5.3911246e-05
1,992	Probabilistic Ranking of Database Query Results	2004	VLDB	9.8462684e-05
805	Evaluating Top-k Selection Queries	1999	VLDB	0.00016437265
3,549	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD	6.9858057e-05
7,623	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB	4.6933659e-05
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057857292