基于LSH的高维大数据k近邻搜索算法

doi:10.3969/j.issn.0372-2112.2016.04.022

电子学报 ›› 2016, Vol. 44 ›› Issue (4): 906-912.DOI: 10.3969/j.issn.0372-2112.2016.04.022

基于LSH的高维大数据k近邻搜索算法

王忠伟, 陈叶芳, 钱江波, 陈华辉

宁波大学信息科学与工程学院, 浙江宁波 315211

收稿日期:2014-12-24 修回日期:2015-09-20 出版日期:2016-04-25
- 通讯作者:
- 陈叶芳
- 作者简介:
- 王忠伟 男,1988年出生于河南商丘.宁波大学信息科学与工程学院硕士研究生,主要研究方向为大数据、数据挖掘. E-mail:huanfengwei@163.com
- 基金资助:
- 国家自然科学基金 (No.61472194,No.61572266); 浙江省自然科学基金 (No.LY13F020040); 宁波市自然科学基金 (No.2014A610023); "信息与通信工程"浙江省重中之重学科开放基金

LSH-Based Algorithm for k Nearest Neighbor Search on Big Data

WANG Zhong-wei, CHEN Ye-fang, QIAN Jiang-bo, CHEN Hua-hui

Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo, Zhejiang 315211, China

Received:2014-12-24 Revised:2015-09-20 Online:2016-04-25 Published:2016-04-25
- Supported by:
- National Natural Science Foundation of China (No.61472194, No.61572266); National Natural Science Foundation of Zhejiang Province, China (No.LY13F020040); Ningbo Natural Science Fund (No.2014A610023); Open Fund for Information and Communication Engineering --Top Priority Discipline of Zhejiang Province

摘要/Abstract

摘要：

局部敏感哈希(LSH)及其变体是解决高维数据k近邻(kNN)搜索的有效算法.但是,随着数据规模的日趋庞大,传统的集中式LSH算法结构已经不能够满足大数据时代的需求.本文分析传统LSH方案的不足之处,拓展AND-OR结构,提出通过索引而不比较原始数据直接实现高维大数据k近邻搜索算法C2SLSH.理论分析和实验证明,C2SLSH在分布式平台下具有稳定的可扩展性,在保证同等精确率的情况下,处理速度大约是现有方法的3倍.

关键词: 高维数据k近邻, 局部敏感哈希, MapReduce, 冲突计数排序

Abstract:

The locality sensitive hashing (LSH) and its variants are efficient algorithms to solve the k nearest neighbor (kNN) search problems on high-dimensional data.However,with the increase of large data size,the traditional centralized LSH algorithms cannot meet the challenge of the big data era.Based on a new AND-OR construction,this paper proposes an algorithm (called C2SLSH) for the k nearest neighbor search on big data.Different to the traditional algorithms,the C2SLSH can directly get the results from an index without having to compare the original data.The theoretical analysis and experimental results show that the algorithm has stable scalability on a distributed platform.Furthermore,it is faster than the conventional methods for about three times with the same accuracy rate.

Key words: kNN, LSH, MapReduce, collision counting sorting

中图分类号:

TP311.13

王忠伟, 陈叶芳, 钱江波, 等. 基于LSH的高维大数据k近邻搜索算法[J]. 电子学报, 2016, 44(4): 906-912.

WANG Zhong-wei, CHEN Ye-fang, QIAN Jiang-bo, et al. LSH-Based Algorithm for k Nearest Neighbor Search on Big Data[J]. Acta Electronica Sinica, 2016, 44(4): 906-912.

参考文献

[1] Shi J R,et al.Metric learning for high-dimensional tensor Data[J].Chinese Journal of Electronics,2011,20(3):495-498.
[2] 巩敦卫,王更星,孙晓燕.高维多目标优化问题融入决策者偏好的集合进化优化方法[J].电子学报,2014,42(5):933-939. GONG Dun-wei,WANG Geng-xing,SUN Xiao-yan.Set-based evolutionary optimization algorithms integrating decision-maker's preferences for many-objective optimization problems[J].Acta Electronica Sinica,2014,42(5):933-939.(in Chinese)
[3] 赵永威,郭志刚,李弼程,等.基于随机化视觉词典组和上下文语义信息的目标检索方法[J].电子学报,2012,40(12):2472-2480. ZHAO Yong-wei,GUO Zhi-gang,LI Bi-cheng,et al.Object retrieval method based on randomized visual dictionaries and contextual semantic information[J].Acta Electronica Sinica,2012,40(12):2472-2480.(in Chinese)
[4] Guttman A.R-trees:A Dynamic Index Structure for Spatial Searching[M].USA:ACM Press,1984.
[5] Bentley J L.K-d trees for semidynamic point sets[A].Proceedings of the Sixth Annual Symposium on Computational Geometry[C].USA:ACM Press,1990.187-197.
[6] Gionis A,Indyk P,Motwani R.Similarity search in high dimensions via hashing[A].Proceedings of the 25th International Conference on Very Large Data Bases[C].USA:VLDB Press,1999,Vol 99.518-529.
[7] Indyk P,Motwani R.Approximate nearest neighbors:towards removing the curse of dimensionality[A].Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing[C].USA:ACM Press,1998.604-613.
[8] Qian Jiangbo,Zhu Qiang,Chen Huahui.Multi-granularity locality-sensitive bloom filter[J].IEEE Transactions on Computers,2015,64(12):3500-3514.
[9] Lv Q,Josephson W,Wang Z,et al.Multi-probe LSH:efficient indexing for high-dimensional similarity search[A].Proceedings of the 33rd International Conference on Very Large Data Bases[C].USA:VLDB Endowment Press,2007.950-961.
[10] 龙柏,孙广中,熊焰,陈国良.一种基于多核机群架构的混合索引结构[J].电子学报,2011,39(2):275-279. LONG Bai,SUN Guang-zhong,XIONG Yan,CHEN Guo-liang.A hybrid index structure based on multi-core cluster[J].Acta Electronica Sinica,2011,39(2):275-279.(in Chinese)
[11] Gan Junhao,et al.Locality-sensitive hashing scheme based on dynamic collision counting[A].Proceedings of the ACM SIGMOD International Conference on Management of Data[C].USA:ACM Press,2012.1-12.
[12] Hadoop:Open-source Implementation of mapreduce[OL].http://lucene.apache.org/hadoop/.2012.
[13] Koga H,Oguri M,Watanabe T.MIXED-LSH:Reduction of remote accesses in distributed locality-sensitive hashing based on L1-distance[A].Proceedings of IEEE 26th International Conference on Advanced Information Networking and Applications (AINA)[C].USA:IEEE Press,2012.175-182.
[14] Bahmani B,Goel A,Shinde R.Efficient distributed locality sensitive hashing[A].Proceedings of the 21st ACM International Conference on Information and Knowledge Management[C].USA:ACM Press,2012.2174-2178.
[15] Panigrahy R.Entropy based nearest neighbor search in high dimensions[A].Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm[C].USA:ACM Press,2006.1186-1195.
[16] Datar M,Immorlica N,Indyk P,et al.Locality-sensitive hashing scheme based on p-stable distributions[A].Proceedings of the Twentieth Annual Symposium on Computational Geometry[C].USA:ACM Press,2004.253-262.
[17] Rajaraman A,Ullman J D.Mining of Massive Datasets[M].England:Cambridge University Press,2011.
[18] LabelMe,the Open Annotation Tool[OL].http://labelme.csail.mit.edu.
[19] Python Version of Matlab Code for Accessing the Tiny Image Dataset[OL].http://horatio.cs.nyu.edu/mit/tiny/data/index.html.
[20] Pan J,Manocha D.Bi-level locality sensitive hashing for k-nearest neighbor computation[A].Proceedings of IEEE 28th International Conference on Data Engineering (ICDE)[C].USA:IEEE Press,2012.378-389.
[21] Stupar A,Michel S,et al.Rankreduce processing k-nearest neighbor queries on top of mapreduce[A].Proceedings of the 8th Workshop on Large-Scale Distributed Systems for Information Retrieval[C].USA:ACM Press,2010.13-18.
[22] Tao Y,Yi K,et al.Efficient and accurate nearest neighbor and closest pair search in high-dimensional space[J].ACM Transactions on Database Systems (TODS),2010,35(3):20.
[23] Zhang C,Li F,Jestes J.Efficient parallel kNN joins for large data in mapreduce[A].Proceedings of the 15th International Conference on Extending Database Technology[C].USA:ACM Press,2012.38-49.

基于LSH的高维大数据k近邻搜索算法

LSH-Based Algorithm for k Nearest Neighbor Search on Big Data

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

[1]	吕品, 李全刚, 柳厅文, 宁振虎, 王玉斌, 时金桥, 方滨兴. 基于双向LSTM的误植域名滥用检测方法[J]. 电子学报, 2018, 46(9): 2081-2086.
[2]	丁琳琳, 崔子强, 尹显坤, 王俊陆, 宋宝燕. 基于MapReduce的增广动态Skyline查询处理方法[J]. 电子学报, 2018, 46(5): 1062-1070.
[3]	米允龙, 李金海, 刘文奇, 林晶. MapReduce框架下的粒概念认知学习系统研究[J]. 电子学报, 2018, 46(2): 289-297.
[4]	李灿, 钱江波, 董一鸿, 陈华辉. M2LSH:基于LSH的高维数据近似最近邻查找算法[J]. 电子学报, 2017, 45(6): 1431-1442.
[5]	梁俊杰, 李凤华, 刘琼妮, 尹利. MapReduce框架下的优化高维索引与KNN查询[J]. 电子学报, 2016, 44(8): 1873-1880.
[6]	赵卓峰, 丁维龙, 张帅. 海量车牌识别数据集上基于时空划分的旅行时间计算方法[J]. 电子学报, 2016, 44(5): 1227-1233.
[7]	黄震华. 云环境下top-n推荐算法[J]. 电子学报, 2015, 43(1): 54-61.
[8]	黄龙涛, 邓水光, 戴康, 李莹, 尹建伟. 基于MapReduce的并行Web服务自动组合[J]. 电子学报, 2012, 40(7): 1397-1403.
[9]	李建江;崔健;王聃;严林;黄义双. MapReduce并行编程模型研究综述[J]. 电子学报, 2011, 39(11): 2635-2642.