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

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

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

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

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

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