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: 8777
Venue: VLDB
Year: 1999
Pagerank: 9.0821709e-05
Overall Rank: 2,149 | 85.26%
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
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
1,513	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010530872
1,519	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010513777
1,759	Rank-aware Query Optimization	2004	SIGMOD	9.8160244e-05
1,936	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.4557372e-05
2,359	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.698016e-05
2,770	Relaxed Currency and Consistency: How to Say "Good Enough" in SQL	2004	SIGMOD	8.1458395e-05
3,706	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.1819534e-05
5,222	CliffGuard: A Principled Framework for Finding Robust Database Designs	2015	SIGMOD	6.3103741e-05
5,863	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	6.0626421e-05
6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.8809448e-05
6,815	Supporting Ranking and Clustering as Generalized Order-By and Group-By	2007	SIGMOD	5.7652375e-05
7,177	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	5.6806091e-05
7,185	Anytime Measures for Top-k Algorithms	2007	VLDB	5.6779179e-05
7,202	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.6755422e-05
8,147	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.4788421e-05
8,281	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	5.4574671e-05
9,026	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.3295983e-05
11,421	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	5.093636e-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	434	Query Optimization for Parallel Execution	1992	SIGMOD
2	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
3	6,389	Query Refinement for Diverse Top-k Selection	2024	SIGMOD
4	9,044	Threshold Query Optimization for Uncertain Data	2010	SIGMOD
5	12,308	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
6	1,844	Probabilistic Ranking of Database Query Results	2004	VLDB
7	635	Evaluating Top-k Selection Queries	1999	VLDB
8	3,698	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD
9	7,711	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
10	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB