基于mapreduce快速knnjoin方法

《基于mapreduce快速knnjoin方法》由会员分享，可在线阅读，更多相关《基于mapreduce快速knnjoin方法（11页珍藏版）》请在金锄头文库上搜索。

1、第 37 卷 计 算 机 学 报 Vol. 37 2014 论文在线出版号 No.16 CHINESE JOURNAL OF COMPUTERS Online Publishing No.16 本课题得到国家自然科学基金重大研究计划重点项目 （2012.12014.12） “面向非常规突发事件主动感知与应急指挥的物联网技术与系统” （编号：91124001）, 国家863“智慧城市”重大专项之子课题(2013.12015.12)”面向城市动态运行管理的大规模数据智能检索技术”（编号：2013AA01A603） , 中科院“感知中国”先导专项重点课题(2012.12016.12)”面向物理信息感

2、知的传感器时空数据管理与海云服务合成引擎研究”（编号：XDA06020600），中科院战略性科技先导专项课题（编号：XDA06010600）资助.戴健戴健，男，1983年生，博士研究生,主要研究领域为大规模时空数据管理及数据挖掘，E-mail: .丁治明丁治明，男，1966年生，博士，研究员，博士生导师，主要研究领域为数据库与知识库系统、时态与空间数据库、物联网与云计算数据管理，E-mail:. 基于基于 MapReduceMapReduce 快速快速 kNN JoinkNN Join 方法方法 戴健1),2) 丁治明2) 1)(中国科学院大学 北京 100049) 2)(中国科学院软件研究所

3、 基础软件国家工程研究中心, 北京 100190) 摘摘 要要 kNN 连接是空间数据库领域一个基本而又重要的问题，被广泛地应用于多个其他领域。它对于提高众多实际应用的性能有着重要意义。随着目前参加 kNN 连接的数据集的增大和要求的响应时间的缩短（尤其在一些应急环境中） ，我们实际上对 kNN 连接的效率要求更高。然而，目前的方法大多基于单个进程或者单台机器，并不具有很好的伸缩性。为了解决这个问题，我们引入了 map-reduce 框架来运行 kNN join 并提出了两种新的方法：基于 map-reduce 的分布式网格概略化 kNN join(DSGMP-J)和基于 map-reduce

4、 的 voronoi diagram 下 kNN join(VDMP-J)。并把它们和最新的方法 H-BNLJ 进行了实验对比。实验结果证明了我们提出的 DSGMP-J 和 VDMP-J 方法具有较优的伸缩性。 关键词关键词 kNN 连接；大数据；MapReduce 中图法分类号中图法分类号 TP311 MapReduce Based Fast kNN Join DAI Jian1),2) DING Zhing-Ming2) 1 (University of Chinese Academy of Sciences, Beijing, 100049) 2 (National Fundamenta

5、l Software Research Center, Institute of Software, Chinese Academy of Science, Beijing 100190) Abstract kNN Join is a basic and important operation which is widely used in many fields. Hence, it plays a significant role in improving the efficiency of the applications in those fields. Nowadays, with

6、the rapid increase of data size and the requirement for shorter response time (especially in some emergency environments), people actually ask for a more efficient way to conduct kNN Join. However, conventional kNN join operation is mostly running on single computer and/or single process at present,

7、 which cannot provide enough scalability. To address this problem, we incorporate the map-reduce framework into the running of kNN join and propose two novel methods: distributed sketched grid based kNN Join using map-reduce (DSGMP-J) and voronoi diagram based kNN Join using map-reduce (VDMP-J). And

8、 compare them with a state-of-the-art method: hadoop block nested loop join (H-BNLJ). The experiment results prove that the DSGMP-J and the VDMP-J outperform the H-BNLJ in scalability. Key words kNN Join; big data; map reduce 计算机学报提前在线出版2 计 算 机 学 报 2014 年 1 引言 对很多应用而言， K 最近邻连接(kNN join)是一 个非常基本和关键的操

9、作。这些应用可能来自于知 识发现，数据挖掘和空间数据库等。 近些年随着移动应用的广泛发展， 相应地， kNN join 具有下面两个趋势：一方面，参与 kNN 连接的 数据集越来越大；另一方面，需要 kNN 返回结果 的响应时间越来越短。 传统地，很多 K 最近邻连接的算法是在单个进 程或者单台机器上执行。一般要求对其中一个集合 S的每个元素扫描一次另一个集合R的全部元素，这样，很容易导致计算复杂度为()O S R。虽然这样的算法在单进程或者单 cpu 上运行很好， 然而， 随着 K 最近邻连接的规模的增大和要求相应时间 的缩短，这些算法不能很好的伸缩，不能满足海量 动态数据场景下应用的需求。

10、 归根到底，为了能够快速响应大规模的 K 最近 邻连接，我们需要一个具有很好伸缩性，能够并行 的集群来进行 K 最近邻连接的计算。MapReduce 体系结构的设计采用了 divide-conquer 的方法，是 一个简单但是功能强大的并行和分布式计算架构。 同时，MapReduce 充分考虑了可扩展性。近年来， MapReduce 得到了来自工业界和学术界的众多支 持。在工业界，Google 公司内部,通过大规模集群 和MapReduce 软件,每天有超过20PB 的数据得到 处理,每个月处理的数据量超过 400PB。在数据分 析的基础上,Google 提供了围绕互联网搜索的一 系列服务(包

11、括地图服务、定向广告服务等)。如此 大规模的在线数据管理和分析,是传统的关系数据 管理技术所无法完成的。与此同时，在学术界，一 些数据库相关的重要国际会议上近年来也越来越 多出现使用 MapReduce 来进行大数据处理的方法。 MapReduce 已经成为了一个充满生命力的大数据 处理框架。 出于这些考虑，本文中我们用 MapReduce 贯穿 了所涉及到的三个 kNN 连接处理方法。首先，我 们介绍了局部暴力方法 H-BNLJ(Hadoop Block Nested Loop Join)方法，并把它作为了我们的 baseline 方法。然而，由于 2 次的 MapReduce 和过 多的传

12、输代价，随着数据集规模的增大，通讯代价 显著增加，H-BNLJ 的伸缩性并不好。然后，我们 思考并尝试了使用基于栅格的数据划分方式，同时使用分布式栅格索引对局部数据进行索引，提出了 DSGMR-J(Distributed Sketched Grid Join)方法。 实验 证明，这个栅格的划分方法加上分布式索引的方式 可以加速 kNN 连接的处理过程。但是，由于数据 的分布可能呈现出除均匀分布外的多种形式，因 此，栅格式划分并不能保证 kNN 连接结果的局部 性。换句话说，在大多数情况下，我们仍然需要 2 次的 MapReduce 才能得到 kNN 的结果。最后，我 们设计了一种基于 Voro

13、noi Diagram 的数据划分方 式，在此划分基础上，我们证明了合适的参数选择 可以提供一个很好的近似 kNN 连接结果。从而， 通过1次MapReduce可以得到kNN近似连接结果。 本文的组织方式如下。在第 2 节，我们形式化 定义了本文要解决的问题 kNN Join。第 3 节，我们 介绍了本文所涉及到的相关技术。第 4 节详细给出 了我们为了解决快速大规模 kNN 连接所采用的三 个方法。这三个方法的对比分析在第 5 节通过试验 结果进行了展示。 最后， 我们在第 6 节总结了全文。 2 问题定义 形式化地，设两个定义在d上的数据集R和 S。 这两个集合中的每个记录(sS)rR 都

14、是 一个d维空间的点。本文中，为了简单起见并不失 一般性，我们考察2d =的情况；同时，两个点之 间的距离使用他们的欧式距离来表示( , )d r s。 这样 ( , )knn r S返回 k 个属于 S 集合的最近邻r的点。 我们定义( , )knnJ R S为 R 和 S 的连接： ( , )(r,knn(r,S)|for all rRknnJ R S =。 3 相关技术介绍 3.1 MapReduce 作为一种广受关注和欢迎的编程模型， MapReduce 已经被成功地用在了众多大数据集的 并行处理程序中7-12。这些并行程序甚至可以很 好地扩展到上千台普通机器上。Hadoop 是一个流

15、 行的开源 MapReduce 实现。 它运行在 Hadoop 文件 系统 (HDFS)：一种分布式的存储系统之上。在 HDFS 中，一个大文件被拆分成很多大小固定的块 （不能整除的情况下会有一块碎片）并在计算机之 间进行分配。 而 MapReduce 是一种可以直接对这些 文件进行操作的框架。一般地，MapReduce 包含两 个由用户自定义的函数， 即map函数和reduce函数。计算机学报提前在线出版论文在线出版号 No.16 戴健等：基于 MapReduce 快速 kNN Join 方法 3 Map 函数用于把输入分块对应地转化为中间结果， 而 reduce 函数用于把中间结果进行提取

16、， 并进行归 纳合并计算得到最终的结果。 MapReduce 技术是一种简洁的并行计算模型, 它在系统层面解决了扩展性、容错性等问题,通过 接受用户编写的 Map 函数和 Reduce 函数,自动地 在可伸缩的大规模集群上并行执行,从而可以处理 和分析大规模的数据。形式化地， Map: 1122(k ,v )(k ,v )* Reduce: 223(k ,v )*v * 3.2 DSTR-Tree 从抽象模型的角度来看，移动对象的时空轨迹对应于XYT空间的一条曲线。在移动对象数 据库中往往需要对轨迹曲线进行离散化才能进行 进一步操作和处理。网络受限移动对象的动态概略 化 轨 迹 R 树 索 引 (Dynamic Sketched-Trajectory R-Tree for Network constrained Moving Objects, DSTR