一种快速的反向k近邻查找算法及其改进
反向k近邻是反向最近邻的扩展，目前大多数反向k近邻查询算法主要从R树演化而来，其查询性能往往随着维数的增加而下降，并且对于k>1的情况性能不尽人意。本文提出一种快速的反向K近邻查找算法，该方法利用现代计算机具有外存便宜，运行速度快的特点，预先计算数据之间的距离，并组织为数据索引块存储于外存，由计算机在空闲时自动进行维护。在进行反向最近邻查询时，只需读入相应的索引块，就可以进行直接查询，其时间复杂为O(N)，而且不受k大小的影响。为减少索引块的读取时间，本文又提出一种改进方法来有效地压缩索引块，仅用必要的二进制位来存储对象之间的距离，并将冗余减少到最低水平，有效地提高了算法的效率。最后通过实验分析评估算法的有效性和效率。
反向k近邻查找算法 算法优化 时间复杂度 索引块
骆炎民 柳培忠 陈汉雄
华侨大学计算机科学与技术学院, 厦门 361021 华侨大学工学院, 泉州 362021 筑波大学计算机科学系, 日本茨城 305-8577
国内会议
厦门
中文
1-7
2012-08-01（万方平台首次上网日期，不代表论文的发表时间）