Distributed Antipole Clustering for Efficient Data Search and Management in Euclidean and Metric Spaces

In this paper a simple and efficient distributed version ofthe recently introduced Antipole Clustering algorithm forgeneral metric spaces is proposed. This combines ideasfrom the M-Tree, the Multi-Vantage Point structure and theFQ-Tree to create a new structure in the “bisector tree”class, called the Antipole Tree. Bisection is based on theproximity to an “Antipole” pair of elements generated by asuitable linear randomized tournament. The final winners(A;B) of such a tournament are far enough apart to approximatethe diameter of the splitting set. A simple linearalgorithm computing Antipoles in Euclidean spaces withexponentially small approximation ratio is proposed. TheAntipole Tree Clustering has been shown to be very effectivein important applications such as range and k-nearestneighbor searching, mobile objects clustering in centralizedwireless networks with movable base stations and multiplealignment of biological sequences. In many of such applicationsan efficient distributed clustering algorithm is needed.In the proposed distributed versions of Antipole Clusteringthe amount of data passed from one node to another is eitherconstant or proportional to the number of nodes in the network.The Distributed Antipole Tree is equipped with additionalinformation in order to perform efficient range searchand dynamic clusters management. This is achieved byadding to the randomized tournaments technique, methodologiestaken from established systems such as BFR andBIRCH*. Experiments show the good performance of theproposed algorithms on both real and synthetic data.