信息檢索中top-k問題的并行算法及優(yōu)化研究.pdf

1、隨著互聯(lián)網(wǎng)絡的發(fā)展，以文本形式存儲在網(wǎng)絡上的信息呈現(xiàn)爆炸式增長。
　　 大量積累的動態(tài)信息阻礙了人類對它的有效利用。作為大規(guī)模文本集合上信息檢索工具的搜索引擎在誕生之初就成為解決網(wǎng)絡信息訪問的重要工具，并在其后的發(fā)展中占據(jù)著人類信息生活越來越重要的位置。針對某一查詢，搜索引擎可能命中數(shù)以億記的查詢結果，而用戶關心的往往只是符合其查詢要求的最優(yōu)的數(shù)十個結果。如何從搜索引擎命中的大量結果中，快速、準確地找出最符合查詢需求的結果集合，

2、構成搜索引擎設計的一個關鍵問題——top-k 查詢問題。
　　 Top-k 查詢針對分散在不同信息源中的對象，根據(jù)聚合函數(shù)找出其中分數(shù)最優(yōu)的k個對象。其在信息檢索領域具有廣泛的應用，并且是影響搜索引擎性能的關鍵組件。為了提升top-k 查詢的數(shù)據(jù)處理能力，加速top-k 查詢的計算過程，本文以分布式存儲系統(tǒng)和共享式存儲系統(tǒng)為目標平臺，研究top-k 查詢并行算法設計和性能優(yōu)化的關鍵技術。主要的研究工作分為三個部分：一是研究分布式

3、存儲平臺上的top-k 查詢并行算法，以解決海量數(shù)據(jù)的查詢問題；二是研究基于任務并行的top-k 查詢處理，優(yōu)化查詢算法的數(shù)據(jù)訪問開銷；三是研究多核處理器平臺上top-k 查詢的計算性能優(yōu)化，以提高查詢的速度滿足用戶的實時性要求。本文對于并行查詢算法和性能優(yōu)化技術的研究，可以充分利用現(xiàn)有并行計算機的處理能力，解決top-k 查詢中海量數(shù)據(jù)處理和實時性相關問題，具有重要的學術價值和應用價值。本文的主要研究成果，貢獻和創(chuàng)新點可以概括為以下幾

4、點：
　　 1.提出處理海量數(shù)據(jù)的top-k 查詢并行算法由于top-k 查詢處理的數(shù)據(jù)規(guī)模日益擴大，單計算機的存儲系統(tǒng)難以滿足應用需求。本文提出一種數(shù)據(jù)劃分方法，將大規(guī)模數(shù)據(jù)劃分到分布式并行機的存儲系統(tǒng)上，并針對這種數(shù)據(jù)劃分設計了基于消息傳遞的top-k 查詢并行算法，而后通過縮短通信消息長度、減少通信次數(shù)等手段進一步優(yōu)化了該并行算法。
　　 2.提出減小數(shù)據(jù)訪問開銷的top-k 查詢并行算法Top-k 查詢是一種I/

5、O 密集型計算問題，數(shù)據(jù)訪問的開銷占了總開銷的很大比重。本文研究了常用top-k 查詢算法對數(shù)據(jù)源的訪問方式，提出一種多策略的并行算法減小查詢的數(shù)據(jù)訪問開銷。通過算法分析，得出了并行算法數(shù)據(jù)訪問開銷優(yōu)于原有算法的必要數(shù)值條件，并且給出了并行算法訪問開銷的一個上界。
　　 3.優(yōu)化多核平臺上top-k 查詢的計算性能隨著研究的深入，top-k 查詢算法被設計得越來越復雜，大部分算法都通過引入額外計算來加快算法終止從而減少數(shù)據(jù)訪問上