A taxonomy for nearest neighbour queries in spatial databases

Nearest neighbour queries (or kNN) have been used in many disciplines, including spatial databases. kNN queries have gone beyond simply finding nearest objects. It is, therefore, important to understand the full spectrum of kNN queries, even before starting to work on how to process and optimise such queries. The aim of this paper is to give a complete picture of what kNN queries are capable of. In this study, we present a survey of kNN queries, in which we propose a taxonomy of kNN queries, comprising four perspectives: (i) a Space perspective, (ii) a Result perspective, (iii) a Query-Point perspective, and (iv) a Relationship perspective. These give a comprehensive overview of kNN queries. As kNN is a large area of research, in this paper, we confine the discussion to kNN queries on stationary objects.

► The paper presents a complete taxonomy of Nearest Neighbour Queries in spatial databases.
► The taxonomy comprises 4 perspectives: space, result, query-point, and relationship.
► The space perspective covers Euclidean space and spatial road network space.
► The result perspective focuses on various possible types of query results.
► The query-point perspective highlights that locations of the query.