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

Scalable Proximity Searching Method Based on Cover Tree

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

Aiming at the problem of constraint on network protocols or incurring embedding error in the existing methods,a scalable proximity search method based on cover tree CPS is raised.It is comprised of two parts： cover tree constructing protocol and maintaining protocol,and k nearest neighbors searching algorithm.Attending nodes compute the layers of themselves,so as to construct a layered tree.The neighbor maintaining protocol is responsible for maintaining the structure of cover tree,ensuring the adaptability in the network environment.k nearest neighbors searching algorithm constructs candidate nodes for every level by pruning the cover tree in order to improve the searching efficiency.Simulation results indicate that the accuracy of CPS is better than Tiers.