基于覆盖树的可扩展邻近搜索方法

摘要

针对邻近搜索技术受限于网络协议的支持以及存在空间嵌入误差的问题,提出一种基于覆盖树的可扩展邻近搜索方法CPS,包括覆盖树构建与维护协议和k近邻搜索算法两部分.节点自主计算自身所处层次,构造一棵层次化树.邻居维护协议负责维护覆盖树结构,确保其适应动态的网络环境.k近邻搜索算法通过对覆盖树剪枝,构造各层候选节点集合,提高搜索效率.实验结果表明,CPS的搜索精度优于典型的邻近搜索方法Tiers.