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.2196057e-05
Overall Rank: 5,229 | 64.85%
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,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2468757e-05
4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.434561e-05
5,482	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.111411e-05
5,769	Proximity Rank Join	2010	VLDB	6.0007533e-05
9,053	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	5.230408e-05
10,153	Threshold Queries in Theory and in the Wild	2022	VLDB	5.0715586e-05
11,526	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.9793485e-05
12,677	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.9793485e-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.0010679641
313	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021311041
507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017101297
524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00016909926
961	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001282305
2,614	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.2255837e-05
4,408	Efficiently Answering Top-k Typicality Queries on Large Databases	2007	VLDB	6.6122752e-05
7,247	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.5748328e-05
7,327	Anytime Measures for Top-k Algorithms	2007	VLDB	5.5512161e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
2	7,615	Processing Top-k Join Queries	2010	VLDB
3	507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
4	3,049	Joining Ranked Inputs in Practice	2002	VLDB
5	12,677	Efficient Rank Join with Aggregation Constraints	2011	VLDB
6	961	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD
7	5,769	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,614	Evaluating Rank Joins with Optimal Cost	2008	PODS