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: 1445
Venue: PODS
Year: 2008
Pagerank: 7.8049517e-05
Overall Rank: 2,965 | 79.40%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Karl Schnaitter
2. Neoklis Polyzotis

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,474	Top-k Bounded Diversification	2012	SIGMOD	8.6956353e-05
4,060	On the Complexity of Query Result Diversification	2013	VLDB	6.4840236e-05
4,072	Proximity Rank Join	2010	VLDB	6.4726748e-05
5,379	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5375923e-05
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
6,923	Skyline Query Processing over Joins	2011	SIGMOD	4.8878659e-05
7,365	Sharing Work in Keyword Search over Databases	2011	SIGMOD	4.7459715e-05
7,768	On the Complexity of Package Recommendation Problems	2012	PODS	4.6523419e-05
8,088	Determining the Relative Accuracy of Attributes	2013	SIGMOD	4.5856065e-05
8,148	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5717374e-05
8,857	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	4.4302523e-05
9,353	Rank Join Queries in NoSQL Databases	2014	VLDB	4.3485003e-05
12,199	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1905499e-05
12,240	Finding Maximum Degrees in Hidden Bipartite Graphs	2010	SIGMOD	4.1905499e-05
12,288	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	4.1905499e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
551	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310856
673	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018325667
1,207	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001327437
6,826	Depth Estimation for Ranking Query Optimization	2007	VLDB	4.9090969e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
12,199	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1905499e-05
8,065	Efficient Computation of Quantiles over Joins	2023	PODS	4.5899218e-05
673	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018325667
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
551	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310856
7,660	Processing Top-k Join Queries	2010	VLDB	4.6814547e-05
2,249	Rank-aware Query Optimization	2004	SIGMOD	9.1956569e-05
5,379	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5375923e-05
4,072	Proximity Rank Join	2010	VLDB	6.4726748e-05