基于MapReduce的信息检索相关算法并行化研究与实现
发布时间：2019-01-05 07:54
【摘要】：随着Internet的日益普及与迅速发展,互联网上的信息量呈几何级数增长,信息爆炸已成为当今网络时代的特征之一。作为访问互联网的重要入口,搜索引擎在帮助用户从浩如烟海的Internet中快速准确地获得所需信息方面起到了日益重要的作用,人们的生产生活已经越来越依赖搜索引擎。搜索引擎检索的对象是整个互联网上的全部数据,包括网页、图片、音乐、视频、FTP资源等。这些海量的数据对信息检索系统的高效运行提出了新的挑战：一方面,单台计算机的处理能力受到CPU时钟频率、内存容量、磁盘读写速度和网络带宽等因素的制约,无法在理想的时间内独自处理全部的数据；另一方面,这些海量数据并非存储在单台计算机上或者单个数据库中,而是分布在整个Internet上,这就需要成千上万台计算机以“相互合作”的方式对这些海量数据进行处理。因此,为搜索引擎设计能够高效地处理海量Internet数据的并行算法成为了学术界和工业界共同的研究方向与追求目标。在过去的数十年中,并行计算领域的研究取得了长足的进步,一些经典的并行计算平台相继出现,如MPI、OpenMP、OpenCL、CUD A等,特别是Google于2004年提出的MapReduce并行计算模型,以其良好的可扩展性、可靠性和易用性,为并行计算提供了简单、高效的计算模型和运行环境,降低了并行计算从理论向应用转化的难度,为并行计算的实际应用提供了一个简单易用的平台。 信息检索领域的传统算法发展至今已日趋成熟,然而,有些算法并非是专为并行环境设计的,面临着无法直接处理大规模的海量数据或者无法在有效的时间内完成对海量数据的计算的窘境。因此,如果能够将这些算法加以改造,使其能够分布在多台计算机上并行地运行,则可以大大提高对海量数据的处理效率,更加快速地响应人们的搜索需求,改善用户的搜索体验。在信息检索领域中,查询推荐(Query Suggestion)与网页排序(Page Rank)是两项重要的研究内容：查询推荐可以帮助用户更加精确有效地查询并节省搜索时间,而网页排序则可以改善搜索质量、帮助用户更容易地找到所需的网页。如果能够对这两个领域中的一些串行算法进行并行化改造,使其能够并行地运行于计算机集群中,则能够有效提升搜索引擎对大规模数据的处理能力,加快搜索引擎在查询推荐和网页排序方面的更新速度,提高用户对检索的满意度。 本文研究了查询推荐领域的QUBIC算法和基于频繁项集挖掘的网页排序算法,以对海量Internet数据的并行处理作为研究背景,基于MapReduce并行计算模型对QUBIC算法和基于频繁项集挖掘的网页排序算法进行了并行化改造,使得QUBIC算法和基于频繁项集挖掘的网页排序算法能够运行于MapReduce并行计算框架之中,并利用Hadoop并行计算软件框架实现了一个原型系统。具体而言,本文的主要研究工作包含以下方面： (1)对QUBIC算法进行基于MapReduce模型的并行化改造,提出了数据分布和并行计算的具体方法,包括：搜索引擎日志文件的分布存储,Query-URL二部图的构造,Jaccard相似系数的计算,QAG的生成,QAG中连通分量的计算以及对Query的排序。 (2)对传统的SON频繁项集挖掘算法进行基于MapReduce模型的并行化改造,提出频繁项集并行挖掘的PSON算法,并将其应用于对频繁URL的挖掘。在计算出搜索引擎返回结果中关联性较大的一组URL后,按照其重要程度降序呈现给用户。 本文在Hadoop并行计算平台上实现了本文对原算法进行并行化改造的思想,并进行了实验。实验表明,本文提出的对相关算法进行并行化改造的方法是行之有效的,并且具有良好的可扩展性能和加速比性能。最后,本文实现了一个原型系统,从整体上演示了QUBIC并行算法和频繁URL并行挖掘算法的运行效果,验证了这两类算法的正确性和有效性。
[Abstract]:With the increasing popularity and rapid development of the Internet, the amount of information on the Internet has been increasing, and the information explosion has become one of the features of the current network era. As an important gateway to the Internet, the search engine has played an increasingly important role in helping users to quickly and accurately obtain the required information from the Internet, such as the smoke and sea, and people's production life has become more and more dependent on the search engine. The object retrieved by the search engine is all the data on the whole Internet, including web pages, pictures, music, videos, FTP resources, and so on. These massive data pose a new challenge to the efficient operation of the information retrieval system. On the one hand, the processing power of a single-stage computer is restricted by factors such as CPU clock frequency, memory capacity, disk read-write speed and network bandwidth. it is not possible to process all of the data on its own within an ideal time; on the other hand, these mass data are not stored on a single computer or in a single database, but distributed across the internet, This requires thousands of computers to process these mass data in 鈥渕utual cooperation鈥，
本文编号：2401495
[Abstract]:With the increasing popularity and rapid development of the Internet, the amount of information on the Internet has been increasing, and the information explosion has become one of the features of the current network era. As an important gateway to the Internet, the search engine has played an increasingly important role in helping users to quickly and accurately obtain the required information from the Internet, such as the smoke and sea, and people's production life has become more and more dependent on the search engine. The object retrieved by the search engine is all the data on the whole Internet, including web pages, pictures, music, videos, FTP resources, and so on. These massive data pose a new challenge to the efficient operation of the information retrieval system. On the one hand, the processing power of a single-stage computer is restricted by factors such as CPU clock frequency, memory capacity, disk read-write speed and network bandwidth. it is not possible to process all of the data on its own within an ideal time; on the other hand, these mass data are not stored on a single computer or in a single database, but distributed across the internet, This requires thousands of computers to process these mass data in 鈥渕utual cooperation鈥，
本文编号：2401495
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/2401495.html
