关键词: 空间数据库, Voronoi图, 最近邻查询, 单纯型连续近邻链, 受限区域

Abstract: The exiting methods of the nearest neighbor query can not search the simple continuous near neighbor chain in the constrained regions. To remedy the deficiency of the existing work, according to the complexity of the constrained regions and the obstacles, the simple continuous near neighbor chain query with non obstacles and with obstacles were studied respectively. The VOR_NB_CRSCNNC algorithm and the VOR_CB_CRSCNNC algorithm were presented. The spatial data were filtered and computed based on the Voronoi diagram and the judging circles. The calculations of each query were reduced by only considering the points which lay in the Voronoi polygon and the juding circles. The theatrical study and the experimental results show that the redundant calculation is reduced and the query efficiency is less affected by the constrained regions.

Key words: spatial database, Voronoi diagram, nearest neighbor query, Simple Continues Near Neighbor Chain (SCNNC), constrained region