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

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

支持k近邻查询的X*树索引结构

章德斌1,曹丽君2,梁永欣1,张忠平1   

  1. 1.燕山大学 信息科学与工程学院,河北 秦皇岛 066004
    2.河北科技师范学院,河北 秦皇岛 066004
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-02-11 发布日期:2011-02-11

X*tree index structure for k nearest neighbor queries

ZHANG Debin1,CAO Lijun2,LIANG Yongxin1,ZHANG Zhongping1   

  1. 1.College of Information Science and Engineering,Yanshan University,Qinhuangdao,Hebei 066004,China
    2.Hebei Normal University of Science & Technology,Qinhuangdao,Hebei 066004,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-02-11 Published:2011-02-11

摘要: 通过分析已有的索引结构在进行k近邻查询时效率上的不足,提出了适合进行k近邻查询的X*树索引结构,采用了新的结点分裂算法,同时不需要额外存储结点分裂的历史信息。实验结果表明它比X树的时间和空间性能更好,更适合k近邻查询的应用。

关键词: k近邻查询, 高维索引结构, 结点分裂, 带权重叠率

Abstract: By analyzing the inefficiency of k nearest neighbor query in existing index structures,this paper presents X*tree index structure which is suitable to perform k nearest neighbor query.A new node splitting algorithm is adopted,and the Split History field is omitted.The experiment shows that it has better performance than X*tree in time and space complexity,and it is more suitable to k nearest neighbor query.

Key words: k nearest neighbor query, high dimensional index structure, node splitting, weighted overlap