计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (5): 126-129.

• 数据库、信号与信息处理 • 上一篇    下一篇

球面上的最近邻查询方法研究

张丽平,李 松,郝忠孝   

  1. 哈尔滨理工大学 计算机科学与技术学院,哈尔滨 150080
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-02-11 发布日期:2011-02-11

Research of methods for nearest neighbor query on spherical surface

ZHANG Liping,LI Song,HAO Zhongxiao   

  1. School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-02-11 Published:2011-02-11

摘要: 球面上的最近邻查询在空间数据库最近邻查询领域具有重要的意义。为了处理球面上的最近邻查询问题,针对球面上数据对象点的特征和近邻查询的需要,给出了处理球面上最近邻查询的3种方法:利用球面voronoi图计算最近邻方法(VNS);利用欧氏空间内的空间数据索引结构方法(SPINS)和降维方法(APNS)。进一步,在动态的密集数据集和动态的稀松数据集两种典型的组合情况下分别着重对3 种方法处理最近邻查询的性能进行了实验比较。理论分析和实验结果表明,给出的3种方法可较好地处理球面上具有不同性质特征的空间数据对象点的近邻查询问题。

关键词: 最近邻, 球面, 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