一种可扩展的面向海量数据高维最近邻检索的对等索引结构  

A Scalable Peer-to-Peer Indexing Scheme for High Dimensional Nearest-neighbor Search in Massive Datasets

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

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

出　　处：《小型微型计算机系统》2014年第4期765-769,共5页Journal of Chinese Computer Systems

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

摘　　要：大规模数据集的最近邻检索,目前逐渐成为计算机领域中一个重要问题.采用一种分布式对等索引结构,对海量数据集进行最近邻检索.通过采用lp范数下的局部敏感哈希算法对高维空间的数据进行相似检索,并利用典型的哈希算法与不均匀Hilbert曲线结合,将高维的局部敏感哈希数据桶空间映射到一维DHT索引空间.系统设计时同时考虑相似性检索和P2P网络维持的需求,索引本身具备局部敏感特性,以及DHT网络的负载均衡能力.文中将展示如何利用局部敏感哈希有效地在P2P网络中执行最近邻搜索问题.实验基于真实数据,进一步验证本方法的有效性,以及扩展性上相比于其他方法的优势.Nearest-Neighbor （ NN ） search is an increasingly important problem in many computer applications, in which high dimen- sional massive datasets are involved. In this paper, we propose a P2P distributed indexing scheme to perform NN search in massive datasets. We consider the locality sensitive hashing （ LSH ） scheme under lp-metric to support similarity search in high dimensional space and we put forward a novel mapping from the multi-dimensional LSH bucket space to the one dimension DHT key space using non-uniform Hilbert Curve. We consider the requirements of both similarity search and the maintenance of P2P network. Our inde- xing scheme preserves the locality sensitive property of LSH indexes and guarantees load balance in DHT networks. We also show how to leverage the LSH indexing scheme to efficiently process NN search in P2P network. Experiments on real world data confirm the effectiveness and efficiency of our approach and show the scalability gains compared to state-of-the-art schemes.

关 键 词：最近邻搜索 局部敏感哈希 分布式哈希表 HILBERT曲线 

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