A Voronoi Diagram-Based Grid Structure for Efficient Nearest Neighbor Query Processing
Dongseop Kwon · Journal of the Korea Society of Computer and Information · 2008
Hearest-neighbor searches are essential operations in various applications such as multimedia systems and GIS systems. Although numbers of research works for nearest-neighbor search have been proposed. they have a limitation on the performance since they process queries on the fly with indexes on data. This paper proposes a new nearest-neighbor search algorithm based on a grid-based data structure, which Preprocesses and stores the result of nearest-neighbor queries using Voronoi diagrams over static data. While traditional techniques try to index data itself, the proposed technique attempts to index the result of the queries. Therefore, it performs nearest-neighbor queries more efficiently