空间数据库中基于MapReduce的kNN算法研究

来源 :大连海事大学 | 被引量 : 19次 | 上传用户:qqqq_eeqg
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,随着基于位置的服务(LBS)和移动互联网的快速发展,地理空间数据的数据量正在迅猛的增长。这些迅速增加的空间数据给传统的空间数据索引机制带来了新的问题,而这些传统的索引方法往往是基于内存的或者需要优化的磁盘访问的先决条件。因此,如何实现高效的空间索引和查询处理大规模空间数据成为云计算环境应用的新的需求和挑战。一种可扩展的、分布式的空间数据索引技术不失为进行高效空间数据的查询和分析的最佳选择。现在已经有几种将空间分布式索引和查询处理技术与MapReduce相结合的方法,例如R-树和基于泰森多边形的空间索引。然而,R-树不适合进行平行化,基于泰森多边形索引的查询需要额外的查询点定位和局部索引重建计算。本文对空间数据索引和查询方法存在的问题进行了研究,提出了一种改进的方法。本文首次尝试设计了一种云环境下的倒排网格索引和在该索引基础上进行的基于MapReduce的空间kNN查询。本文所做的主要工作如下:(1)针对二维空间中的数据点,本文设计了一种分布式的倒排网格索引方法,该索引方法完全符合空间数据索引的标准一动态性和简单性。由于倒排网格索引具有松耦合和无共享的特殊结构,所以该索引比较适合基于MapReduce的大规模空问数据的并行查询。(2)本文提出了一种基于MapReduce的空间倒排网格索引的建立方法和在该索引基础上的并行kNN查询算法MRCircleTrip。另外,本文还给出了算法在收敛性上的数学证明,以证明算法循环停止条件的准确性。(3)为了验证本文所设计的索引结构的可扩展性和kNN查询算法的性能,本文在建立倒排网格索引和kNN空间查询方面做了大量的实验。实验结果表明,本文所提出的索引的建立时间明显低于建立R-树和泰森多边形索引的时间,同时在可扩展性上该索引也优于其他两种索引;本文所提出的并行kNN算法在处理空间查询时至少比基于泰森多边形索引的算法快三倍。
其他文献
当今社会,化石能源的逐渐枯竭使得能源危机的发生不可避免,开发利用可再生能源,走可持续发展道路是人类的必经之路。太阳能拥有其他清洁能源不可比拟的优势,必将在21世纪成为新能
智能监控是未来监控行业的发展趋势,人流量统计在智能监控领域具有重要的意义,但由于背景环境的复杂性、行人运动过程中出现遮挡问题导致当前方法准确率不高,此外传统过线统
随着红外热像仪制作工艺的进步以及计算机科学技术的快速发展,红外热图像以及基于红外热图像的三维温谱图重构技术将会越来越广泛地应用到实际生活当中。基于红外热图像的三
在进行常识推理时,人们从外界获得的新信念往往会与原信念集中的一些信念产生矛盾。面对不一致信念,如何对信念集进行协调性维护,这是常识推理中一个关键性问题。目前,对不一
随着计算机技术和互联网技术的飞速发展和广泛运用,数字多媒体在人们日常生活中的使用日趋频繁。计算机强大的处理能力使多媒体信息的存储、复制、传播和修改变得非常方便的
现代社会,Internet的应用越来越普及,我们通过何种方式快速从海量的图像中搜索自己所需图像显得非常重要。基于内容的图像检索技术就是为了适应海量图像数据的存取和查询操作而
文本倾向性分类是数据挖掘、模式识别和智能信息处理领域的前沿研究课题,其主要任务是根据文本中主观信息所反映的语气色彩倾向判断出其相对的情感色彩的倾向极性。支持向量
随着软件开发技术的成熟与应用的普及,软件质量的保证面临新的挑战,同时也彰显了软件测试的重要性。近年来,面向对象的技术的发展,使基于UML的软件测试已成为一个重要的研究课题
随着当今信息科学技术的发展,对于信息安全的保障也有了更加迫切的需求。当前通常用于信息安全保障方法主要有,入侵检测,防火墙以及其他的信息安全技术。保障网络安全的其中一种
复句关系词自动标识系统主要完成对复句的处理,标识复句中隐藏的关系词、关系词搭配以及语义。早期研究汉语复句的专家学者都是依靠自己的学识和思维,讨论并总结复句中隐藏的