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.1279819e-05
Overall Rank: 3,653 | 75.45%
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
189	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.0002585319
1,456	Manu: A Cloud Native Vector Database Management System	2022	VLDB	0.00010588868
4,616	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	6.4983802e-05
6,974	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.6277375e-05
7,102	DeepEverest: Accelerating Declarative Top-K Queries for Deep Neural Network Interpretation	2022	VLDB	5.5991152e-05
7,396	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	5.5344583e-05
7,795	On Efficient Top-k Query Processing in Highly Distributed Environments	2008	SIGMOD	5.4503179e-05
11,718	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9769913e-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.0010679903
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016288995
840	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013544367
1,441	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010638056
1,446	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00010625633
2,008	IO-Top-k: Index-access Optimized Top-k Query Processing	2006	VLDB	9.1956849e-05
2,561	Answering Top-k Queries Using Views	2006	VLDB	8.2940439e-05
2,874	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.9186028e-05
2,940	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB	7.8306095e-05
3,006	Optimized Query Execution in Large Search Engines with Global Page Ordering	2003	VLDB	7.7598321e-05
12,927	Data Currency in Replicated DHTs	2007	SIGMOD	4.9769913e-05

Semantically Similar Papers

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