JTop Algorithms for Top-k Join Queries
Reza Akbarinia, Ihab F. Ilyas, M. TAMER ÖZSU, Patrick Valduriez, David R. Cheriton · 2008
Top-k join queries have become very important in many important areas of computing. One of the most efficient algorithms for top-k join queries is the Rank-Join algorithm [17] [18]. However, there are many cases where Rank-Join does much unnecessary access to the input data sources. In this report, we first show that there are many cases where Rank-Join’s stopping mechanism is not efficient, and it does much unnecessary accesses to the input data sources. Then, we propose JTop, a family of much more efficient algorithms for top-k queries. We prove that our algorithms always perform less work than Rank-Join, and thus are more efficient. We also show that the performance of our algorithms can be O(n) times better than that of Rank-Join where n is the number of data items in the database. We evaluated the performance of our algorithms through experimentation over databases with different distributions. The results show that over the tested databases our algorithms significantly outperform Rank-Join.