Evaluating Rank Joins with Optimal Cost

Summary: Generalized analysis of rank-join under monotone scores and ranked access; shows HRJN may read inputs suboptimally and that computing optimal stopping is NP-hard in general. For bounded-query-complexity cases, gives an algorithm that infers tight benefit bounds and attains constant-factor optimal cost. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1444
Venue: PODS
Year: 2008
Pagerank: 8.3774452e-05
Overall Rank: 2,585 | 82.27%
DOI: 10.1145/1376916.1376924

Incoming Non-self Citations Over Time

Authors

1. Karl Schnaitter (University of California Santa Cruz)
2. Neoklis Polyzotis (University of California Santa Cruz)

BibTeX Citation

@inproceedings{schnaitter_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Evaluating Rank Joins with Optimal Cost}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376924},
        doi = {10.1145/1376916.1376924},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Schnaitter, Karl and Polyzotis, Neoklis},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,259	Top-k Bounded Diversification	2012	SIGMOD	8.8529269e-05
3,596	On the Complexity of Query Result Diversification	2013	VLDB	7.2722683e-05
5,138	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.3495536e-05
5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.1540123e-05
5,640	Proximity Rank Join	2010	VLDB	6.1384844e-05
6,643	Skyline Query Processing over Joins	2011	SIGMOD	5.8152344e-05
7,404	Determining the Relative Accuracy of Attributes	2013	SIGMOD	5.6246845e-05
7,670	Sharing Work in Keyword Search over Databases	2011	SIGMOD	5.5709469e-05
8,028	On the Complexity of Package Recommendation Problems	2012	PODS	5.504636e-05
8,133	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.4813895e-05
8,894	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	5.3504579e-05
9,497	Rank Join Queries in NoSQL Databases	2014	VLDB	5.2608378e-05
12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB	5.093636e-05
12,427	Finding Maximum Degrees in Hidden Bipartite Graphs	2010	SIGMOD	5.093636e-05
12,475	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
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
7,123	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.6966694e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
2	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
3	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
4	509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
5	5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
6	499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
7	7,550	Processing Top-k Join Queries	2010	VLDB
8	1,759	Rank-aware Query Optimization	2004	SIGMOD
9	5,138	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD
10	5,640	Proximity Rank Join	2010	VLDB