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: 4198
Venue: SIGMOD
Year: 2009
Pagerank: 6.3495536e-05
Overall Rank: 5,138 | 64.75%
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,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.1747954e-05
5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	6.1552328e-05
5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.1540123e-05
5,640	Proximity Rank Join	2010	VLDB	6.1384844e-05
8,894	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	5.3504579e-05
9,961	Threshold Queries in Theory and in the Wild	2022	VLDB	5.1879626e-05
11,183	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	5.093636e-05
12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB	5.093636e-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.0010828372
308	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021787597
499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017431827
509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017220967
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
2,585	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.3774452e-05
4,321	Efficiently Answering Top-k Typicality Queries on Large Databases	2007	VLDB	6.7617825e-05
7,123	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.6966694e-05
7,185	Anytime Measures for Top-k Algorithms	2007	VLDB	5.6779179e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
2	7,550	Processing Top-k Join Queries	2010	VLDB
3	499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
4	3,017	Joining Ranked Inputs in Practice	2002	VLDB
5	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
6	973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD
7	5,640	Proximity Rank Join	2010	VLDB
8	509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
9	1,759	Rank-aware Query Optimization	2004	SIGMOD
10	2,585	Evaluating Rank Joins with Optimal Cost	2008	PODS