DKNNS:面向延迟敏感型应用的可扩展精确分布式K近邻搜索算法研究

DKNNS: Scalable and accurate distributed K nearest neighbor search for latency-sensitive applications

为了降低用户访问延迟,延迟敏感型网络应用需要选择合适的邻近服务节点响应用户访问请求.分布式K近邻搜索通过可扩展的选择距任意用户节点邻近的K个服务节点,可以有效满足网络应用延迟优化的目的.已有工作在精确度以及可扩展性等方面存在不足.针对可扩展精确的K近邻搜索问题,文中提出了分布式K近邻搜索方法DKNNS(distributed K nearest neighbor search).DKNNS将大量的服务节点组织为邻近性感知的多级环,通过最远节点搜索机制选择优化的K近邻搜索初始化节点,然后基于回退方式快速的在目标节点邻近区域发现K个近邻.基于理论分析,模拟测试以及真实环境下的部署实验发现,在不同规模的节点集合下,DKNNS算法能够确定近似最优的K个服务节点.且DKNNS的查询延迟,查询开销均显著低于Meridian算法.最后,DKNNS的返回结果相对于Meridian具有较高的稳定性.

To reduce the access latencies of end hosts, latency-sensitive applications need to choose suitably close service machines to answer the access requests from end hosts. Distributed K nearest neighbor search locates K service machines closest to end hosts, which can efficiently optimize the access latencies for end hosts. Existing work has weakness in terms of the accuracy and scalability. According to the scalable and accurate K nearest neighbor search problem, we propose a distributed/（ nearest neighbor search method called DKNNS in this paper. Service machines are organized into a locality-aware multilevel ring. DKNNS first locates a service machine that starts the search process based on a farthest neighbor search scheme, then discovers K nearest service machines based on a backtracking approach within the proximity region containing the target in the latency space. Theoretical analysis, simulation results and deployment experiments on the PlanetLab show that, DKNNS can determine K approximately optimal service machines, with modest completion time and query loads. Finally, DKNNS is also quite stable that can be used for reducing frequent searches by caching found nearest neighbors.