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.8828694e-05
Overall Rank: 2,193 | 85.31%
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
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016221103
1,447	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010604169
1,539	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010292787
1,712	Rank-aware Query Optimization	2004	SIGMOD	9.7961248e-05
1,935	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3407959e-05
2,406	Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? *	2005	CIDR	8.4962449e-05
2,839	Relaxed Currency and Consistency: How to Say "Good Enough" in SQL	2004	SIGMOD	7.9381931e-05
3,793	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.9967739e-05
5,324	CliffGuard: A Principled Framework for Finding Robust Database Designs	2015	SIGMOD	6.1645235e-05
5,994	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.9045522e-05
6,552	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7306642e-05
6,970	Supporting Ranking and Clustering as Generalized Order-By and Group-By	2007	SIGMOD	5.6152718e-05
7,342	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB	5.5329816e-05
7,348	Anytime Measures for Top-k Algorithms	2007	VLDB	5.5302579e-05
7,362	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5281595e-05
8,337	Adaptive Execution of Variable-Accuracy Functions	2006	VLDB	5.3357365e-05
8,473	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	5.3148581e-05
9,227	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.1903311e-05
11,785	Lightweight Materialization for Fast Dashboards Over Joins	2023	SIGMOD	4.9605343e-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	448	Query Optimization for Parallel Execution	1992	SIGMOD
2	568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
3	6,534	Query Refinement for Diverse Top-k Selection	2024	SIGMOD
4	12,648	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
5	9,248	Threshold Query Optimization for Uncertain Data	2010	SIGMOD
6	1,897	Probabilistic Ranking of Database Query Results	2004	VLDB
7	647	Evaluating Top-k Selection Queries	1999	VLDB
8	3,776	Optimizing MPF Queries: Decision Support and Probabilistic Inference	2007	SIGMOD
9	7,886	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
10	51	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB