可擴(kuò)展Web信息搜集系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)與應(yīng)用初探ppt課件

1、可擴(kuò)展Web信息搜集系統(tǒng)的設(shè)計(jì)、實(shí)現(xiàn)與運(yùn)用初探控制器控制器搜集器搜集器索引器索引器索引數(shù)據(jù)庫索引數(shù)據(jù)庫檢索器檢索器用戶接口用戶接口WWW用戶用戶原始數(shù)據(jù)庫原始數(shù)據(jù)庫 HTML 存取分析 HTML 存取分析 主主進(jìn)進(jìn)程程 . . . robots 分分析析 結(jié)結(jié)果果插插入入 URL 檢檢查查 SOCKET接口 SOIF數(shù)據(jù)格式 PIPE接口 SOIF數(shù)據(jù)格式 通過信號(hào) SIGUSR1通知 HTML 存取分析 新新 URL 處處理理 未未訪訪問問 URL 選選取取 URL Cache 數(shù)數(shù)據(jù)據(jù)庫庫 NewUrlCache 分布式并行分布式并行 盡能夠減少主控之間網(wǎng)絡(luò)通訊量盡能夠減少主控之間網(wǎng)絡(luò)通訊

2、量 各節(jié)點(diǎn)負(fù)載平衡各節(jié)點(diǎn)負(fù)載平衡 具有可擴(kuò)展性具有可擴(kuò)展性 系統(tǒng)可以動(dòng)態(tài)變化系統(tǒng)可以動(dòng)態(tài)變化系統(tǒng)具有如下特點(diǎn)系統(tǒng)具有如下特點(diǎn)分布式戰(zhàn)略分布式戰(zhàn)略物理上分散物理上分散IP分段分段主控通訊戰(zhàn)略主控通訊戰(zhàn)略環(huán)形通訊環(huán)形通訊網(wǎng)狀通訊網(wǎng)狀通訊高效搜集盡能夠多的網(wǎng)頁高效搜集盡能夠多的網(wǎng)頁目的目的搜搜集集器器主控主控2主控主控1主控主控3搜搜集集器器搜集器搜集器主控主控N搜集器搜集器 模擬數(shù)據(jù)：大小為模擬數(shù)據(jù)：大小為507MB-761,129507MB-761,129個(gè)網(wǎng)頁的模個(gè)網(wǎng)頁的模擬擬WebWeb數(shù)據(jù)數(shù)據(jù) 模擬實(shí)驗(yàn)機(jī)器配置：一臺(tái)模擬實(shí)驗(yàn)機(jī)器配置：一臺(tái)PCPC機(jī)，配有雙機(jī)，配有雙Intel550 CPU

3、Intel550 CPU，內(nèi)存為，內(nèi)存為512MB512MB，硬盤，硬盤36GB36GB，運(yùn)，運(yùn)轉(zhuǎn)的操作系統(tǒng)為轉(zhuǎn)的操作系統(tǒng)為Solaris 8.0Solaris 8.0 基于上述實(shí)驗(yàn)環(huán)境，分別模擬實(shí)驗(yàn)了主控?cái)?shù)基于上述實(shí)驗(yàn)環(huán)境，分別模擬實(shí)驗(yàn)了主控?cái)?shù)n n為為2 2，4 4，8 8，1616時(shí)四種情況時(shí)四種情況01234567891000.0020.0040.0060.0080.01時(shí) 間差方2 4 8 16參 考Hash函數(shù)：函數(shù)：H ( URL ) = ( DNS ( URL中主機(jī)部分中主機(jī)部分 ) ) MOD n 2, 1)()(2kpXExXDkk參考序列參考序列可擴(kuò)展搜集系統(tǒng)負(fù)載方差可擴(kuò)

4、展搜集系統(tǒng)負(fù)載方差 機(jī)器配置：四臺(tái)機(jī)器配置：四臺(tái)PCPC機(jī)，配有雙機(jī)，配有雙Intel550 CPUIntel550 CPU，內(nèi)，內(nèi)存為存為512MB512MB，硬盤，硬盤36GB36GB，運(yùn)轉(zhuǎn)的操作系統(tǒng)為，運(yùn)轉(zhuǎn)的操作系統(tǒng)為Solaris 8.0Solaris 8.0基于上述實(shí)驗(yàn)環(huán)境，分別實(shí)驗(yàn)了主控?cái)?shù)基于上述實(shí)驗(yàn)環(huán)境，分別實(shí)驗(yàn)了主控?cái)?shù)n n為為1 1，2 2，3 3，4 4時(shí)四種情況時(shí)四種情況模擬實(shí)驗(yàn)方差模擬實(shí)驗(yàn)方差 實(shí)踐實(shí)驗(yàn)方差實(shí)踐實(shí)驗(yàn)方差01234567891000.511.522.533.544.5x 105timeweb page number1,2,3,4 main-controll

5、ers4 3 2 1 11.522.533.5411.522.533.544.5main-controller numberspeedup1,2,3,4 main-controllers)_(4*4)_(3*3)deg_(2*2)deg_(1*1)(depthdirectoryfURLparentpriorityfreereplicafareeinfaURLpriority 為什么要增量式搜集為什么要增量式搜集 設(shè)計(jì)目的設(shè)計(jì)目的 消除曾經(jīng)搜集到的網(wǎng)頁中曾經(jīng)失效的網(wǎng)頁消除曾經(jīng)搜集到的網(wǎng)頁中曾經(jīng)失效的網(wǎng)頁 重新搜集更新過的網(wǎng)頁重新搜集更新過的網(wǎng)頁 搜集沒有訪問過的網(wǎng)頁搜集沒有訪問過的網(wǎng)頁 檢查全部

6、網(wǎng)頁檢查全部網(wǎng)頁 重新訪問的網(wǎng)頁數(shù)量不大重新訪問的網(wǎng)頁數(shù)量不大 檢查中與效力器建立銜接檢查中與效力器建立銜接 網(wǎng)頁平均生命周期網(wǎng)頁平均生命周期1.43年，同一時(shí)間存在的網(wǎng)年，同一時(shí)間存在的網(wǎng)頁總體的半衰期大約頁總體的半衰期大約0.99年年 有選擇性的檢查網(wǎng)頁有選擇性的檢查網(wǎng)頁 Harvest搜索引擎 Google搜索引擎 Internet Archive Inktomi搜索引擎 采用全局采用全局Hash函數(shù)在一切運(yùn)轉(zhuǎn)節(jié)點(diǎn)間動(dòng)態(tài)分配未訪問函數(shù)在一切運(yùn)轉(zhuǎn)節(jié)點(diǎn)間動(dòng)態(tài)分配未訪問URL。 基于第一種方法，同時(shí)每個(gè)主控記錄著一張基于第一種方法，同時(shí)每個(gè)主控記錄著一張Web主機(jī)主機(jī)表，這張表在各個(gè)主控中是一

7、樣的，其中每一條記錄表，這張表在各個(gè)主控中是一樣的，其中每一條記錄包含一個(gè)包含一個(gè)Web主機(jī)及其所對(duì)應(yīng)主控信息。主機(jī)及其所對(duì)應(yīng)主控信息。 采用兩階段映射的方法采用兩階段映射的方法 知：知：H : hosts on the web ; N : main-controllers; M : elements in the Array A.那么有：那么有： (h , n) | m =f1(h), n=f2(m), hH, mM, nN 要求：要求：(Ui Uj) = ；(Hi Hj) = ；(Ni Nj) = 負(fù)載平衡負(fù)載平衡通訊量低通訊量低各主控之間不反復(fù)任務(wù)各主控之間不反復(fù)任務(wù) 有利于后續(xù)任務(wù)有利

8、于后續(xù)任務(wù)11229911229911111122111110101111N1111221010N2(5001.10000)N2 shift (9546.10000)N 1 0 s h i f t (49546.50000)N 1 s h i f t (4546.5000)N1 (45001.45555) Array AURLsN2 (45556.46110)N9 (49440.50000)N1(1.5000)N10(45001.50000)N1(1.4545)N2(5001.9545)N10(45001.49545)N1(1.5000)N2(5001.10000)N9(40001.45000

9、)a) 穩(wěn)定形狀b)添加節(jié)點(diǎn) c) 減少節(jié)點(diǎn)設(shè)設(shè)N = 10 and M = 50000 Web直徑直徑 網(wǎng)頁出度，網(wǎng)頁入度網(wǎng)頁出度，網(wǎng)頁入度 存在于導(dǎo)航功能中的稱為導(dǎo)航影響入度存在于導(dǎo)航功能中的稱為導(dǎo)航影響入度 存在于認(rèn)可功能中的稱為認(rèn)可影響入度存在于認(rèn)可功能中的稱為認(rèn)可影響入度 有效入度有效入度 權(quán)威型網(wǎng)頁，目錄型網(wǎng)頁權(quán)威型網(wǎng)頁，目錄型網(wǎng)頁第三次搜集數(shù)據(jù)具有代表性第三次搜集數(shù)據(jù)具有代表性覆蓋了中國覆蓋了中國89.6%的網(wǎng)站，的網(wǎng)站，45.2%的網(wǎng)頁。的網(wǎng)頁。類似于寬度優(yōu)先搜索的戰(zhàn)略類似于寬度優(yōu)先搜索的戰(zhàn)略覆蓋了覆蓋了93.2%有影響力的網(wǎng)站有影響力的網(wǎng)站 平均每個(gè)網(wǎng)站有網(wǎng)頁平均每個(gè)網(wǎng)站有網(wǎng)

10、頁548.72548.72個(gè)。個(gè)。 網(wǎng)頁文字平均為網(wǎng)頁文字平均為12.92 KB12.92 KB，網(wǎng)站在各省之間的分布方，網(wǎng)站在各省之間的分布方差為差為24.1824.18。 其中教育網(wǎng)有其中教育網(wǎng)有81448144個(gè)網(wǎng)站，網(wǎng)站分布方差為個(gè)網(wǎng)站，網(wǎng)站分布方差為16.1416.14； 科技網(wǎng)有科技網(wǎng)有732732個(gè)網(wǎng)站，網(wǎng)站分布方差為個(gè)網(wǎng)站，網(wǎng)站分布方差為27.6827.68。 實(shí)驗(yàn)數(shù)據(jù)是實(shí)驗(yàn)數(shù)據(jù)是2,278,524 2,278,524 網(wǎng)頁，網(wǎng)頁，58,625,283 58,625,283 個(gè)鏈個(gè)鏈接接 網(wǎng)頁的平均出度為網(wǎng)頁的平均出度為25.725.7。在在58,625,283 58,625,

11、283 個(gè)鏈接中指向國外的鏈接數(shù)只需個(gè)鏈接中指向國外的鏈接數(shù)只需1%1%。 網(wǎng)頁的度的分布尤其是有效入度網(wǎng)頁的度的分布尤其是有效入度/入度分布符合冪級(jí)數(shù)定律：擁有度入度分布符合冪級(jí)數(shù)定律：擁有度為為i的網(wǎng)頁數(shù)與的網(wǎng)頁數(shù)與1/ix成正比，其中成正比，其中x1x=1.95x=2.37網(wǎng)頁的度的分布尤其是有效入度網(wǎng)頁的度的分布尤其是有效入度/入度分布符合冪級(jí)數(shù)定律：擁有度入度分布符合冪級(jí)數(shù)定律：擁有度為為i的網(wǎng)頁數(shù)與的網(wǎng)頁數(shù)與1/ix成正比，其中成正比，其中x1x=1.86中國中國Web直徑直徑=17 網(wǎng)絡(luò)社區(qū)網(wǎng)絡(luò)社區(qū)C= PIC= PI 二分圖定義二分圖定義 完全二分圖完全二分圖 網(wǎng)絡(luò)中心社區(qū)對(duì)應(yīng)

12、于完全二分圖網(wǎng)絡(luò)中心社區(qū)對(duì)應(yīng)于完全二分圖Ccore=PcoreIcoreCcore=PcoreIcore 實(shí)驗(yàn)數(shù)據(jù)是實(shí)驗(yàn)數(shù)據(jù)是2,278,524 2,278,524 網(wǎng)頁，網(wǎng)頁，58,625,283 58,625,283 個(gè)鏈接，個(gè)鏈接，2.5GB2.5GB。即。即PpotentialPpotential分布于分布于2,278,524 2,278,524 網(wǎng)頁根網(wǎng)頁根URLURL中，中， Ipotential Ipotential分布于分布于58,625,28358,625,283個(gè)個(gè)URLURL中中一個(gè)Ppotential相當(dāng)于一個(gè)好的目錄型網(wǎng)頁Hub，至少包含6個(gè)不同域名的超鏈接剩下剩下1

13、/81/8左右的網(wǎng)頁數(shù)據(jù)文件的大小減少到左右的網(wǎng)頁數(shù)據(jù)文件的大小減少到313MB313MB 過濾掉后，得到過濾掉后，得到118MB118MB的鏈接文件的鏈接文件 去掉網(wǎng)頁中有效入度大于9的鏈接 得到得到71MB71MB的鏈接文件數(shù)據(jù)的鏈接文件數(shù)據(jù) 去掉鏈接中反復(fù)的部分 數(shù)據(jù)文件變成數(shù)據(jù)文件變成14.5MB14.5MB大小大小 將鏈接數(shù)據(jù)中的根URL和超鏈接URL編碼成整數(shù) 生成生成IpotentialIpotential列表和列表和PpotentialPpotential列表以及列表以及URLURL和整數(shù)的對(duì)應(yīng)關(guān)系表。得到和整數(shù)的對(duì)應(yīng)關(guān)系表。得到PpotentialPpotential集合集合

14、包含包含20,16020,160個(gè)個(gè)URLURL， Ipotential Ipotential集合包含集合包含201,603201,603個(gè)個(gè)URLURL，PpotentialPpotential與與IpotentialIpotential的元素的元素個(gè)數(shù)比是個(gè)數(shù)比是1 1：10 10 用i表示W(wǎng)eb中心社區(qū)中Pcore的元素?cái)?shù)，用j表示Icore的元素?cái)?shù)。在Web中心社區(qū)參數(shù)i=3,j=3和i=3,j=4的情況下，從Ipotential集合中分別隨機(jī)抽取100個(gè)，200個(gè)，1000，結(jié)合全部的Ppotential，利用倒排表方法找出Web中心社區(qū) 基于基于Web的鏈接構(gòu)造的鏈接構(gòu)造 Page

15、Rank HITS(Hyperlink-Induced Topic Search ) Web運(yùn)用日志的發(fā)掘運(yùn)用日志的發(fā)掘1. 設(shè)計(jì)和實(shí)現(xiàn)了一種可擴(kuò)展海量設(shè)計(jì)和實(shí)現(xiàn)了一種可擴(kuò)展海量Web信息搜集系信息搜集系統(tǒng)體系構(gòu)造統(tǒng)體系構(gòu)造2. 設(shè)計(jì)實(shí)現(xiàn)了動(dòng)態(tài)可配置方案設(shè)計(jì)實(shí)現(xiàn)了動(dòng)態(tài)可配置方案3.增量式搜集戰(zhàn)略和網(wǎng)頁搜集戰(zhàn)略增量式搜集戰(zhàn)略和網(wǎng)頁搜集戰(zhàn)略4. 提出了一種分析海量數(shù)據(jù)的方法，并由此得到提出了一種分析海量數(shù)據(jù)的方法，并由此得到了了2019年初中國年初中國Web的大小、外形和構(gòu)造，尤的大小、外形和構(gòu)造，尤其設(shè)計(jì)了一種獲得網(wǎng)絡(luò)社區(qū)的方法。其設(shè)計(jì)了一種獲得網(wǎng)絡(luò)社區(qū)的方法。 已發(fā)表已發(fā)表 Hongfei YAN, Jianyong WANG, Xiaoming LI, and Lin GUO, “Architectural Design and Evaluation of an Efficient Web-crawling System, Journal of System and Software, Vol. 60 No. 3, March 2019. pp.185-193. YAN