基于MapReduce的top-k查询算法研究

来源 :中国海洋大学 | 被引量 : 0次 | 上传用户:lijun1111
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着数据规模的日益扩大和数据类型的日益复杂,人类已经进入了大数据时代。一方面,各类场景和应用程序的可用数据量在急剧增加,另外一方面,传统的数据处理技术已经难以处理这些规模巨大的急剧增加的原始数据,这给数据处理技术带来了严峻的挑战,如何才能挖掘用户所需要的有效信息,迫切需要提出更加快速而有效地查询优化技术。排名查询,也称top-k查询,是各种复杂数据查询中的一种。它一般通过一个聚合得分函数,计算所有对象的得分,返回得分值最高的前k个对象。Top-k查询应用于很多领域,如信息检索、多媒体数据库、数据挖掘、网络搜索等。对很多交互式系统来说,高效的top-k查询也是至关重要的。Top-k查询问题还涉及到诸多数据库处理技术,包括索引技术、查询优化等。由于高效的top-k查询应用的广泛性,而得到了越来越多的关注,也成为数据查询优化领域的一大研究热点,具有十分重要的理论价值和非常广阔的应用前景。大数据时代的严峻挑战,也给top-k查询处理技术带来新的瓶颈。面对大规模的数据,传统的数据库管理技术不再适用,新的巨大数量的分布式系统,同时也导致了传统数据查询算法的不再适用。此外,top-k查询算法对性能的要求较为严苛,尤其是对很多实时性系统来说,通信代价和时间代价都必须是有限的。因此适用于大规模数据的高效的top-k迫切需要提出。目前,学术界和社会各界都对top-k查询算法进行了大量的研究。应用于集中式数据库和规模较小的分布式系统的top-k算法已经趋于成熟。适用于集中式数据库上的比较典型的算法有FA(Fagin Algorithm)和TA(Threshold Algorithm)。而小规模分布式系统上的比较成熟的算法大多是对TA算法的改进。但是针对数据巨大的分布式系统来说,这些算法不再适用。本文对应用于大规模数据的top-k查询算法进行了设计和研究。借鉴传统top-k查询处理技术的优点,并采用并行编程模型MapReduce,提出了一种基于MapReduce的top-k查询算法。该算法是一种预处理算法,需要预先建立全局索引表COIT(Candidate Objects Index Table),全局索引表COIT的建立大幅度减少了节点间数据交换,大大提高了top-k查询的效率。而MapReduce的引入,提高了算法的并行度,实现了算法的线性扩展能力。此外,本文还搭建了MapReduce的开源实现平台Hadoop,并实验测试本文所提算法的性能。实验表明,该算法具有较好的性能和良好的可扩展性。
其他文献
PID控制器以其自身的优点在工业控制领域应用非常广泛,免疫算法是基于人工免疫理论,在遗传算法的基本框架之上结合免疫算子而形成的一种新型优化算法,本文深刻分析了免疫算法
流程管理是 PDM 系统中实施业务过程管理与过程控制的一项关键技术。为了从整体上提高产品设计的效率,降低设计成本,提高产品业务管理水平和竞争力,需要把产品数据管理技术与
随着中国数字娱乐产业的发展,三维游戏引擎系统已开始成为众多关注和较快发展的VR应用技术之一,然而相对于美国、日本等国家而言,我国对三维游戏引擎技术的研究还比较滞后。
随着计算机技术的迅猛发展,程序设计技术的不断成熟,模块化的设计要求已经不仅仅是出于程序编写规范性上的要求,人们越发的意识到把应用程序设计成一组彼此通信的小片段是比设计
在数据库系统中,查询速度的快慢直接影响到应用系统的生命力,其中连接作为关系数据库模型的一个基本的操作,将在不同的关系上进行,使用频率较高,执行的开销也很大,因此查询优
数据挖掘是目前国际上数据库和信息决策领域最前沿的研究方向之一。由于高维数据日益成为主流,在实际应用中经常会遇到高维数据的情况,对高维数据挖掘的研究有着越来越重要的意
随着互联网的快速发展,扩展标记语言(XML)由于支持半结构化数据,能够自描述、平台无关,已经迅速成为整合异构数据的标准。与此同时,对大量不断涌现的XML数据的有效存储也成为了研
实时数据库中的事务有严格的时间限制,如截止期。传统的数据库系统缺少支持实时事务的机制。为了满足实时数据库系统的要求,必须要有好的并发控制和调度策略。目前对实时数据
缓冲区溢出漏洞是目前软件面临最严重的安全漏洞。产生缓冲区溢出漏洞有两种原因,一是在软件开发过程中,程序员在编写程序时对缓冲区操作没有进行边界检测;二是在程序中调用
面对当前的动态系统、动态环境,需要用动态的安全模型、方法、技术和解决方案来应对当前的网络安全问题。入侵检测和防火墙技术是动态网络安全的重要组成部分,本文研究的入侵