The N-tree: an Indexing Technique for Nearest-Neighbor Queries
Faïza Najjar, Hassenet Slimani · IEEE International Conference on Computer Systems and Applications, 2006. · 2006
The advances of wireless technologies and mobile devices allow users to access information anywhere at any time. Among many mobile applications, the study of location-dependent query has received increasing attention in recent years. In particular, we focus on solving the nearest neighbor (NN) problem by exploring the use of an efficient index structure. In this paper, we propose a new index structure, called N-tree, for answering NN queries and enhancing the performance of location-dependent query processing. The N-tree makes use of both Voronoi diagram and its dual the Delaunay triangulation to preprocess the solution space for answering location-dependent queries efficiently. The basic idea of the construction of the balanced binary space partitioning tree, N-tree, is to determine a good frontier, represented by a set of neighbor sites, covering the remaining sites. Then, we describe how to process nearest neighbor queries based on the N-tree, and how to page N-tree. The performance of the N-tree is evaluated using synthetic data sets. Experimental results show that the proposed N-tree outperforms the traditional well-known indexes and it is as good as the D-tree, reported to be the best index [16]. Furthermore, we introduce an extension for processing k-nearest neighbor queries based on the N-tree.