Probabilistic Optimization of Top N Queries

Summary: Introduces probabilistic optimization for Top-N queries by selecting aggressive predicates that prune low-ranked results while modeling the probability and cost of insufficient answers and execution restarts. Experiments show lower average runtime for modest optimization overhead. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hcfdb2d78a29bc0ce
Venue: VLDB
Year: 1999
Pagerank: 8.9044171e-05
Overall Rank: 2,183 | 85.33%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Donko Donjerkovic (University of Wisconsin)
2. Raghu Ramakrishnan (University of Wisconsin)

BibTeX Citation

@article{donjerkovic_vldb99,
        title = {{Probabilistic Optimization of Top N Queries}},
        author = {Donjerkovic, Donko and Ramakrishnan, Raghu},
        journal = {PVLDB},
        series = {{VLDB} '99},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
255	The History of Histograms (abridged)	2003	VLDB	0.00022974524
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016244162
1,441	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010638056
1,535	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010326646
1,773	Rank-aware Query Optimization	2004	SIGMOD	9.6683429e-05
1,931	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3511556e-05
2,397	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.5238625e-05
2,826	Relaxed Currency and Consistency: How to Say "Good Enough" in SQL	2004	SIGMOD	7.9641044e-05
3,784	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.0197908e-05
5,310	CliffGuard: A Principled Framework for Finding Robust Database Designs	2015	SIGMOD	6.184026e-05
5,983	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.9241225e-05
6,542	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7496415e-05
6,952	Supporting Ranking and Clustering as Generalized Order-By and Group-By	2007	SIGMOD	5.6338956e-05
7,324	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	5.5512232e-05
7,329	Anytime Measures for Top-k Algorithms	2007	VLDB	5.5485926e-05
7,342	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5464639e-05
8,322	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.3534332e-05
8,458	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	5.3324907e-05
9,204	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.2075502e-05
11,741	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.9769913e-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
1	446	Query Optimization for Parallel Execution	1992	SIGMOD
2	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
3	12,605	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
4	6,522	Query Refinement for Diverse Top-k Selection	2024	SIGMOD
5	9,224	Threshold Query Optimization for Uncertain Data	2010	SIGMOD
6	1,887	Probabilistic Ranking of Database Query Results	2004	VLDB
7	643	Evaluating Top-k Selection Queries	1999	VLDB
8	3,771	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD
9	7,868	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
10	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB