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: h8c649b2552e6180c
Venue: PODS
Year: 2008
Pagerank: 8.2217676e-05
Overall Rank: 2,615 | 82.43%
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,177	Top-k Bounded Diversification	2012	SIGMOD	8.9132232e-05
3,338	On the Complexity of Query Result Diversification	2013	VLDB	7.4068199e-05
4,745	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.4369578e-05
5,233	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.2167391e-05
5,770	Proximity Rank Join	2010	VLDB	5.9979126e-05
6,781	Skyline Query Processing over Joins	2011	SIGMOD	5.6820651e-05
7,549	Determining the Relative Accuracy of Attributes	2013	SIGMOD	5.4959973e-05
7,828	Sharing Work in Keyword Search over Databases	2011	SIGMOD	5.4434032e-05
8,068	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.392976e-05
8,190	On the Complexity of Package Recommendation Problems	2012	PODS	5.3791856e-05
9,061	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	5.227932e-05
9,688	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1403642e-05
12,683	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.9769913e-05
12,724	Finding Maximum Degrees in Hidden Bipartite Graphs	2010	SIGMOD	4.9769913e-05
12,772	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	4.9769913e-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.0010679903
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
7,249	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.5722715e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
2	12,683	Efficient Rank Join with Aggregation Constraints	2011	VLDB
3	7,438	Efficient Computation of Quantiles over Joins	2023	PODS
4	524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
5	4,745	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
6	507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
7	7,621	Processing Top-k Join Queries	2010	VLDB
8	1,773	Rank-aware Query Optimization	2004	SIGMOD
9	5,233	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD
10	5,770	Proximity Rank Join	2010	VLDB