Distributed antipole clustering for efficient data search and management in Euclidean and metric spaces

In this paper a simple and efficient distributed version of the introduced antipole clustering algorithm for general metric spaces is proposed. This combines ideas from the M-tree, the multi-vantage point structure and the FQ-tree to create a new structure in the "bisector tree" class, called the antipole tree. Bisection is based on the proximity to an "antipole" pair of elements generated by a suitable linear randomized tournament. The final winners (A, B) of such a tournament are far enough apart to approximate the diameter of the splitting set. A simple linear algorithm computing antipoles in Euclidean spaces with exponentially small approximation ratio is proposed. The antipole tree clustering has been shown to be very effective in important applications such as range and k-nearest neighbor searching, mobile objects clustering in centralized wireless networks with movable base stations and multiple alignment of biological sequences. In many of such applications an efficient distributed clustering algorithm is needed. In the proposed distributed versions of antipole clustering the amount of data passed from one node to another is either constant or proportional to the number of nodes in the network. The distributed antipole tree is equipped with additional information in order to perform efficient range search and dynamic clusters management. This is achieved by adding to the randomized tournaments technique, methodologies taken from established systems such as BFR and BIRCH*. Experiments show the good performance of the proposed algorithms on both real and synthetic data