LBD:基于局部位码比较的高维空间KNN搜索算法

摘要

利用高维数据空间合理划分,提出一种简单有效的KNN检索算法-LBD.通过聚类将数据划分成多个子集空间,对每个聚类子集内的高维向量,利用距离和位码定义简化表示形式.KNN搜索时,首先利用距离信息确定候选范围,然后利用某些维上的位码不相同信息进一步缩小搜索范围,提高剪枝效率.位码字符串比较时,按照维度贡献优先顺序,大大加快非候选点过滤.LBD利用特殊的B+树组织,降低I/O和距离计算代价.采用模拟数据和真实数据,实验验证了LBD具有更高的检索效率.