第七章 并行和分布式信息檢索

第七章并行和分布式信息檢索并行信息檢索并行計(jì)算(ParallelComputing)并行計(jì)算將單個(gè)問(wèn)題劃分為多個(gè)較小的“子”問(wèn)題，用多個(gè)處理器同時(shí)分別處理這些“子”問(wèn)題來(lái)得到單個(gè)問(wèn)題的解；并行計(jì)算機(jī)多個(gè)可以同時(shí)工作的處理器構(gòu)成的計(jì)算機(jī)系統(tǒng)；并行信息檢索把信息檢索過(guò)程建立在利用并行算法對(duì)數(shù)據(jù)進(jìn)行分割的基礎(chǔ)上；計(jì)算機(jī)體系結(jié)構(gòu)分類按照指令(Instruction)流和數(shù)據(jù)(Data)流的數(shù)目，F(xiàn)lynn將計(jì)算機(jī)體系結(jié)構(gòu)分成四類：SISD（SingleInstructionSingleData）

單指令流單數(shù)據(jù)流SIMD（SingleInstructionMultipleData）單指令流多數(shù)據(jù)流MISD（MultipleInstructionSingleData）多指令流單數(shù)據(jù)流MIMD（MultipleInstructionMultipleData）

多指令流多數(shù)據(jù)流MIMD并行體系結(jié)構(gòu)并行信息檢索原理多個(gè)查詢之間的并行處理（任務(wù)級(jí)并行檢索）利用MIMD結(jié)構(gòu)對(duì)多個(gè)查詢的處理并行化，每個(gè)處理器處理不同的查詢，每個(gè)查詢的處理之間相互獨(dú)立，最多只對(duì)共享內(nèi)存中的部分代碼或者共有數(shù)據(jù)實(shí)行共享。并行信息檢索原理單個(gè)查詢內(nèi)部的并行處理（進(jìn)程級(jí)并行檢索）將查詢的計(jì)算量進(jìn)行分割，分成多個(gè)子任務(wù)，并分配到多個(gè)處理器的搜索進(jìn)程上去執(zhí)行。數(shù)據(jù)分割方法檢索算法處理的基本數(shù)據(jù)元素k1k2...ki...ktd1W1,1W2,1...Wi,1...Wt,1d2W1,2W2,2...Wi,2...Wt,2.....................djW1,jW2,j...Wi,j...Wt,j.....................dNW1,NW2,N...Wi,N...Wt,N文檔標(biāo)引詞數(shù)據(jù)分割方法文檔分割法對(duì)數(shù)據(jù)矩陣進(jìn)行水平切割，將文檔分割為一系列子任務(wù)，每個(gè)處理器分別處理一部分文檔語(yǔ)詞分割法對(duì)數(shù)據(jù)矩陣進(jìn)行垂直分割，每個(gè)處理器分別處理一部分標(biāo)引詞倒排文檔的分割邏輯文檔分割（logicaldocumentpartitioning）物理文檔分割（physicaldocumentpartitioning）語(yǔ)詞分割（termpartitioning）邏輯文檔分割數(shù)據(jù)分割方式從倒排索引數(shù)據(jù)結(jié)構(gòu)上來(lái)說(shuō)倒排索引與原單進(jìn)程順序處理沒(méi)有區(qū)別倒排索引能夠支持并行進(jìn)程直接訪問(wèn)各進(jìn)程所管轄的那一部分文檔對(duì)應(yīng)的倒排索引部分查詢處理過(guò)程代理發(fā)起P個(gè)并行進(jìn)程來(lái)處理查詢；每個(gè)進(jìn)程在自己管轄的文檔集上執(zhí)行相同的文檔排名算法；搜索進(jìn)程在一個(gè)共享數(shù)組中記錄文檔排名；最終由代理產(chǎn)生文檔的排名列表。TermiP1P2P3P4倒排列表Termi詞典邏輯文檔分割物理文檔分割數(shù)據(jù)分割方式文檔從物理上劃分成不同子集，每個(gè)子集歸屬一個(gè)進(jìn)程管轄每個(gè)文件子集包含自己的索引查詢處理過(guò)程代理將查詢提交給所有并行搜索進(jìn)程；每個(gè)并行進(jìn)程處理查詢并返回匹配文件列表；代理收集各個(gè)進(jìn)程返回的匹配文件列表并把它們合并為一個(gè)最終的匹配文件列表。語(yǔ)詞分割數(shù)據(jù)分割方式倒排索引按詞表集合劃分，不同的詞表集合對(duì)應(yīng)不同的并行處理器處理查詢處理方式查詢根據(jù)不同詞表集被拆解成多個(gè)，每個(gè)子查詢被送往對(duì)應(yīng)的處理器進(jìn)行處理；處理器產(chǎn)生匹配列表以及排名值并將列表返回給代理；代理將不同處理器返回的匹配結(jié)果加以混合。文檔集：DocumentText

1Peaseporridgehot2Peaseporridgecold3Peaseporridgeinthepot4Peaseporridgehot,peaseporridgenotcold5Peaseporridgecold,peaseporridgenothot6Peaseporridgehotinthepot舉例<6,1>coldhotinnotpeaseporridgepotthe<1,1><2,1><3,1><4,2><5,2>詞匯表<2,1><4,1><1,1><4,1><5,1><6,1><3,1><6,1><4,1><5,1><6,1><1,1><2,1><3,1><4,2><5,2><3,1><6,1><3,1><6,1>倒排記錄表<5,1>舉例—倒排文檔<6,1>coldhotinnotpeaseporridgepotP1P2P3the<1,1><2,1><3,1><4,2><5,2>倒排記錄表Term“pease”詞匯表舉例—邏輯文檔分割coldhotinnotpeaseporridgepotthe<3,1><4,2><4,1><4,1><3,1><4,1><3,1><4,2><3,1><3,1>P2hotpeaseporridge<1,1><2,1><1,1><1,1><2,1>P1cold<2,1><6,1>hotinnotpeaseporridgepotthe<5,2><5,1><6,1><6,1><5,1><6,1><5,2><6,1><6,1>P3cold<5,1>舉例—物理文檔分割<6,1>coldhotinnotpeaseporridgepotthe<1,1><2,1><3,1><4,2><5,2><2,1><4,1><1,1><4,1><5,1><6,1><3,1><6,1><4,1><5,1><6,1><1,1><2,1><3,1><4,2><5,2><3,1><6,1><3,1><6,1>P1P2P3<5,1>舉例—語(yǔ)詞分割分布式信息檢索分布式計(jì)算(DistributedComputing)分布式計(jì)算運(yùn)用網(wǎng)絡(luò)連接的多臺(tái)計(jì)算機(jī)解決一個(gè)問(wèn)題。分布式信息檢索在分布式環(huán)境中，利用分布式計(jì)算技術(shù)從大量異構(gòu)的信息資源中檢索出對(duì)用戶有用的信息的過(guò)程分布式環(huán)境是指信息資源在物理上分布于各地，但邏輯上是一個(gè)整體。分布式信息檢索過(guò)程從用戶處接收查詢；把用戶查詢翻譯成檢索提問(wèn)表達(dá)式；確定與提問(wèn)式相關(guān)的數(shù)據(jù)集；利用提問(wèn)式對(duì)數(shù)據(jù)集進(jìn)行檢索；收集相應(yīng)的檢索結(jié)果；對(duì)檢索結(jié)果進(jìn)行整理；將整理結(jié)果返回給用戶。分布式信息檢索系統(tǒng)體系結(jié)構(gòu)客戶機(jī)1集合選擇結(jié)果合并信息檢索服務(wù)器1客戶機(jī)2客戶機(jī)n信息檢索服務(wù)器2信息檢索服務(wù)器n網(wǎng)絡(luò)網(wǎng)絡(luò)文檔集合的劃分非合作信息檢索每一個(gè)檢索服務(wù)器由不同組織建立，采用不同的檢索模型和方法，每個(gè)文檔集合的質(zhì)量未知，合并結(jié)果困難。合作信息檢索每一個(gè)檢索服務(wù)器由同一組織建立，采用相同的檢索模型和方法，每個(gè)文檔集合的質(zhì)量已知，合并結(jié)果相對(duì)簡(jiǎn)單。隨機(jī)劃分文檔集合語(yǔ)義分割文檔集合文檔集合的選擇樸素法直接將用戶的查詢請(qǐng)求發(fā)送給所有的信息檢索服務(wù)器進(jìn)行檢索；粗略法為每一個(gè)信息檢索服務(wù)器提供描述信息的數(shù)據(jù)集選擇方法；定性的方法采用粗略信息代表數(shù)據(jù)集內(nèi)容定量的方法基于學(xué)習(xí)的方法根據(jù)查詢經(jīng)驗(yàn)預(yù)測(cè)數(shù)據(jù)集對(duì)新查詢的有用程度作業(yè)文檔集：1.你\見(jiàn)\或者\(yùn)不\見(jiàn)\我2.我\就在\那里3.不\悲\不