Towards Load Balancing for LSH-based Distributed Similarity Indexing in High-Dimensional Space
Lu Rong Shen, Jiagao Wu, Yongrong Wang, Linfeng Liu · 2018
Locality-Sensitive Hashing (LSH) and its variants are well-known indexing schemes for solving the similarity search problem in high-dimensional space. Traditionally, these indexing schemes are centrally managed and multiple hash tables are needed to guarantee the search quality. However, due to the limitation of storage space, the centralized indexing schemes become impractical for massive data objects. Therefore, several distributed indexing schemes are proposed and how to ensure load balancing is a key issue in large-scale structured P2P networks. In this paper, we propose a novel theoretical model of data distribution to solve the load balancing problem. Unlike earlier schemes, we focus on load balancing in single hash table rather than multiple tables which, to our knowledge, has not been considered before. Then we propose a static distributed indexing scheme based on the theoretical model to predict the distribution of hash results. Furthermore, we propose a dynamic load rebalancing algorithm to make the static indexing scheme more practical and robust. The experiments based on synthetic and two real datasets show that the proposed distributed similarity indexing scheme are effective and efficient in high-dimensional space.