View publication
| Title | CP-Index: Using Clustering and Pivots for Indexing Non-Metric Spaces |
| Authors | Victor Sepulveda, Benjamin Bustos |
| Publication date | 2010 |
| Abstract | Most multimedia information retrieval systems use an indexing scheme to speed up similarity search. The index aims to discard large portions of the data collection at query time. Generally, these approaches use the triangular inequality to discard elements or groups of elements, thus requiring that the comparison distance satisfies the metric postulates. However, recent research shows that, for some applications, it is appropriate to use a non-metric distance, which can give more accurate judgments about the similarity of two objects. In such cases, the lack of the triangle inequality makes impossible to use the traditional approaches for indexing. In this paper we introduce the CP-index, a new approximate indexing technique for non-metric spaces that combines clustering and pivots. The index dynamically adapts to the conditions of the non-metric space using pivots when the fraction of triplets that break the triangle inequality is small, but sequentially searching the most promising candidates when the pivots becomes ineffective. |
| Pages | 75-82 |
| Conference name | International Workshop on Similarity Search and Applications |
| Publisher | IEEE Computer Society Press (Los Alamitos, CA, USA) |
| Reference URL |
|