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

作　　者：FU YongQuan WANG YiJie 

机构地区：[1]National Key Laboratory for Parallel and Distributed Processing,School of Computer Science,National University of Defense Technology

出　　处：《Science China(Information Sciences)》2013年第3期119-135,共17页中国科学（信息科学）（英文版）

基　　金：supported by National Basic Research Program of China(Grant No.2011CB302601);National Natural Science Foundation of China(Grant No.60873215);Natural Science Foundation for Distinguished Young Scholars of Hunan Province(Grant No.S2010J5050);Specialized Research Fund for the Doctoral Program of Higher Education(Grant No.200899980003)

摘　　要：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 K 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 /（ 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.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 K 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 /（ 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.

关 键 词：latency sensitive network applications K nearest neighbor search network coordinate 

分 类 号：TP393.09[自动化与计算机技术—计算机应用技术]