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

• DOI: 10.1007/s11432-011-4449-7
• Publication Date: 2011-11-26T01:11:03Z
• Authors: YongQuan Fu; YiJie Wang
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

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 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.