摘要
大规模数据集的最近邻检索,目前逐渐成为计算机领域中一个重要问题.采用一种分布式对等索引结构,对海量数据集进行最近邻检索.通过采用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.
出处
《小型微型计算机系统》
CSCD
北大核心
2014年第4期765-769,共5页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(60975045)资助
国家科技支撑计划课题项目(2011BAH11B01)资助
中科院先导专项项目(XDA06030900)资助
