發(fā)布時間：2019-01-05 07:54

【摘要】：隨著Internet的日益普及與迅速發(fā)展,互聯(lián)網(wǎng)上的信息量呈幾何級數(shù)增長,信息爆炸已成為當今網(wǎng)絡時代的特征之一。作為訪問互聯(lián)網(wǎng)的重要入口,搜索引擎在幫助用戶從浩如煙海的Internet中快速準確地獲得所需信息方面起到了日益重要的作用,人們的生產(chǎn)生活已經(jīng)越來越依賴搜索引擎。搜索引擎檢索的對象是整個互聯(lián)網(wǎng)上的全部數(shù)據(jù),包括網(wǎng)頁、圖片、音樂、視頻、FTP資源等。這些海量的數(shù)據(jù)對信息檢索系統(tǒng)的高效運行提出了新的挑戰(zhàn)：一方面,單臺計算機的處理能力受到CPU時鐘頻率、內(nèi)存容量、磁盤讀寫速度和網(wǎng)絡帶寬等因素的制約,無法在理想的時間內(nèi)獨自處理全部的數(shù)據(jù)；另一方面,這些海量數(shù)據(jù)并非存儲在單臺計算機上或者單個數(shù)據(jù)庫中,而是分布在整個Internet上,這就需要成千上萬臺計算機以“相互合作”的方式對這些海量數(shù)據(jù)進行處理。因此,為搜索引擎設計能夠高效地處理海量Internet數(shù)據(jù)的并行算法成為了學術界和工業(yè)界共同的研究方向與追求目標。在過去的數(shù)十年中,并行計算領域的研究取得了長足的進步,一些經(jīng)典的并行計算平臺相繼出現(xiàn),如MPI、OpenMP、OpenCL、CUD A等,特別是Google于2004年提出的MapReduce并行計算模型,以其良好的可擴展性、可靠性和易用性,為并行計算提供了簡單、高效的計算模型和運行環(huán)境,降低了并行計算從理論向應用轉(zhuǎn)化的難度,為并行計算的實際應用提供了一個簡單易用的平臺。 信息檢索領域的傳統(tǒng)算法發(fā)展至今已日趨成熟,然而,有些算法并非是專為并行環(huán)境設計的,面臨著無法直接處理大規(guī)模的海量數(shù)據(jù)或者無法在有效的時間內(nèi)完成對海量數(shù)據(jù)的計算的窘境。因此,如果能夠?qū)⑦@些算法加以改造,使其能夠分布在多臺計算機上并行地運行,則可以大大提高對海量數(shù)據(jù)的處理效率,更加快速地響應人們的搜索需求,改善用戶的搜索體驗。在信息檢索領域中,查詢推薦(Query Suggestion)與網(wǎng)頁排序(Page Rank)是兩項重要的研究內(nèi)容：查詢推薦可以幫助用戶更加精確有效地查詢并節(jié)省搜索時間,而網(wǎng)頁排序則可以改善搜索質(zhì)量、幫助用戶更容易地找到所需的網(wǎng)頁。如果能夠?qū)@兩個領域中的一些串行算法進行并行化改造,使其能夠并行地運行于計算機集群中,則能夠有效提升搜索引擎對大規(guī)模數(shù)據(jù)的處理能力,加快搜索引擎在查詢推薦和網(wǎng)頁排序方面的更新速度,提高用戶對檢索的滿意度。 本文研究了查詢推薦領域的QUBIC算法和基于頻繁項集挖掘的網(wǎng)頁排序算法,以對海量Internet數(shù)據(jù)的并行處理作為研究背景,基于MapReduce并行計算模型對QUBIC算法和基于頻繁項集挖掘的網(wǎng)頁排序算法進行了并行化改造,使得QUBIC算法和基于頻繁項集挖掘的網(wǎng)頁排序算法能夠運行于MapReduce并行計算框架之中,并利用Hadoop并行計算軟件框架實現(xiàn)了一個原型系統(tǒng)。具體而言,本文的主要研究工作包含以下方面： (1)對QUBIC算法進行基于MapReduce模型的并行化改造,提出了數(shù)據(jù)分布和并行計算的具體方法,包括：搜索引擎日志文件的分布存儲,Query-URL二部圖的構造,Jaccard相似系數(shù)的計算,QAG的生成,QAG中連通分量的計算以及對Query的排序。 (2)對傳統(tǒng)的SON頻繁項集挖掘算法進行基于MapReduce模型的并行化改造,提出頻繁項集并行挖掘的PSON算法,并將其應用于對頻繁URL的挖掘。在計算出搜索引擎返回結果中關聯(lián)性較大的一組URL后,按照其重要程度降序呈現(xiàn)給用戶。 本文在Hadoop并行計算平臺上實現(xiàn)了本文對原算法進行并行化改造的思想,并進行了實驗。實驗表明,本文提出的對相關算法進行并行化改造的方法是行之有效的,并且具有良好的可擴展性能和加速比性能。最后,本文實現(xiàn)了一個原型系統(tǒng),從整體上演示了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