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.2255837e-05
Overall Rank: 2,614 | 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,174	Top-k Bounded Diversification	2012	SIGMOD	8.917444e-05
3,338	On the Complexity of Query Result Diversification	2013	VLDB	7.4103278e-05
4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.434561e-05
5,229	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.2196057e-05
5,769	Proximity Rank Join	2010	VLDB	6.0007533e-05
6,776	Skyline Query Processing over Joins	2011	SIGMOD	5.6847562e-05
7,543	Determining the Relative Accuracy of Attributes	2013	SIGMOD	5.4986002e-05
7,824	Sharing Work in Keyword Search over Databases	2011	SIGMOD	5.445981e-05
8,062	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	5.3955302e-05
8,183	On the Complexity of Package Recommendation Problems	2012	PODS	5.3817332e-05
9,053	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	5.230408e-05
9,681	Rank Join Queries in NoSQL Databases	2014	VLDB	5.1427987e-05
12,677	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.9793485e-05
12,718	Finding Maximum Degrees in Hidden Bipartite Graphs	2010	SIGMOD	4.9793485e-05
12,766	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	4.9793485e-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.0010679641
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
7,247	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.5748328e-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,677	Efficient Rank Join with Aggregation Constraints	2011	VLDB
3	7,435	Efficient Computation of Quantiles over Joins	2023	PODS
4	524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
5	4,752	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
6	507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB
7	7,615	Processing Top-k Join Queries	2010	VLDB
8	1,773	Rank-aware Query Optimization	2004	SIGMOD
9	5,229	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD
10	5,769	Proximity Rank Join	2010	VLDB