Using spatial data access structures for filtering nearest neighbor queries

摘要

The detection of the nearest neighbor object to a given point in the reference space (NN query) is a common problem in geographical information systems (GISs). Data structures supporting range queries are not always adequate to support NN queries. For this reason, additional data structures, mainly relying on the use of some kind of tree, have been proposed. The main drawback of such solutions is that at least one tree path has to be analyzed in order to determine the NN object. In this paper, we overcome this problem by considering information on the reference space to improve the search. In particular, we propose a data structure that is obtained by integrating the R+-tree with a regular grid, indexed by using a hashing technique. The resulting data structure combines the advantages of a rectangular decomposition of the space, typical of R+-trees, with a direct access to each portion of the space, typical of hashing. The proposed technique is then compared both theoretically and experimentally with the R+-tree.