一种高维大数据全k近邻查询算法

doi:10.11959/j.issn.1000-0801.2015171

摘要/Abstract

摘要：

全k近邻（all k-nearest neighbor，AkNN）查询，是k近邻查询的一个变型，旨在在一个查询过程中为给定数据集的每个对象确定k个最近邻。提出了一种在Hadoop分布式平台下处理高维大数据的AkNN查询算法。首先使用行条化思想结合p-stable LSH算法将高维数据对象降维，然后结合空间填充曲线Z-order的优良特性，把降维后的数据嵌入一维空间中，接着进行范围查询。整个过程使用MapReduce框架分布式并行处理。实验结果表明，所提出的算法可以高效处理高维大数据的AkNN查询。

关键词: 高维, AkNN, MapReduce, 行条化, 局部敏感散列, Z-order

Abstract:

A new variant of k nearest neighbor queries，which called as all k-nearest neighbor queries（AkNN），is a process to search the k nearest neighbors of each object in a data set.An AkNN query algorithm for high-dimensional big data on the Hadoop system was proposed.Using the banding technique and the p-stable LSH algorithm，dimensionality reduction was performed，then the data was embeded in a Z-order curve.The preprocessed data were continued to be treated on a MapReduce framework in a distributed parallel manner.Experimental results show that the proposed algorithm can efficiently handle AkNN queries for large-scale high-dimensional data.

Key words: high-dimensional, AkNN, MapReduce, banding, locality sensitive hashing, Z-order

王忠伟,陈叶芳,肖四友,钱江波. 一种高维大数据全k近邻查询算法[J]. 电信科学, 2015, 31(7): 52-62.

Zhongwei Wang,Yefang Chen,Siyou Xiao,Jiangbo Qian. An AkNN Algorithm for High-Dimensional Big Data[J]. Telecommunications Science, 2015, 31(7): 52-62.

图/表 8

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 22

1	B?hm C ， Krebs F . k-nearest neighbour join：Turbo charging the KDD process. Knowledge and Information Systems， 2004，6（6）： 728～749
2	Xia C ， Lu H ， Ooi B C ，et al. Gorder：an efficient method for kNN join processing. Proceedings of the 30th International Conference on Very Large Data Bases， Toronto，Canada， 2004： 756～767
3	Yu C ， Cui B ， Wang S ，et al. Efficient index-based kNN join processing for high-dimensional data. Information and Software Technology， 2007，49（4）： 332～344
4	Chen Y ， Patel J M Efficient evaluation of all-nearest-neighbor queries. Proceedings of the 23rd International Conference on Data Engineering， Istanbul，Turkey， 2007： 1056～1065
5	Emrich T ， Graf F ， Kriegel H P ，et al. Optimizing all-nearestneighbor queries with trigonometric pruning. Lecture Notes in Computer Science， 2010（6187）： 501～518
6	Zhang J ， Mamoulis N ， Papadias D ，et al. All-nearest-neighbors queries in spatial databases. Proceedings of the 16th International Conference on Scientific and Statistical Database Management， Santorini Island，Greece， 2004： 297～306
7	Kouiroukidis N ， Evangelidis G . The effects of dimensionality curse in high dimensional kNN search. Proceedings of 15th Panhellenic Conference on Informatics （PCI）， Gastonia，USA， 2011： 41～45
8	Weber R ， Schek H J ， Blott S . A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. Proceedings of the 24rd International Conference on Very Large Data Bases， New York，USA， 1998： 194～205
9	Arya S ， Mount D M ， Netanyahu N S ，et al. An optimal algorithm for approximate nearest neighbor searching fixed dimensions.Journal of the ACM（JACM）. Journal of Artificial Intelligence Research， 1998，45（6）： 891～923
10	Indyk P ， Motwani R . Approximate nearest neighbors：towards removing the curse of dimensionality. Proceedings of the 30th Annual ACM Symposium on Theory of Computing， Dallas，Texas，USA， 1998： 604～613
11	Hadoop. ， 2015
12	Afrati F N ， Ullman J D . Optimizing joins in a MapReduce environment. Proceedings of the 13th International Conference on Extending Database Technology，Palais de Beaulieu， Lausanne，Switzerlan， 2010： 99～110
13	Jiang D ， Tung A ， Chen G . Map-join-reduce：toward scalable and efficient data analysis on large clusters. IEEE Transactions on Knowledge and Data Engineering， 2011，23（9）： 1299～1311
14	Vernica R ， Carey M J ， Li C . Efficient parallel set-similarity joins using MapReduce. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data， Indianapolis，Indiana，USA， 2010： 495～506
15	Zhang C ， Li F ， Jestes J . Efficient parallel kNN joins for large data in MapReduce. Proceedings of the 15th International Conference on Extending Database Technology， Berlin，Germany， 2012： 38～49
16	Rajaraman A ， Ullman J D . Mining of Massive Datasets. Cambridge： Cambridge University Press， 2011
17	Datar M ， Immorlica N ， Indyk P ，et al. Locality-sensitive hashing scheme based on p-stable distributions. Proceedings of the 20th Annual Symposium on Computational Geometry， New York，USA， 2004： 253～262
18	Tao Y ， Yi K ， Sheng C ，et al. Quality and efficiency in high dimensional nearest neighbor search. Proceedings of the 35th SIGMOD International Conference on Management of Data， Providence，Rhode Island，USA， 2009： 563～576
19	Labelme. ， 2015
20	Fergus R ， Torralba A ， Freeman W T . Tiny Images Dataset. ， 2015
21	Pan J ， Manocha D . Bi-level locality sensitive hashing for k-nearest neighbor computation. Proceedings of the 28th International Conference on Data Engineering（ICDE）， Washington DC，USA， 2012： 378～389
22	Spark. ， 2015

[1]	王源,江昊,吴明,姚冬桂,张毅,羿舒文,汪海,吴静. 基于用户移动网络接入位置的高效分布式相似矩阵计算方法[J]. 电信科学, 2018, 34(5): 26-38.
[2]	李昊奇,应娜,郭春生,王金华. 基于深度信念网络和线性单分类SVM的高维异常检测[J]. 电信科学, 2018, 34(1): 34-42.
[3]	钱途,钱江波,董一鸿,陈华辉. SLSB-forest：高维数据的近似k近邻查询[J]. 电信科学, 2017, 33(9): 58-68.
[4]	彭聪,钱江波,陈华辉,董一鸿. 基于加权自学习散列的高维数据最近邻查询算法[J]. 电信科学, 2017, 33(6): 73-85.
[5]	赵会敏,雒江涛,杨军超,徐正,雷晓,罗林. 集成BP神经网络预测模型的研究与应用[J]. 电信科学, 2016, 32(2): 60-67.
[6]	任建新,陈华辉. 一种自适应子空间相似性搜索方法[J]. 电信科学, 2015, 31(7): 63-74.
[7]	方艾,徐雄,梁冰,张玉忠,杨翊平. 主流大数据处理开源架构的分析及对比评测[J]. 电信科学, 2015, 31(7): 152-157.
[8]	许金凤,董一鸿,王诗懿,何贤芒,陈华辉. 大规模图数据划分算法综述[J]. 电信科学, 2014, 30(7): 100-106.
[9]	单观敏,董一鸿,何贤芒. 基于MapReduce的连续SkyIine查询[J]. 电信科学, 2014, 30(5): 94-104.
[10]	刘勇,雒江涛,邓生雄,王小平. 基于Hadoop的网络分流和流特征计算[J]. 电信科学, 2014, 30(12): 76-81.
[11]	陶彩霞,谢晓军,陈康,郭利荣,刘春. 基于云计算的移动互联网大数据用户行为分析引擎设计[J]. 电信科学, 2013, 29(3): 27-31.
[12]	吴斌,刘心光. 一种基于改进的链式MapReduce的并行ETL应用[J]. 电信科学, 2013, 29(12): 1-8.
[13]	唐宏. 基于MapReduce的大规模流量分析系统的设计[J]. 电信科学, 2013, 29(12): 155-157.
[14]	周国亮,朱永利,王桂兰. CC-MRSJ:Hadoop平台下缓存敏感的星型联接算法[J]. 电信科学, 2013, 29(10): 31-37.
[15]	黎宏剑,刘恒,黄广文,卜立. 基于Hadoop的海量电信数据云计算平台研究[J]. 电信科学, 2012, 28(8): 80-85.