$k$ Nearest Neighbors Queries

Given a set of data points $P$ and a query point $q$ , and an integer $k>0$ , the $k$ nearest neighbors ($k$ NN) query is to find a result set $kNN$ that consists of $k$ data points such that for any $p\in (P-kNN)$ and any $p'\in kNN$ , $dist(p',q)\leq dist(p,q)$ .

Nearest neighbor queries have received intensive attention in spatial database community in the past decade. A $k$ NN query has various applications in spatial databases. Consider, for example, a set of points in two dimensions representing cities. A $k$ NN query may be issued to find ``what are the $k$ closest cities from a point $p$ ". In this section, we present a brief overview of the work done on $k$ NN queries. Since $k$ NN queries are widely studied by the researchers in different problem settings, we categorise the related work according to the characteristics of problem settings as follows.

• Snapshot $k$ NN queries: Find $k>0$ objects from a static dataset that are closest to a static query point according to Euclidean distance between them.

• Continuous $k$ NN queries: Continuously report $k>0$ objects, over a time period $T$ , from a continuously moving dataset that are closest to a continuously moving query point. These type of queries are most related with our work.

• $k$ NN queries in spatial networks: Find $k>0$ objects that are closest to a query point $q$ according to their network distances from $q$ . An example is ``find $k$ nearest hotels from my current location". Clearly, the underlying network is road network and the network distance between two points may be different from the minimum Euclidean distance between them. The problem can be extended to continuous monitoring of $k$ NNs on networks.

• Approximate $k$ NN queries: Sometimes the data is very large or can be accessed only once (e.g. in data streams). In such cases, finding exact $k$ NNs is not efficient so there are many solutions proposed to find the approximate $k$ nearest neighbors of queries with some guaranteed relative error. Such queries are called approximate-$k$ NN queries.

• Distributed processing of $k$ NN queries: Different from previous problem settings where a central server is solely responsible for computations, this problem is to find $k$ NNs assuming that the moving data points also have the computation and storage capabilities. Such algorithms utilize the computation and storage capabilities of mobile objects and aim to reduce computation load on the server and/or communication cost between mobile objects and the server.

In Section , we overview the related work on snapshot $k$ NN queries. Previous work on continuous monitoring of $k$ NN queries is given in Section . Section  surveys the work on $k$ NN queries over spatial networks. Approximate $k$ NN queries are presented in Section . Section  reviews the work on distributed processing of $k$ NN queries.