An indexing scheme for efficient support K-NN queries over DHTS

Distributed Hash Tables (DHTs) have been widely used as building block for large scale distributed applications. However, supporting k-NN queries efficiently remains a problem. In this paper, we present k-NN Search Tree (KST) which employs a novel mapping mechanism and a tree summarization strategy for reasonable distribution of its index structure. Analysis show that it can effectively support k-NN processing of such complex queries. Experimental results demonstrate that in comparison with the latest indexing techniques, PHT and DST, KST has a much better query performance in terms of both bandwidth consumption and response time.