Voronoi-based reverse nearest neighbor query processing on spatial networks

Maytham Safar

doi:10.1007/s00530-009-0167-z

Voronoi-based reverse nearest neighbor query processing on spatial networks

2009-09-12

72

PRE

AI

DOI：10.1007/s00530-009-0167-z

Original

Original request for help

Save

Abstract

En 中文

The use of Voronoi diagram has traditionally been applied to computational geometry and multimedia problems. In this paper, we will show how Voronoi diagram can be applied to spatial query processing, and in particular to Reverse Nearest Neighbor (RNN) queries. Spatial and geographical query processing, in general, and RNN in particular, are becoming more important, as online maps are now widely available. In this paper, using the concept of Voronoi diagram, we classify RNN into four types depending on whether the query point and the interest objects are the generator points of the Voronoi Polygon or not. Our approach is based on manipulating Network Voronoi Diagram properties and applying a progressive incremental network expansion for finding the polygon inner network distances required to solve RNN queries. Our experimentation results show that our approaches have good response times in answering RNN queries.

Keywords:

Voronoi diagram

Network Voronoi diagram

Spatial network databases

Nearest neighbor

Reverse nearest neighbor

Query processing

Voronoi-based reverse nearest neighbor query processing on spatial networks

Abstract

Journal

Organization