DocumentCode :
2547973
Title :
An effective clustering algorithm to index high dimensional metric spaces
Author :
Chávez, Edgar ; Navarro, Gonzalo
Author_Institution :
Escuela de Ciencias Fisico-Matematicas, Univ. Michoacana, Mexico
fYear :
2000
fDate :
2000
Firstpage :
75
Lastpage :
86
Abstract :
A metric space consists of a collection of objects and a distance function defined among them, which satisfies the triangular inequality. The goal is to preprocess the set so that, given a set of objects and a query, one can retrieve those objects close enough to the query. The number of distances computed to achieve this goal is the complexity measure. The problem is very difficult in the so-called high dimensional metric spaces, where the histogram of distances has a large mean and a small variance. A recent survey on methods to index metric spaces has shown that the so-called clustering algorithms are better suited than their competitors, pivot based algorithms, to cope with high dimensional metric spaces. The authors present a new clustering method that achieves much better performance than all the existing data structures. We present analytical and experimental results that support our claims and that give the users the tuning parameters to make optimal use of this data structure
Keywords :
computational complexity; data structures; indexing; information retrieval; pattern clustering; search problems; set theory; clustering algorithm; clustering algorithms; clustering method; complexity measure; data structures; distance function; distance histogram; high dimensional metric space indexing; object retrieval; pivot based algorithms; set preprocessing; triangular inequality; tuning parameters; Audio databases; Clustering algorithms; Clustering methods; Data structures; Extraterrestrial measurements; Fingerprint recognition; Histograms; Image databases; Information retrieval; Performance evaluation;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
String Processing and Information Retrieval, 2000. SPIRE 2000. Proceedings. Seventh International Symposium on
Conference_Location :
A Curuna
Print_ISBN :
0-7695-0746-8
Type :
conf
DOI :
10.1109/SPIRE.2000.878182
Filename :
878182
Link To Document :
بازگشت