Range Nearest-Neighbor QueryHaibo Hu and Dik Lun LeeAbstract—A range nearest-neighbor (RNN) query retrieves the nearest neighbor (NN) for every point in a range. It is a naturalgeneralization of point and continuous nearest-neighbor queries and has many applications. In this paper, we consider the ranges as(hyper)rectangles and propose efficient in-memory processing and secondary memory pruning techniques for RNN queries in both 2Dand high-dimensional spaces. These techniques are generalized for kRNN queries, which return the k nearest neighbors for everypoint in the range. In addition, we devise an auxiliary solution-based index EXO-tree to speed up any type of NN query. EXO-tree isorthogonal to any existing NN processing algorithm and, thus, can be transparently integrated. An extensive empirical study wasconducted to evaluate the CPU and I/O performance of these techniques, and the study showed that they are efficient and robustunder various data sets, query ranges, numbers of nearest neighbors, dimensions, and cache sizes.Index Terms—Spatial database, nearest-neighbor search.æ1INTRODUCTIONNEAREST-NEIGHBOR (NN) query is an important querytype supported by most spatial databases [1], [2], [3],[4]. Traditional NN queries require input as points fromwhich the NNs are computed. Thus, they are also calledpoint nearest-neighbor (PNN) queries. Although Tao et al.[5] extended PNN queries to “continuous nearest-neighbor”(CNN) queries, which retrieve the NNs for all points on aline segment, the query input is still limited to a1-dimensional line. In this paper, we propose a moregeneral query type—“range nearest-neighbor”(RNN)queries. Given a d-dimensional data set, an RNN queryretrieves the nearest neighbors for every point in ad-dimensional hyperrectangle. Such a generalization elim-inates the dimensionality limitation on the query input.RNN queries have many applications:1. In mobile environments, users do not have theaccurate knowledge about their locations to specifythe query points because all location identificationmethods have errors. Even if they have suchknowledge, they may not want to expose theselocations to the service providers for privacyreasons. RNN queries address these issues byallowing users to specify ranges rather than pointsfor NN queries. They are particularly appealing tothe large number of 2G/3G mobile subscriberswhose devices are incapable of pinpointing loca-tions. While these devices cannot support conven-tional NN queries, they can issue RNN queriesthrough text messages such as “find the nearesthotels to the City Park.”2. A user may continuously ask for nearest neighborswhile moving around. It is inefficient to submitmany PNN queries individually to the server. Abetter alternative is to submit a single RNN queryaround the current location to fetch all possiblenearest neighbors for this area. Any PNN queryissued in this area is then processed locally by anearest-neighbor search in the prefetched set, savingboth computation and communication costs.3. The above case can be generalized to the situation inwhich these PNN queries are submitt ed fromdifferent users. Processing them individually isinefficient because spatially adjacent PNN queriesoften access the same R-tree nodes. It is moreefficient to group and process them in a batch byfirst issuing an RNN query whose range is thebounding box of all the PNN query points and thenresolving the PNN results within the RNN results.This paper focuses on RNN query processing techniques.In general, processing an NN query on a spatial index (anR-tree, for example) involves two interleaving phases :secondary memory pruning of distant index nodes andin-memory computation of the nearest neighbors. For thefirst phase, we develop efficient pruning heuristics for state-of-the-art NN searching paradigms such as depth-firstsearch (DFS) [6] and best-first search (BFS) [7]. The secondphase is trivial for PNN queries: The distances between allthe objects in a leaf index node and the query point arecalculated and the object with the shortest distance isrecorded as the PNN candidate. However, this cannot beapplied to RNN queries since the number of query points inan RNN query is infinite. Therefore, we propose newalgorithms based on either planar geometry for two-dimensional spaces or linear programming for high-dimen-sional spaces. We then extend both the secondary memoryand in-memory techniques to kRNN queries, which retrievethe k nearest neighbors for every point in the range. Inaddition to these techniques, we propose a CNN-basedalgorithm for two-dimensional RNN queries.Another contribution of this paper is a solution-basedauxiliary index, called EXO-tree. It is designed to accelerateall types of NN (PNN, CNN, and RNN) searches. The basicidea is that, for each index node, EXO-tree indexes some78 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 18, NO. 1, JANUARY 2006. The authors are with the Department of Computer Science, Hong KongUniversity of Science and Technology, Clear Water Bay, Kowloon, HongKong. E-mail: {haibo, dlee}@cs.ust.hk.Manuscript received 23 Dec. 2004; revised 22 May 2005; accepted 12 July2005; published online 18 Nov. 2005.For information on obtaining reprints of this article, please send e-mail to:[email protected], and reference IEEECS Log Number TKDE-0525-1204.1041-4347/06/$20.00 ß 2006 IEEE Published by the IEEE Computer Society“valuable” objects to avoid visiting this node when weprocess NN queries. EXO-tree is built on top of the primaryspatial index (for example, an R-tree) and is separatelystored. Therefore, it does not affect the processing of othertypes of queries, such as range queries or spatial joins. EXO-tree is also orthogonal to other NN processing techniques.Thus, it can be incorporated into the aforementionedsecondary memory pruning techniques to further speedup the RNN search.The remainder of the paper is organized as follows:Section 2 reviews DFS, BFS, CNN, and some specialized NNsearch indexes. Section 3 presents the formal definition ofRNN queries. In Sections 4 and 5, various in-memory andsecondary memory RNN (and, more generally, kRNN)processing techniques are proposed. The EXO-tree isproposed in Section 6. The intensive experimental results,in terms of I/O and CPU costs, are analyzed in Section 7 tojustify all these techniques. Finally, w e suggest somedirections for future research.2RELATED WORK2.1 DFS and BFS ParadigmsGiven a hierarchical spatial