论文部分内容阅读
近年来,随着地理信息数据的大量积累,web2.0时代社交网络,地理信息查询系统,基于地理信息的移动应用等相关产品的飞速发展,空间关键词查询方法和基于空间关键词查询的应用逐渐成为研究的焦点。在实际应用中,各类空间查找产品、查找服务的使用对象都对数据获取和服务使用的实时性有较高的要求。传统的技术方案往往是基于特定索引结构的单机查询算法,存在求解时间长、索引创建时间长、索引维护困难等问题,难以满足现实的服务需求。如何在海量空间信息中快速近实时的查找目标信息,是本课题研究的重点。本文以Spark RDD并行化处理模型为基础,设计了两种基于RDD并行化处理模型的空间关键词查询算法,引入了Grid索引机制减少IO提高查找效率。对查询算法的设计、结构、索引的建立和维护进行了详细的阐述,最后通过多组实验验证并对比评价了算法的有效性、快速性、可扩展性。论文主要成果如下:(1)提出了一种解决Min_Sum空间关键词查找问题的半并行化算法。本文在深入研究空间数据特点与并行化空间数据查找理论基础之上,结合基于内存的Spark RDD模型的并行化处理优势,提出了一种基于数组编码匹配的半并行化Min_Sum查询算法。给出了算法的描述、结构、实例。(2)针对IO问题的优化,提出了一种Grid索引方案。通过对传统集中式查询方案和半并行化查找算法在性能与IO上的对比和分析,提出了一种基于Spark RDD模型的并行化索引构建方法。描述了索引的构建过程、维护方法、使用方法。(3)提出了基于Grid索引方案的两阶段Min_Sum空间关键词查询算法。在查询关键词数量小于一定阈值的条件下,通过引入索引机制,大幅降低系统IO,使算法性能得到提高。给出了两阶段算法的描述、结构。(4)提出了一种解决Max Sum_CoSKQ空间关键词查找问题的并行化算法。针对常见空间关键词查询的另一个问题的深入研究,结合Spark RDD模型的变量共享机制、数据可重用机制、笛卡尔积的并行化处理优势,提出了一种并行化的、“查询关键词数”不敏感的查找算法。给出了算法的描述、结构、实例,最后探讨了引入Grid索引结构的MaxSum_CoSKQ算法的相关定义和执行过程,给出了一种解决MaxSum_CoSKQ变种问题Dia_CoSKQ问题的设想草案。(5)针对两种查询算法进行了分组实验并分析了算法的性能、索引的性能、存在的不足。通过AWS EC2集群对上述算法进行了分组实验,测试了算法的运行速度、减少系统IO后算法的运行速度以及算法可扩展性实验,最后对实验结果进行了总结分析和客观评价。