An Adaptive Algorithm for P2P k-nearest Neighbor Search in High Dimensions
Xiaopeng Yu, Xiao-Gao Yu · 2007
K-Nearest Neighbors search (KNNS) in high-dimensional feature spaces is an important paradigm in pattern recognition. Existing centralized KNNS does not scale up to large volume of data because the response time is linearly increasing with the size of the searched file. In this article, an adaptive distributed A-nearest neighbor search algorithm (P2PAKNNS) for high dimension data is proposed to further improve the scalability in P2P systems. The idea adopts the generalized hypersphere partitioning and the similarity measure function HDsim(x oarr, y oarr) , which can adaptively determines the size of the hypersphere and avoid the problems that it-norm leads to the non-contrasting behavior of distance in high dimensional space. By exploiting parallelism in a dynamic network of computers, the query execution scales up very well considering the number of distance computations. The experiments indicate the algorithm is effective.