Sequential Algorithms for Constructing an 'Out-of-Place' Multidimensional Quad-Tree Index for Answering Exact and Approximate Fixed-Radius Nearest Neighbor Queries

摘要

Answering nearest neighbor queries is an important problem in many areas, ranging from geographic systems to similarity searching in object data-bases (e.g. image and video databases). In order to answer such queries efficiently, an index data structure is usually constructed over the searched objects. In this paper we present novel top-down and bottom-up sequential algorithms for constructing a multidimensional quad-tree index. In all the algorithms the objects may be indexed in association with both quad-tree nodes which they intersect and those which they do not intersect. The common aspect of all the algorithms is that, in order to answer a query, only a single node of the index will need to be searched. The work presented in this paper continues the work presented in [21].