K-Nearest Neighbor Search in Peer-to-Peer Systems
Hoda Mashayekhi, Jafar Alim Habibi · 2010
Abstract — Data classification in large scale systems, such as peer-to-peer networks, can be very communication-expensive and impractical due to the huge amount of available data and lack of central control. Frequent data updates pose even more difficulties when applying existing classification techniques in peer-to-peer networks. We propose a distributed, scalable and robust classification algorithm based on k-nearest neighbor estimation. Our algorithm is asynchronous, considers data updates and imposes low communication overhead. The proposed method uses a content based overlay structure to organize data and moderate the number of query messages propagated in the network. Simulation results show that our algorithm performs efficiently in large scale networks. Keywords- Classification; K-Nearest Neighbors; Content Addressable Network; Peer-to-peer systems.