DocumentCode :
3530840
Title :
Optimal Pivots to Minimize the Index Size for Metric Access Methods
Author :
Ares, Luis G. ; Brisaboa, Nieves R. ; Esteller, Maria F. ; Pedreira, Óscar ; Places, Angeles S.
Author_Institution :
Database Lab., Univ. da Coruna, A Coruna, Spain
fYear :
2009
fDate :
29-30 Aug. 2009
Firstpage :
74
Lastpage :
80
Abstract :
We consider the problem of similarity search in metric spaces with costly distance functions and large databases. There is a trade-off between the amount of information stored in the index and the reduction in the number of comparisons for solving a query. Pivot-based methods clearly outperform clustering-based ones in number of comparisons, but their space requirements are higher and this can prevent their application in real problems. Therefore, several strategies have been proposed that reduce the space needed by pivot-based methods, as BAESA, FQA or KVP. In this paper, we analyze the usefulness of pivots depending on their proximity to the object. As consequence of this analysis, we propose a new pivot-based method that requires an amount of space equal or very close to that needed by clustering-based methods. We provide experimental results that show that our proposal represents a competitive strategy to clustering oriented solutions when using the same amount of memory.
Keywords :
data mining; database indexing; pattern clustering; query processing; very large databases; BAESA; FQA; KVP; clustering-based method; competitive strategy; data mining; distance function; index size minimization; large database; metric access method; metric space similarity search; optimal pivot-based method; query processing; Algorithm design and analysis; Clustering algorithms; Costs; Databases; Extraterrestrial measurements; Indexes; Indexing; Laboratories; Proposals; Indexing; Metric Spaces; Similarity Search;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Similarity Search and Applications, 2009. SISAP '09. Second International Workshop on
Conference_Location :
Prague
Print_ISBN :
978-0-7695-3765-8
Type :
conf
DOI :
10.1109/SISAP.2009.21
Filename :
5271948
Link To Document :
بازگشت