Robust and Efficient Algorithms for Rank Join Evaluation

Summary: Proposes FRPA, an instance-optimal rank-join operator that fixes PBRJRR_FR bottlenecks, keeping I/O on par with its best. Introduces adaptive a-FRPA and reports experiments with up to 10x speedups over the state-of-the-art in rank-join evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h3bf9fc44360dac13
Venue: SIGMOD
Year: 2009
Pagerank: 6.2167391e-05
Overall Rank: 5,233 | 64.83%
DOI: 10.1145/1559845.1559890

Incoming Non-self Citations Over Time

Authors

1. Jonathan Finger (HistoRx, Inc.; University of California Santa Cruz)
2. Neoklis Polyzotis (University of California Santa Cruz)

BibTeX Citation

@inproceedings{finger_sigmod09,
        title = {{Robust and Efficient Algorithms for Rank Join Evaluation}},
        author = {Finger, Jonathan and Polyzotis, Neoklis},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559890},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559890},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,593	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2429717e-05
4,745	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.4369578e-05
5,487	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1085184e-05
5,770	Proximity Rank Join	2010	VLDB	5.9979126e-05
9,061	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	5.227932e-05
10,157	Threshold Queries in Theory and in the Wild	2022	VLDB	5.0691578e-05
11,532	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.9769913e-05
12,683	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
313	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021301023
507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017093562
524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00016902116
962	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012818013
2,615	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.2217676e-05
4,409	Efficiently Answering Top-k Typicality Queries on Large Databases	2007	VLDB	6.609155e-05
7,249	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.5722715e-05
7,329	Anytime Measures for Top-k Algorithms	2007	VLDB	5.5485926e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,745	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
2	7,621	Processing Top-k Join Queries	2010	VLDB
3	507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
4	3,051	Joining Ranked Inputs in Practice	2002	VLDB
5	12,683	Efficient Rank Join with Aggregation Constraints	2011	VLDB
6	962	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD
7	5,770	Proximity Rank Join	2010	VLDB
8	524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
9	1,773	Rank-aware Query Optimization	2004	SIGMOD
10	2,615	Evaluating Rank Joins with Optimal Cost	2008	PODS