关键词: 最近邻, 球面, voronoi图, R树, 空间数据库

Abstract: The nearest neighbor query on the spherical surface has great significance in the nearest neighbor query of the spatial database.To deal with the nearest neighbor query on the spherical surface effectively，based on the characteristics of the data objects on the spherical surface and the needs of the nearest neighbor query，three methods are proposed.The methods are respectively the nearest neighbor query based on the spherical surface voronoi diagram（VNS），the query based on the spatial index structure in the euclidean space（SPINS） and the method of the dimensional reduction（APNS）.Furthermore，the performance of the three methods is analyzed by experiment according to the dynamic dense dataset and the dynamic sparse dataset.The theoretical analysis and the experimental results show that the three methods can handle nearest neighbor query of the data objects with different properties on the spherical surface efficiently.

Key words: nearest neighbor, spherical surface, voronoi diagram, R tree, spatial database