Direction-Aware Nearest Neighbor Query

Abstract

Although the direction aspect is as important as the distance aspect when retrieving spatial objects, the studies of direction-aware queries are limited. The direction-based surrounder query cannot guarantee good directional diversity. In this paper, we propose the direction-aware nearest neighbor query (DNN query), which can recommend the nearest objects and ensure that the results have good directional diversity. Given a query point q and an angular threshold θ, the DNN query searches for the nearest neighbors on various directions around q. The DNN query can apply to the scenario where the user searches for the nearest objects around him. It can also apply to the scenario where the user searches for the photos of a geographic object according to the locations where the photos are taken. It can find photos that capture different views of the query object. In this paper, we propose the point-DNN query, where the query object is a point, and extend it to the range-DNN query, where the query object is a rectangle. We design algorithms to answer the DNN queries and also conduct comprehensive experiments to evaluate the performances of the algorithms.

Keywords

• Nearest neighbor query
• direction-aware
• spatial database