Nearest Neighbor Queries in Spatial and Spatio-temporal Databases

Dimitris Papadias

HKUST

Nearest neighbor (NN) search constitutes one of the most important queries in spatial and spatio-temporal databases. The most common type is the point NN query, which retrieves the Euclidean nearest neighbors of a static point. Such a query, however, is usually meaningless in highly dynamic environments, where the query point or the database objects move over time, or in applications (e.g., road networks), where the distance is not defined according to the Euclidean metric. This presentation overviews related work and proposes alternative forms of nearest neighbor search that cover a wide variety of situations: (i) time parameterized queries, (ii) continuous queries, (iii) location based queries, (iv) group NN queries (v) NN in road networkds and (vi) NN in the presence of obstacles.