Branch-and-Bound Algorithm for Reverse Top-k Queries

Summary: Proposes a branch-and-bound algorithm for reverse top-k queries that avoids per-user top-k executions and full preference scans. Leverages pruning properties and optimizations; experiments show large gains over RTA on large preference collections. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h773b823a88697c30
Venue: SIGMOD
Year: 2013
Pagerank: 6.5014577e-05
Overall Rank: 4,614 | 68.98%
DOI: 10.1145/2463676.2465278

Incoming Non-self Citations Over Time

Authors

1. Akrivi Vlachou (Athena; Norwegian Institute of Technology)
2. Christos Doulkeridis (Norwegian Institute of Technology; University of Piraeus)
3. Kjetil Nørvåg (Norwegian Institute of Technology)
4. Yannis Kotidis (Athens University of Economics and Business)

BibTeX Citation

@inproceedings{vlachou_sigmod13,
        title = {{Branch-and-Bound Algorithm for Reverse Top-k Queries}},
        author = {Vlachou, Akrivi and Doulkeridis, Christos and Nørvåg, Kjetil and Kotidis, Yannis},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2465278},
        url = {https://dl.acm.org/doi/10.1145/2463676.2465278},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,955	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.8102237e-05
5,353	Why Not Yet: Fixing a Top-k Ranking that Is Not Fair to Individuals	2023	VLDB	6.1637765e-05
5,913	Reverse k-Ranks Query	2014	VLDB	5.9500931e-05
6,378	Maximum Rank Query	2015	VLDB	5.8086918e-05
6,971	Global Immutable Region Computation	2014	SIGMOD	5.6308579e-05
8,993	Creating Top Ranking Options in the Continuous Option and Preference Space	2019	VLDB	5.2419215e-05
9,172	Determining the Impact Regions of Competing Options in Preference Space	2017	SIGMOD	5.2140475e-05
10,086	On m-Impact Regions and Standing Top-k Influence Problems	2021	SIGMOD	5.0830849e-05
11,874	tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space	2022	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
111	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00032675259
342	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00020530255
418	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018617842
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016607433
643	Evaluating Top-k Selection Queries	1999	VLDB	0.00015217076
1,892	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.4166991e-05
2,485	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD	8.3993865e-05
2,786	DADA: A Data Cube for Dominant Relationship Analysis	2006	SIGMOD	8.0165674e-05
3,068	Towards Robust Indexing for Ranked Queries	2006	VLDB	7.6867401e-05
3,192	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	7.5512396e-05
3,656	Best Position Algorithms for Top-k Queries	2007	VLDB	7.1256193e-05
4,241	Creating Competitive Products	2009	VLDB	6.7085648e-05
4,547	Identifying the Most Influential Data Objects with Reverse Top-k Queries	2010	VLDB	6.5425744e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	643	Evaluating Top-k Selection Queries	1999	VLDB
2	2,561	Answering Top-k Queries Using Views	2006	VLDB
3	7,327	Anytime Measures for Top-k Algorithms	2007	VLDB
4	7,615	Processing Top-k Join Queries	2010	VLDB
5	7,394	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
6	8,449	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
7	12,599	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
8	2,485	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD
9	4,547	Identifying the Most Influential Data Objects with Reverse Top-k Queries	2010	VLDB
10	5,913	Reverse k-Ranks Query	2014	VLDB