PINE Based RNN Queries in Road Networks.
Maytham H. Safar, Ahmad Alsaleh · Biblioteca Digital da Memória Científica do INPE (National Institute for Space Research) · 2005
A common query type in spatial networks is to find the Reverse Nearest Neighbors RNN of a given query object. Due to the difficulties and the expense of the required calculations to answer such a query, almost all approaches in the literature use Euclidean distances and not the real network distance. In this work, we propose an approach that is based on a real network distance computation to answer the RNN query. In addition, we distinguish between four different types of queries that could rise by using two types of objects such as a road intersection (e.g., a location of a vehicle) or an interest point (e.g., a restaurant.) Our approach is based on manipulating the network Voronoi diagram properties and applying a progressive incremental network expansion for finding the polygon inner network distances required to solve an RNN query.