信息組織與檢索 第八章-并行和分布信息檢索

TOC4/3/20201第8章并行和分布信息檢索為了有效地存取大規(guī)模文檔集需要并行和分布處理技術(shù)提供有效的可伸縮信息檢索服務(wù)本章內(nèi)容：并行信息檢索系統(tǒng)分布信息檢索系統(tǒng)TOC4/3/20202第8章本章內(nèi)容并行和分布計(jì)算的概念并行信息檢索分布信息檢索小結(jié)TOC4/3/202038.1并行和分布計(jì)算的概念為什么要采用并行和分布技術(shù)？–Web上的信息爆炸式增長(zhǎng)–數(shù)字圖書(shū)館的興起–多媒體數(shù)據(jù)的廣泛應(yīng)用–海量信息的檢索–盡管可以借助于高效的索引技術(shù)和強(qiáng)大的計(jì)算能力，但是單個(gè)計(jì)算機(jī)的能力畢竟有限–對(duì)大規(guī)模信息進(jìn)行檢索需要采用并行和分布計(jì)算的方法TOC4/3/202048.1并行和分布計(jì)算的概念什么是并行計(jì)算？–用多個(gè)處理器去求解單個(gè)問(wèn)題，把單個(gè)大問(wèn)題分解為較小的“部分”，每個(gè)處理器對(duì)應(yīng)于“部分”問(wèn)題的處理–利用并行計(jì)算的方法，可以減少求解問(wèn)題的總時(shí)間–利用并行計(jì)算技術(shù)，使得系統(tǒng)具有靈活的可伸縮性，能夠解決各種規(guī)模的計(jì)算問(wèn)題TOC4/3/202068.1并行和分布計(jì)算的概念并行計(jì)算體系結(jié)構(gòu)的四種類(lèi)型：–MISD(Multiple

Instruction

Single

Data)多指令流和單數(shù)據(jù)流?N個(gè)處理器，處理共享內(nèi)存中的單數(shù)據(jù)流。每個(gè)處理器執(zhí)行它自己的指令流，多個(gè)操作同時(shí)作用在相同的數(shù)據(jù)項(xiàng)。?MISD體系結(jié)構(gòu)現(xiàn)在很少見(jiàn)了TOC4/3/202078.1并行和分布計(jì)算的概念并行計(jì)算體系結(jié)構(gòu)的四種類(lèi)型：–MIMD(Multiple

Instruction

MultipleData)多指令流和多數(shù)據(jù)流?包含N個(gè)處理器，N個(gè)指令流和N個(gè)數(shù)據(jù)流?處理器與SISD計(jì)算機(jī)中采用的處理器相似?每個(gè)處理器有它自己的控制單元、處理單元和局部?jī)?nèi)存?處理器之間交互頻繁的MIMD系統(tǒng)稱(chēng)為緊耦合系統(tǒng)，而處理器之間交互較少的MIMD系統(tǒng)稱(chēng)為松耦合系統(tǒng)TOC8.1并行和分布計(jì)算的概念4/3/20208TOC4/3/202098.1并行和分布計(jì)算的概念MIMD與分布系統(tǒng)–MIMD指的是使用兩個(gè)以上的相同類(lèi)型處理器的單臺(tái)、自包含并行計(jì)算機(jī)系統(tǒng)，但有時(shí)也可以表征分布計(jì)算機(jī)體系結(jié)構(gòu)–在分布計(jì)算環(huán)境下，局域網(wǎng)或廣域網(wǎng)把多臺(tái)計(jì)算機(jī)連接起來(lái)，協(xié)同處理一個(gè)問(wèn)題。即使分布計(jì)算環(huán)境下的耦合是非常松散的，但還是包含了MIMD的基本部件TOC4/3/2020108.1并行和分布計(jì)算的概念MIMD與分布系統(tǒng)–MIMD并行計(jì)算機(jī)與一個(gè)分布計(jì)算環(huán)境之間的主要不同是處理器之間的通信費(fèi)用。?在分布環(huán)境下，通信費(fèi)用相當(dāng)高。–分布式程序是粗顆粒的，而運(yùn)行在單臺(tái)并行計(jì)算機(jī)上的程序是細(xì)顆粒的?顆粒性指的是在程序執(zhí)行中，相對(duì)于通信量的計(jì)算量的比例?粗顆粒程序的計(jì)算量較大（相對(duì)于通信來(lái)說(shuō)）?而細(xì)顆粒程序執(zhí)行較大的通信量（相對(duì)于計(jì)算來(lái)說(shuō)）TOC4/3/2020118.2并行信息檢索并行檢索算法的實(shí)現(xiàn)有兩種方式：–開(kāi)發(fā)新的檢索策略，并直接采用并行算法；–使現(xiàn)有的信息檢索算法適應(yīng)于并行計(jì)算。多采用后一種方式

下面以MIMD結(jié)構(gòu)為例，討論并行檢索系統(tǒng)的實(shí)現(xiàn)問(wèn)題TOC4/3/2020128.2.1并行信息檢索的結(jié)構(gòu)一、一般原理模型結(jié)構(gòu)代理：–用戶(hù)向搜索引擎提交的查詢(xún)是由一個(gè)代理程序來(lái)管理的。代理接受用戶(hù)的搜索請(qǐng)求，并把請(qǐng)求分發(fā)到各個(gè)搜索引擎上去搜索引擎：–并行計(jì)算機(jī)中的每個(gè)處理器運(yùn)行一個(gè)分離的、獨(dú)立的搜索引擎。搜索引擎并不協(xié)同處理單個(gè)查詢(xún)，但是它們可能共享程序代碼庫(kù)、文件系統(tǒng)緩沖的數(shù)據(jù)或共享內(nèi)存中的數(shù)據(jù)。TOC8.2.1并行信息檢索的結(jié)構(gòu)4/3/202013TOC8.2.1并行信息檢索的結(jié)構(gòu)4/3/202014TOC4/3/2020158.2.1并行信息檢索的結(jié)構(gòu)問(wèn)題–并不是簡(jiǎn)單地堆積CPU和磁盤(pán)，就可以提高信息檢索的性能。–問(wèn)題是如何有效地利用硬件資源，設(shè)計(jì)合理的軟件結(jié)構(gòu)（包括系統(tǒng)的、信息搜索引擎的和數(shù)據(jù)集的結(jié)構(gòu)），提高信息檢索的性能–各個(gè)處理器的訪問(wèn)可能會(huì)互相沖突，因此有存取競(jìng)爭(zhēng)的問(wèn)題。–磁盤(pán)瓶頸將會(huì)降低性能，抵消增加處理器帶來(lái)的吞吐量增益。TOC4/3/2020168.2.1并行信息檢索的結(jié)構(gòu)二、數(shù)據(jù)分割和計(jì)算分割存取沖突問(wèn)題–兩個(gè)搜索進(jìn)程需要存取存放在相同磁盤(pán)上的索引數(shù)據(jù)，仍然會(huì)有磁盤(pán)競(jìng)爭(zhēng)的問(wèn)題策略–數(shù)據(jù)復(fù)制和分割:重復(fù)復(fù)制那些訪問(wèn)次數(shù)多的數(shù)據(jù)，而把較少被訪問(wèn)的數(shù)據(jù)隨機(jī)分布–RAID：讓操作系統(tǒng)去管理索引的劃分TOC4/3/2020178.2.1并行信息檢索的結(jié)構(gòu)性能的提高–為了改善查詢(xún)的響應(yīng)時(shí)間，對(duì)單個(gè)查詢(xún)所需要的計(jì)算量進(jìn)行分割，分出多個(gè)子任務(wù)，并分配到多個(gè)處理器上去執(zhí)行–代理和搜索進(jìn)程?并行運(yùn)行在分離的處理器上，但是現(xiàn)在是協(xié)同運(yùn)行去處理同一個(gè)查詢(xún)?代理程序接受用戶(hù)的一個(gè)查詢(xún)，并把它分配到多個(gè)搜索進(jìn)程上去。?每個(gè)搜索進(jìn)程執(zhí)行部分查詢(xún)?nèi)蝿?wù)，把中間結(jié)果返回給代理?代理把這些中間結(jié)果組合起來(lái)，形成一個(gè)最終的結(jié)果，交付給用戶(hù)TOC8.2.1并行信息檢索的結(jié)構(gòu)4/3/202018TOC4/3/2020198.2.1并行信息檢索的結(jié)構(gòu)統(tǒng)一看待數(shù)據(jù)分割和計(jì)算分割–對(duì)大規(guī)模數(shù)據(jù)進(jìn)行信息檢索計(jì)算的問(wèn)題，可以看成是對(duì)其中“每個(gè)數(shù)據(jù)”進(jìn)行“少量”計(jì)算的檢索問(wèn)題–所以我們可以把信息檢索中的計(jì)算分割問(wèn)題，看成是如何進(jìn)行數(shù)據(jù)分割的問(wèn)題TOC4/3/2020208.2.1并行信息檢索的結(jié)構(gòu)三、示例兩種分割數(shù)據(jù)的方法–文檔分割方法。對(duì)數(shù)據(jù)矩陣進(jìn)行水平切割，子任務(wù)對(duì)應(yīng)于不同的文檔部分。文檔集中的

N個(gè)文檔被分配到P個(gè)處理器上去運(yùn)行–項(xiàng)分割方法。對(duì)數(shù)據(jù)矩陣進(jìn)行垂直切割，每個(gè)處理器分別處理一部分的索引項(xiàng)TOC4/3/2020228.2.2

并行檢索中的倒排索引處理數(shù)據(jù)分割方法應(yīng)用到倒排文件索引邏輯文檔分割物理文檔分割項(xiàng)分割TOC4/3/2020238.2.2

并行檢索中的倒排索引處理邏輯文檔分割采用與原順序檢索算法相同的基本倒排文件索引，對(duì)數(shù)據(jù)進(jìn)行邏輯上的分割。另外，需要對(duì)倒排文件進(jìn)行擴(kuò)展，使得每個(gè)并行進(jìn)程（分別對(duì)應(yīng)于一個(gè)處理器）能夠直接訪問(wèn)一部分索引擴(kuò)展：擴(kuò)展詞表中的每個(gè)條目項(xiàng)，讓它包含

p個(gè)指針，指向?qū)?yīng)的倒排表，其中第j個(gè)指針?biāo)饕奈臋n組（在倒排表中）對(duì)應(yīng)于第j個(gè)處理器處理的文檔子集TOC8.2.2

并行檢索中的倒排索引處理4/3/202024TOC4/3/2020258.2.2

并行檢索中的倒排索引處理物理文檔分割把文檔分割為分離的、自包含的文檔子集，每個(gè)子集對(duì)應(yīng)于一個(gè)并行處理器，每個(gè)子集具有它自己的倒排文件在查詢(xún)時(shí)，搜索進(jìn)程不共享任何東西當(dāng)用戶(hù)把一個(gè)查詢(xún)提交給系統(tǒng)時(shí)，代理把查詢(xún)分配給所有的并行搜索進(jìn)程每個(gè)并行搜索進(jìn)程在屬于它的文檔子集上執(zhí)行查詢(xún)，產(chǎn)生一個(gè)局部的、中間的查詢(xún)結(jié)果子集代理收集從所有并行搜索進(jìn)程那里得到的中間結(jié)果，合并為最終的查詢(xún)結(jié)果。TOC4/3/2020268.2.2

并行檢索中的倒排索引處理物理文檔分割每個(gè)并行搜索進(jìn)程需要利用全局的項(xiàng)統(tǒng)計(jì)值，以便獲得全局一致性的文檔匹配值使得每個(gè)搜索進(jìn)程的返回結(jié)果能夠正確地融合在一起問(wèn)題：如何獲得全局的項(xiàng)統(tǒng)計(jì)值？TOC4/3/2020278.2.2

并行檢索中的倒排索引處理項(xiàng)分割項(xiàng)分割利用的是一個(gè)倒排文件，把倒排文件（或稱(chēng)倒排表）分配給每個(gè)處理器。在查詢(xún)時(shí)，把查詢(xún)分解為多個(gè)索引項(xiàng)，每個(gè)索引項(xiàng)的查詢(xún)送到一個(gè)處理器上去，處理對(duì)應(yīng)的倒排文件個(gè)處理器把檢索到的結(jié)果返回給代理，代理按照查詢(xún)的語(yǔ)義，把這些結(jié)果合并起來(lái)。對(duì)于布爾查詢(xún)來(lái)說(shuō)，結(jié)合的方式是并、交、非等TOC4/3/2020288.3分布信息檢索問(wèn)題：大量的各種類(lèi)型的數(shù)據(jù)難以用一個(gè)中央數(shù)據(jù)庫(kù)存儲(chǔ)這些巨大的不斷增長(zhǎng)的數(shù)據(jù)現(xiàn)實(shí)的方法是把這些數(shù)據(jù)通過(guò)網(wǎng)絡(luò)分布存儲(chǔ)和維護(hù)并為用戶(hù)提供分布的信息檢索能力TOC4/3/2020298.3.1分布信息檢索的體系結(jié)構(gòu)

分布計(jì)算就是利用網(wǎng)絡(luò)連接的多臺(tái)計(jì)算機(jī)，去求解一個(gè)問(wèn)題。

分布計(jì)算系統(tǒng)可以看成是MIMD并行處理器的一種形式–具有相對(duì)較慢的處理器之間的通信通道，采用異構(gòu)處理器組合成一個(gè)并行系統(tǒng)–單個(gè)處理節(jié)點(diǎn)可以是一臺(tái)并行計(jì)算機(jī)TOC4/3/2020308.3.1分布信息檢索的體系結(jié)構(gòu)一、服務(wù)模型

服務(wù)進(jìn)程：分布計(jì)算系統(tǒng)典型地由一組服務(wù)進(jìn)程構(gòu)成，每個(gè)進(jìn)程運(yùn)行在分離的處理節(jié)點(diǎn)上，

一個(gè)委托代理進(jìn)程：負(fù)責(zé)接受客戶(hù)的請(qǐng)求，把請(qǐng)求分配給服務(wù)器，并收集來(lái)自服務(wù)器的中間結(jié)果，把中間結(jié)果合并起來(lái)，形成最終結(jié)果，交給用戶(hù)TOC4/3/2020318.3.1分布信息檢索的體系結(jié)構(gòu)二、系統(tǒng)結(jié)構(gòu)客戶(hù)（用戶(hù)）–檢索系統(tǒng)的用戶(hù)

一個(gè)查詢(xún)服務(wù)器（又稱(chēng)為連接服務(wù)器或通信服務(wù)器，之上運(yùn)行委托代理）–查詢(xún)服務(wù)器負(fù)責(zé)客戶(hù)與信息檢索服務(wù)器之間的所有消息傳遞信息檢索服務(wù)器–信息搜索TOC8.3.1分布信息檢索的體系結(jié)構(gòu)4/3/202032TOC4/3/2020338.3.1分布信息檢索的體系結(jié)構(gòu)三、一些需要考慮的問(wèn)題工程性問(wèn)題搜索協(xié)議的定義，用于規(guī)范化傳輸查詢(xún)請(qǐng)求和查詢(xún)結(jié)果；服務(wù)器的請(qǐng)求處理能力，能夠有效地接收請(qǐng)求，初始化一個(gè)子進(jìn)程或一個(gè)線程，響應(yīng)查詢(xún)請(qǐng)求；利用高速緩沖技術(shù)支持快速的數(shù)據(jù)獲取；–設(shè)計(jì)一個(gè)代理，向多個(gè)分布搜索服務(wù)器提交搜索請(qǐng)求，并維持其同步，還要把中間查詢(xún)結(jié)果合并為最終的用戶(hù)響應(yīng)TOC4/3/2020358.3.2分布信息檢索的文檔集分割獨(dú)立管理下的檢索系統(tǒng)–分布文檔集的建立和管理是獨(dú)立進(jìn)行的–每個(gè)獨(dú)立的搜索服務(wù)可以對(duì)應(yīng)于某個(gè)特定的主題領(lǐng)域–實(shí)際上是對(duì)文檔集按照主題領(lǐng)域進(jìn)行了語(yǔ)義分割–這通常是常見(jiàn)的元搜索系統(tǒng)的形式TOC4/3/2020368.3.2分布信息檢索的文檔集分割集中管理下的檢索系統(tǒng)–在所有搜索服務(wù)器上復(fù)制文檔集?文檔集足夠小，可以存放在單臺(tái)搜索服務(wù)器上，系統(tǒng)的并行性是通過(guò)多任務(wù)來(lái)實(shí)現(xiàn)的–把文檔集隨機(jī)分布?代理把每個(gè)查詢(xún)廣播到所有的搜索服務(wù)器上，并把檢索的結(jié)果合并起來(lái)，返回給用戶(hù)–對(duì)文檔集進(jìn)行語(yǔ)義分割?把用戶(hù)的查詢(xún)分配到合適的搜索服務(wù)器上，最后把各路查詢(xún)結(jié)果合并起來(lái)，形成最終的查詢(xún)結(jié)果TOC4/3/2020378.3.3標(biāo)準(zhǔn)化分布信息檢索系統(tǒng)的基礎(chǔ)保障就是標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化的兩個(gè)方面–元數(shù)據(jù)及其內(nèi)容描述。為了使得信息檢索可互操作，需要一致的數(shù)據(jù)集模型。這方面的標(biāo)準(zhǔn)用于建立標(biāo)準(zhǔn)的、共用的、適合描述各種類(lèi)型數(shù)據(jù)的元數(shù)據(jù)語(yǔ)義庫(kù)和文檔內(nèi)容庫(kù)。–信息檢索協(xié)議。它是一套互操作信息檢索協(xié)議，支持統(tǒng)一的元數(shù)據(jù)語(yǔ)義和內(nèi)容描述。在標(biāo)準(zhǔn)檢索協(xié)議支持下，通過(guò)共同支持的查詢(xún)語(yǔ)義和語(yǔ)法，對(duì)各種異構(gòu)文檔集進(jìn)行搜索?例如：Z39.50TOC8.3.3標(biāo)準(zhǔn)化4/3/202038TOC4/3/2020408.3.4分布信息檢索的查詢(xún)處理資源選擇–給定信息需求和一組資源描述，決定搜索哪些資源庫(kù)–資源描述表示分布信息環(huán)境中包含哪些文檔集–資源選擇的主要問(wèn)題??對(duì)資源排序，即根據(jù)資源滿(mǎn)足查詢(xún)需求的可能程度來(lái)排序TOC4/3/2020418.3.4分布信息檢索的查詢(xún)處理查詢(xún)結(jié)果的合并–要求：把從每個(gè)文檔集得到的排序結(jié)果合并起來(lái)，形成單一的排序–問(wèn)題：因?yàn)槊總€(gè)文檔集可能采用不同的統(tǒng)計(jì)排序準(zhǔn)則，不同的數(shù)據(jù)表示和/或檢索算法，因此文檔的排序和相似值的含義不同，合并這些查詢(xún)結(jié)果是非常困難的TOC4/3/2020428.3.4分布信息檢索的查詢(xún)處理查詢(xún)結(jié)果的合并–合并的方法?循環(huán)交替地合并從各個(gè)文檔集查詢(xún)得到的查詢(xún)結(jié)果排序表，但是這種方法可能導(dǎo)致不好的結(jié)果?利用全局項(xiàng)統(tǒng)計(jì)值去計(jì)算文檔的相似值?采用計(jì)算歸一化的相似值，或基于歸一化值的合并方法?

……TOC4/3/202043小結(jié)

對(duì)于大型的不斷增長(zhǎng)的在線文檔集來(lái)說(shuō)，尤其是多媒體數(shù)據(jù)的大量涌現(xiàn)，需要并

行和分布計(jì)算來(lái)支持信息的檢索

主要討論了MIMD并行體系的信息檢索問(wèn)題

信息檢索系統(tǒng)可以利用的并行策略有任務(wù)并行、數(shù)據(jù)并行和它們的混合方式TOC4/3/202044小結(jié)任務(wù)并行策略:–因?yàn)楦鞣N查詢(xún)可以獨(dú)立地處理，所以我們可以把查詢(xún)處理看成是一個(gè)并行問(wèn)題。–可以利用多處理器體系結(jié)構(gòu)，調(diào)度任務(wù)，平衡查詢(xún)負(fù)荷，每個(gè)處理器執(zhí)行一個(gè)順序地搜索任務(wù)。數(shù)據(jù)并行策略