Processing of Rank Joins in Highly Distributed Systems

In this paper, we study efficient processing of rank joins in highly distributed systems, where servers store fragments of relations in an autonomous manner. Existing rank join algorithms exhibit poor performance in this setting due to excessive communication costs or high latency. We propose a novel distributed rank-join framework that determines the subset of each relational fragment that needs to be fetched to generate the top-k join results. At the heart of our framework lies a score bound estimation algorithm that utilizes statistics to produce sufficient score bounds for each relation, which guarantee the correctness of the rank join result set. Furthermore, we propose a generalization of our framework that supports approximate statistics, in the case that the exact statistical information is not available. In addition, we demonstrate how our algorithms can utilize distributed statistics to process top-k join queries without any modifications. An extensive experimental study validates the efficiency of our framework and demonstrates its advantages over existing methods.