Towards Load Balance and Maintenance in a Structured P2P Network for Locality Sensitive Hashing

摘要

In this paper, we consider load balancing and maintenance of distributed similarity search systems using locality sensitive hashing (LSH) in a structured peer-to-peer (P2P) network based on Distributed Hashing Table (DHT). LSH has been proven efficient in K-Nearest Neighbor (KNN) search in high dimensions. Recently, a number of schemes have been proposed to implement LSH over DHT-based P2P systems to process distributed similarity searches. We provide an efficient structure using virtual nodes to manage the multi-dimensional LSH bucket space in DHT peers and the maintenance algorithm, which improves load balancing in comparison with state-of-the-art techniques such as the virtual node algorithm. Here, we demonstrate effectiveness of the proposed method by experiments.