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.