基于Google S2算法的大规模实时查找与并行优化研究

来源 :湖南大学 | 被引量 : 0次 | 上传用户:xtgdscf
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,随着基于位置服务的移动物体如共享单车,共享汽车的兴起,如何迅速查找附近物体,逐渐成为人们交通出行的迫切需求。当海量用户打开app搜索附近区域的目标时,不仅要求系统及时反馈位置信息,而且对其查找的准确性有较高的要求。同时,在附近多目标查找领域中,传统的算法是根据经纬度公式通过三角函数转换来计算两地距离。这种方法比较耗费时间,开销也比较大;后来,出现了效率较高的Geohash算法,由于其局限性,导致在一些特殊的情况下查找出来的结果不准确,且没有与大数据平台结合,无法实现实时的精确查找。基于此,本文提出了基于Google S2的DS2-TopKF并行算法来实现大规模区域查找。论文详细介绍了相关算法的实现原理和系统的搭建过程,通过结合Flink、Kafka等分布式技术可实现对附近多目标的实时查找。论文的主要工作如下:1)研究了国内外分布式相关的技术文献,包括流式计算引擎Spark Streaming和Flink,结合并行化组件的特点,提出了针对附近多目标查找的大数据实时查询系统(BDRQS)的概念模型和框架,且详细介绍了BDRQS的功能和各个模块,包括数据采集模块、数据传输模块、数据计算模块、数据存储模块。2)优化了Google S2算法,设计了两点之间的距离与Google S2算法精度的映射函数,并结合TopK算法,提出了单机版的DS2-TopK查找算法,实验结果表明,该算法相较于Google S2算法,不仅可以帮助用户筛选前K个目标点,也更符合实际场景下用户的查询需求,同时为后续算法的并行化奠定了基础。3)将DS2-TopK查找算法与分布式平台Flink结合,设计了并行化的DS2-TopKF查找算法,为充分考虑算法的并行化因素,在实现过程中,从数据源并行加载、数据并行转换以及Checkpoint机制三个方面对其进行了优化。实验结果表明并行化的DS2-TopKF算法相较于单机版的DS2-TopK算法充分利用了节点之间的计算能力,不仅增加了数据的容错性,也极大地提高了数据并行计算的效率。4)搭建了基于Kafka、Flink和Redis的BDRQS大数据平台,利用Flink流计算功能,可实时计算并采集附近目标的数据,实现附近多目标实时查找系统。实验首先测试了BDRQS系统中关于Kafka集群的读写性能,接下来从算法的准确性、数据量的规模、并行度以及和Spark Streaming的对比情况这四个方面入手,实验结果表明,本文设计的BDRQS系统表现了较高的性能和良好的扩展性。
其他文献
随着移动网络和无线通信技术的快速发展,越来越多的以视频信息为载体的应用出现在了人们的日常生活中,视频应用占据了互联网中通信流量的绝大部分。庞大的视频流量和日益提升的视频质量要求为传统基于云计算的服务架构带来了严峻的挑战。一方面云端视频服务器的负载和带宽开销非常大,高质量视频的端到端传输为整个网络带来了巨大的回程传输压力;另一方面由于视频业务与移动网络的分离设计,视频业务难以感知到无线网络的实时状态
由于新时代生态文明建设的时代需要,高校生态道德教育也获得了新的关注,重视大学生对于人与自然关系的认知,并在日常的生活实践中寻求趋向自然的回归,自觉承担起生态文明建设的时代责任。在继农业文明、工业文明的人类社会历史进程中由于人类过分影响大自然的物质和能量循环,生态环境遭到了极大地破坏,生态文明是新形式下人类社会文明发展的必然选择。基于共生理论视角下大学生生态道德教育既契合新时代社会生态建设的现实需要
学位
伴随着严苛的柴油机排放法规发布以及智能船舶概念的推广,缸压闭环反馈控制开始广泛应用于船舶柴油机。但是,由于缸压传感器高昂的价格以及控制策略尚不完善,目前,船用柴油机缸压闭环控制技术仍处于研究和发展阶段。由于实机台架的复杂性、安全性和经济性的限制,缸压闭环控制策略的开发还停留在软件在环和硬件在环仿真平台,因而,以小型柴油机台架为对象,开发一套完整的缸压闭环控制系统快速原型,验证缸压闭环控制策略的可行
学位
目前,我国农业的发展方向发生了转变,从对人民的基本温饱进行满足,一味注重土地生产效率的提高,转向了以体现乡村的整体价值为目标,注重农村劳动生产率的提高。在传统农业向现代农业转型的同时,农业生产发展的低碳化、绿色化、健康化也应被纳入考量范围。近年来,云南省农业经济的增速位于全国前列,发展势头较为迅猛,农业在全省经济发展中的“压舱石”地位日益凸显。但其在发展过程中,同时存在着环境污染与资源浪费等农业环
学位
散货船运输开始于上世纪中期,经过多年的发展,散货船运输已经在航运业当中占据重要的地位。第二次世界大战后,由于全球对散装货物运输量的需求不断变大,再加上散货船本身具备的优势使得散货船运输得到了较快的发展。散货船相比其它货船的运输优势是船舶航线比较固定、单次航程的运输量大、装卸效率高。运输的独特性和便利性使散货船的运输占海运总量的较大比例。货物的装卸载工作是船舶运输生产中非常重要的一部分,随着散货船数
学位
miRNA是一类非编码RNA,与各种人类疾病的产生和发展密切相关。最近,高通量测序技术的的发展和一些大型生命科学项目的进行提供了丰富的组学数据和关联数据,为全面研究miRNA-疾病之间的关联提供了可能。从生物学角度,不同的生物分子之间的关联不是孤立的,而是相互影响和作用的。因此,整合不同分子数据类型来预测miRNA-疾病关联成为近年来热点。本文提出了两种预测疾病和miRNA关系的方法,主要的工作包
足够的体力活动能量消耗是保持良好身体素质的基础,对体力活动能耗的检测在科学运动、体育训练和临床医学领域均有较多的应用场景,因此开展体力活动能耗检测等方面的研究具有非常重大的社会意义和研究价值。人体从食物中摄取能量以供给身体的活动所需,而身体健康的基础是调整摄取的能量与消耗的能量处于相对平衡。饮食决定摄入的能量,运动决定能量的支出。本文计算了每天饮食摄入能量值、能量消耗中基础代谢和食物热效应能耗值,
车辆自组织网络(Vehicular Ad hoc Network,VANET)的特点是不依赖于固定的中心设施,由移动车辆,路边基础设施等来建立临时通信,其中路由算法的好坏决定了整个网络的性能。由于道路上车流量大且移动速度快,带来的网络拓扑结构的快速变化导致通信链路频繁断裂,也加大了能量资源的消耗。另一方面,考虑到对于信息处理的实时性的要求,如果将所有的信息处理都放在云平台去执行,很明显无法满足低延
随着经济的快速增长与人们日益增多的需求,管道及其系统被广泛应用于石化、城市供水/供气、核电等领域,在我国基础建设和经济发展中发挥了重要的作用。然而,在管道的使用过程中,管道容易出现损伤或缺陷,从而导致重大安全事故的发生,因此对管道的定期检测十分重要。本文主要对光纤分布式传感和深度学习这两大技术领域进行了理论方法和应用的创新,并构建传感平台对管道不同类型的损伤信号进行识别和分类。本课题的主要研究内容
以可靠性为中心的维修RCM技术是当前最先进的设备维修计划方案产生技术之一。当前支撑RCM分析的关键技术如FMEA,FMECA等的生成方法依然停留在人工阶段。该方法的缺点不仅耗时、耗力、容易出错、且不易于数据统计及管理。对于包含成千上万个组件的复杂系统而言,要实现快速且有效的FMECA分析是相当困难的。基于此,RCM应当受益于当前最先进的基于模型的系统工程方法。因此,本文创新性提出了一种基于模型的R
学位