Best Position Algorithms for Top-k Queries

Summary: Introduces BPA, which provably never costs more than Threshold Algorithm (TA) and can stop up to m−1 times earlier. BPA2 further reduces sorted-list accesses by roughly m−1×, delivering substantial empirical gains for top-k queries. (summarized by gpt-5.6-luna on Jul 21 2026)

Paper ID: 9793
Venue: VLDB
Year: 2007
Pagerank: 7.1838636e-05
Overall Rank: 3,702 | 74.61%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Reza Akbarinia (INRIA; University of Nantes)
2. Esther Pacitti (INRIA; University of Nantes)
3. Patrick Valduriez (INRIA; University of Nantes)

BibTeX Citation

@article{akbarinia_vldb07,
        title = {{Best Position Algorithms for Top-k Queries}},
        author = {Akbarinia, Reza and Pacitti, Esther and Valduriez, Patrick},
        journal = {PVLDB},
        series = {{VLDB} '07},
        pages = {495--506},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
286	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00022357911
1,589	Manu: A Cloud Native Vector Database Management System	2022	VLDB	0.00010264469
4,514	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	6.6500719e-05
6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.7596335e-05
6,960	DeepEverest: Accelerating Declarative Top-K Queries for Deep Neural Network Interpretation	2022	VLDB	5.7303405e-05
7,299	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.6513289e-05
7,631	On Efficient Top-k Query Processing in Highly Distributed Environments	2008	SIGMOD	5.5780405e-05
11,397	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
827	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013769938
1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00010811133
1,513	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010530872
1,967	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.3804693e-05
2,525	Answering Top-k Queries Using Views	2006	VLDB	8.4653166e-05
2,813	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	8.0975254e-05
2,886	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB	7.9957585e-05
2,948	Optimized Query Execution in Large Search Engines with Global Page Ordering	2003	VLDB	7.9323466e-05
12,631	Data Currency in Replicated DHTs	2007	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,513	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD
2	2,525	Answering Top-k Queries Using Views	2006	VLDB
3	12,028	Efficient Top-k Indexing via General Reductions	2016	PODS
4	1,967	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB
5	8,281	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
6	7,299	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
7	7,550	Processing Top-k Join Queries	2010	VLDB
8	7,185	Anytime Measures for Top-k Algorithms	2007	VLDB
9	3,500	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD
10	12,308	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD