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: h9c9b466b0e939264
Venue: VLDB
Year: 2007
Pagerank: 7.1256193e-05
Overall Rank: 3,656 | 75.43%
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
194	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00025636725
1,462	Manu: A Cloud Native Vector Database Management System	2022	VLDB	0.0001058099
4,614	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	6.5014577e-05
6,973	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.6304028e-05
7,100	DeepEverest: Accelerating Declarative Top-K Queries for Deep Neural Network Interpretation	2022	VLDB	5.601767e-05
7,394	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.5370795e-05
7,787	On Efficient Top-k Query Processing in Highly Distributed Environments	2008	SIGMOD	5.4528991e-05
11,712	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9793485e-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.0010679641
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016296423
838	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013550235
1,439	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010642846
1,445	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.0001063035
2,006	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.199795e-05
2,561	Answering Top-k Queries Using Views	2006	VLDB	8.2977193e-05
2,874	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.9221111e-05
2,939	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB	7.8340314e-05
3,004	Optimized Query Execution in Large Search Engines with Global Page Ordering	2003	VLDB	7.7632345e-05
12,921	Data Currency in Replicated DHTs	2007	SIGMOD	4.9793485e-05

Semantically Similar Papers

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