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.9082736e-05
Overall Rank: 2,181 | 85.34%
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.00022981861
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016245271
1,439	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010642846
1,535	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010331242
1,773	Rank-aware Query Optimization	2004	SIGMOD	9.6719067e-05
1,929	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3546057e-05
2,396	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.5278724e-05
2,826	Relaxed Currency and Consistency: How to Say "Good Enough" in SQL	2004	SIGMOD	7.9678605e-05
3,782	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.0230959e-05
5,316	CliffGuard: A Principled Framework for Finding Robust Database Designs	2015	SIGMOD	6.1836681e-05
5,983	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.926918e-05
6,540	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7523628e-05
6,949	Supporting Ranking and Clustering as Generalized Order-By and Group-By	2007	SIGMOD	5.6365631e-05
7,320	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	5.5538431e-05
7,327	Anytime Measures for Top-k Algorithms	2007	VLDB	5.5512161e-05
7,339	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5490881e-05
8,317	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.3559621e-05
8,449	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	5.3350162e-05
9,195	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.2100166e-05
11,735	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.9793485e-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	6,520	Query Refinement for Diverse Top-k Selection	2024	SIGMOD
4	9,214	Threshold Query Optimization for Uncertain Data	2010	SIGMOD
5	12,599	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
6	1,886	Probabilistic Ranking of Database Query Results	2004	VLDB
7	643	Evaluating Top-k Selection Queries	1999	VLDB
8	3,769	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD
9	7,863	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
10	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB