论文部分内容阅读
随着数据规模的日益扩大和数据类型的日益复杂,人类已经进入了大数据时代。一方面,各类场景和应用程序的可用数据量在急剧增加,另外一方面,传统的数据处理技术已经难以处理这些规模巨大的急剧增加的原始数据,这给数据处理技术带来了严峻的挑战,如何才能挖掘用户所需要的有效信息,迫切需要提出更加快速而有效地查询优化技术。排名查询,也称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,并实验测试本文所提算法的性能。实验表明,该算法具有较好的性能和良好的可扩展性。