分布式结构化P2P网络下局部敏感哈希快速检索的负载均衡  

Load balance of the fast similarity search using locality sensitive hashing in structured P2P networks

作　　者：齐向东[1] 刘大伟[2,3] 王劲林[1,2] 

机构地区：[1]中国科学院声学所国家网络新媒体工程技术研究中心,北京100190 [2]中国科学技术大学网络传播系统与控制联合实验室,合肥230027 [3]中国科学院计算技术研究所烟台分所烟台中科网络技术研究所,烟台264670

出　　处：《高技术通讯》2013年第12期1213-1218,共6页Chinese High Technology Letters

基　　金：国家自然科学基金(60975045);国家科技支撑计划(2011BAH11B01);中科院先导专项(XDA06030)资助项目

摘　　要：研究了分布式哈希表(DHT)结构化P2P网络下,采用局部敏感哈希(LSH)方法进行相似检索时的负载均衡问题。考虑到LSH方法在高维空间下可以有效地进行K近邻检索,近年来LSH逐渐扩展到DHT分布式P2P网络下处理分布式相似检索问题,提出了一种采用虚拟节点方式管理多维度LSH桶空间的方法,将服从特定分布的多维LSH桶空间映射到DHT命名空间,以更好的负载均衡效果降低分布式环境下快速检索的性能损耗,优化查询效率。进而,以Chord结构为例,提出了基于虚拟节点的负载均衡具体算法。与其他方法相比,该方法能有效地改善节点负载均衡。通过实验验证了该方法的有效性。The load balancing and maintenance of the distributed similarity search using locality sensitive hashing（LSH） in structured P2P networks based on distributed hash table （DHT）were studied. Considering that LSH is proved efficient in K-Nearest Neighbor（KNN） search in high dimensions and a number of schemes are gradually used to implement LSH over DHT-based peer-to-peer systems to process the distributed similarity search, an efficient structure using virtual nodes to manage the multi-dimensional LSH bucket space in DHT peers was put forward to improve the searching efficiency and effectiveness in this scenario. Furthermore, a specific maintenance algorithm according to Chord structure was introduced. The algorithm can improve the load balancing in comparison with the state-of-the-art technique. The effectiveness of the proposed method was proved by experiment.

关 键 词：负载均衡 分布式哈希表(DHT) 局部敏感哈希(LSH) 虚节点 分布式相似检索 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]