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.8110394e-05
Overall Rank: 2,961 | 79.41%
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,480	Top-k Bounded Diversification	2012	SIGMOD	8.6899714e-05
4,056	On the Complexity of Query Result Diversification	2013	VLDB	6.4883623e-05
4,069	Proximity Rank Join	2010	VLDB	6.4789031e-05
5,373	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5425231e-05
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
6,921	Skyline Query Processing over Joins	2011	SIGMOD	4.8925595e-05
7,374	Sharing Work in Keyword Search over Databases	2011	SIGMOD	4.7494134e-05
7,770	On the Complexity of Package Recommendation Problems	2012	PODS	4.6562597e-05
8,086	Determining the Relative Accuracy of Attributes	2013	SIGMOD	4.5899469e-05
8,145	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5761263e-05
8,857	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	4.4345027e-05
9,347	Rank Join Queries in NoSQL Databases	2014	VLDB	4.3526718e-05
12,191	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1945683e-05
12,232	Finding Maximum Degrees in Hidden Bipartite Graphs	2010	SIGMOD	4.1945683e-05
12,280	Building Ranked Mashups of Unstructured Sources with Uncertain Information	2010	VLDB	4.1945683e-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
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
552	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310903
674	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018327585
1,262	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012986539
6,829	Depth Estimation for Ranking Query Optimization	2007	VLDB	4.9136064e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
12,191	Efficient Rank Join with Aggregation Constraints	2011	VLDB	4.1945683e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
674	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018327585
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
552	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310903
7,692	Processing Top-k Join Queries	2010	VLDB	4.6761366e-05
2,393	Rank-aware Query Optimization	2004	SIGMOD	8.9016542e-05
5,373	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5425231e-05
4,069	Proximity Rank Join	2010	VLDB	6.4789031e-05