DocumentCode :
2042542
Title :
Distributed antipole clustering for efficient data search and management in Euclidean and metric spaces
Author :
Ferro, Alfredo ; Giugno, Rosalba ; Mongiovì, Misael ; Pigola, Giuseppe ; Pulvirenti, Alfredo
Author_Institution :
Dept. of Math. & Comput. Sci., Catania Univ.
fYear :
2006
fDate :
25-29 April 2006
Abstract :
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
Keywords :
distributed processing; pattern clustering; trees (mathematics); Euclidean space; FQ-tree; M-tree; bisector tree; data management; data search; distributed antipole clustering; distributed antipole tree; linear randomized tournament; metric space; multivantage point structure; Base stations; Binary trees; Clustering algorithms; Computer science; Extraterrestrial measurements; Indexing; Mathematics; Partitioning algorithms; Research and development;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International
Conference_Location :
Rhodes Island
Print_ISBN :
1-4244-0054-6
Type :
conf
DOI :
10.1109/IPDPS.2006.1639313
Filename :
1639313
Link To Document :
بازگشت