JISBD2007-04: Neighbors search in holey multidimensional spaces

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.