JISBD2007-04: Búsqueda de vecinos en espacios multidimensionales agujereados (JISBD2007-04: Neighbors search in holey multidimensional spaces)

M. Barrena (barrena@unex.es)2, C. Pachón (cjpachon@sicubo.com)1, E. Jurado (elenajur@unex.es)2

2Universidad de Extremadura

This paper appears in: Revista IEEE América Latina

Publication Date: Aug. 2008
Volume: 6,   Issue: 4 
ISSN: 1548-0992

Similarity search has a growing usefulness in a range of applications like time series, image and multimedia databases, biological data, and so on. These searches are implemented by means of neighbour queries in the multidimensional spaces where the data resides. Faced with a large volume of data, it becomes imperative the use of indexing methods with specific algorithms capable of reducing the queries response time. The balanced indexing structures based on kd-trees generate a partition of multidimensional space in holey regions that complicate the underlying topology, hindering the calculation of distances between points and regions. In this paper, we introduce a nearest neighbour search algorithm that exploits this topology for efficiency. The experimental results that are included in this study support the usefulness of the proposed method.

Index Terms:
Similarity search, multidimensional indexing, nearest neighbour search   

Documents that cite this document
This function is not implemented yet.

[PDF Full-Text (481)]