可扩展Web信息搜集系统设计实现与应用初探ppt课件

1、可扩展Web信息搜集系统的设计、实现与运用初探控制器控制器搜集器搜集器索引器索引器索引数据库索引数据库检索器检索器用户接口用户接口WWW用户用户原始数据库原始数据库 HTML 存取分析 HTML 存取分析 主主进进程程 . . . robots 分分析析 结结果果插插入入 URL 检检查查 SOCKET接口 SOIF数据格式 PIPE接口 SOIF数据格式 通过信号 SIGUSR1通知 HTML 存取分析 新新 URL 处处理理 未未访访问问 URL 选选取取 URL Cache 数数据据库库 NewUrlCache 分布式并行分布式并行 尽能够减少主控之间网络通讯量尽能够减少主控之间网络通讯

2、量 各节点负载平衡各节点负载平衡 具有可扩展性具有可扩展性 系统可以动态变化系统可以动态变化系统具有如下特点系统具有如下特点分布式战略分布式战略物理上分散物理上分散IP分段分段主控通讯战略主控通讯战略环形通讯环形通讯网状通讯网状通讯高效搜集尽能够多的网页高效搜集尽能够多的网页目的目的搜搜集集器器主控主控2主控主控1主控主控3搜搜集集器器搜集器搜集器主控主控N搜集器搜集器 模拟数据：大小为模拟数据：大小为507MB-761,129507MB-761,129个网页的模个网页的模拟拟WebWeb数据数据 模拟实验机器配置：一台模拟实验机器配置：一台PCPC机，配有双机，配有双Intel550 CPU

3、Intel550 CPU，内存为，内存为512MB512MB，硬盘，硬盘36GB36GB，运，运转的操作系统为转的操作系统为Solaris 8.0Solaris 8.0 基于上述实验环境，分别模拟实验了主控数基于上述实验环境，分别模拟实验了主控数n n为为2 2，4 4，8 8，1616时四种情况时四种情况01234567891000.0020.0040.0060.0080.01时 间差方2 4 8 16参 考Hash函数：函数：H ( URL ) = ( DNS ( URL中主机部分中主机部分 ) ) MOD n 2, 1)()(2kpXExXDkk参考序列参考序列可扩展搜集系统负载方差可扩

4、展搜集系统负载方差 机器配置：四台机器配置：四台PCPC机，配有双机，配有双Intel550 CPUIntel550 CPU，内，内存为存为512MB512MB，硬盘，硬盘36GB36GB，运转的操作系统为，运转的操作系统为Solaris 8.0Solaris 8.0基于上述实验环境，分别实验了主控数基于上述实验环境，分别实验了主控数n n为为1 1，2 2，3 3，4 4时四种情况时四种情况模拟实验方差模拟实验方差 实践实验方差实践实验方差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 为什么要增量式搜集为什么要增量式搜集 设计目的设计目的 消除曾经搜集到的网页中曾经失效的网页消除曾经搜集到的网页中曾经失效的网页 重新搜集更新过的网页重新搜集更新过的网页 搜集没有访问过的网页搜集没有访问过的网页 检查全部

6、网页检查全部网页 重新访问的网页数量不大重新访问的网页数量不大 检查中与效力器建立衔接检查中与效力器建立衔接 网页平均生命周期网页平均生命周期1.43年，同一时间存在的网年，同一时间存在的网页总体的半衰期大约页总体的半衰期大约0.99年年 有选择性的检查网页有选择性的检查网页 Harvest搜索引擎 Google搜索引擎 Internet Archive Inktomi搜索引擎 采用全局采用全局Hash函数在一切运转节点间动态分配未访问函数在一切运转节点间动态分配未访问URL。 基于第一种方法，同时每个主控记录着一张基于第一种方法，同时每个主控记录着一张Web主机主机表，这张表在各个主控中是一

7、样的，其中每一条记录表，这张表在各个主控中是一样的，其中每一条记录包含一个包含一个Web主机及其所对应主控信息。主机及其所对应主控信息。 采用两阶段映射的方法采用两阶段映射的方法 知：知：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) = 负载平衡负载平衡通讯量低通讯量低各主控之间不反复任务各主控之间不反复任务 有利于后续任务有利

8、于后续任务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) 稳定形状b)添加节点 c) 减少节点设设N = 10 and M = 50000 Web直径直径 网页出度，网页入度网页出度，网页入度 存在于导航功能中的称为导航影响入度存在于导航功能中的称为导航影响入度 存在于认可功能中的称为认可影响入度存在于认可功能中的称为认可影响入度 有效入度有效入度 权威型网页，目录型网页权威型网页，目录型网页第三次搜集数据具有代表性第三次搜集数据具有代表性覆盖了中国覆盖了中国89.6%的网站，的网站，45.2%的网页。的网页。类似于宽度优先搜索的战略类似于宽度优先搜索的战略覆盖了覆盖了93.2%有影响力的网站有影响力的网站 平均每个网站有网页平均每个网站有网

10、页548.72548.72个。个。 网页文字平均为网页文字平均为12.92 KB12.92 KB，网站在各省之间的分布方，网站在各省之间的分布方差为差为24.1824.18。 其中教育网有其中教育网有81448144个网站，网站分布方差为个网站，网站分布方差为16.1416.14； 科技网有科技网有732732个网站，网站分布方差为个网站，网站分布方差为27.6827.68。 实验数据是实验数据是2,278,524 2,278,524 网页，网页，58,625,283 58,625,283 个链个链接接 网页的平均出度为网页的平均出度为25.725.7。在在58,625,283 58,625,

11、283 个链接中指向国外的链接数只需个链接中指向国外的链接数只需1%1%。 网页的度的分布尤其是有效入度网页的度的分布尤其是有效入度/入度分布符合幂级数定律：拥有度入度分布符合幂级数定律：拥有度为为i的网页数与的网页数与1/ix成正比，其中成正比，其中x1x=1.95x=2.37网页的度的分布尤其是有效入度网页的度的分布尤其是有效入度/入度分布符合幂级数定律：拥有度入度分布符合幂级数定律：拥有度为为i的网页数与的网页数与1/ix成正比，其中成正比，其中x1x=1.86中国中国Web直径直径=17 网络社区网络社区C= PIC= PI 二分图定义二分图定义 完全二分图完全二分图 网络中心社区对应

12、于完全二分图网络中心社区对应于完全二分图Ccore=PcoreIcoreCcore=PcoreIcore 实验数据是实验数据是2,278,524 2,278,524 网页，网页，58,625,283 58,625,283 个链接，个链接，2.5GB2.5GB。即。即PpotentialPpotential分布于分布于2,278,524 2,278,524 网页根网页根URLURL中，中， Ipotential Ipotential分布于分布于58,625,28358,625,283个个URLURL中中一个Ppotential相当于一个好的目录型网页Hub，至少包含6个不同域名的超链接剩下剩下1

13、/81/8左右的网页数据文件的大小减少到左右的网页数据文件的大小减少到313MB313MB 过滤掉后，得到过滤掉后，得到118MB118MB的链接文件的链接文件 去掉网页中有效入度大于9的链接 得到得到71MB71MB的链接文件数据的链接文件数据 去掉链接中反复的部分 数据文件变成数据文件变成14.5MB14.5MB大小大小 将链接数据中的根URL和超链接URL编码成整数 生成生成IpotentialIpotential列表和列表和PpotentialPpotential列表以及列表以及URLURL和整数的对应关系表。得到和整数的对应关系表。得到PpotentialPpotential集合集合

14、包含包含20,16020,160个个URLURL， Ipotential Ipotential集合包含集合包含201,603201,603个个URLURL，PpotentialPpotential与与IpotentialIpotential的元素的元素个数比是个数比是1 1：10 10 用i表示Web中心社区中Pcore的元素数，用j表示Icore的元素数。在Web中心社区参数i=3,j=3和i=3,j=4的情况下，从Ipotential集合中分别随机抽取100个，200个，1000，结合全部的Ppotential，利用倒排表方法找出Web中心社区 基于基于Web的链接构造的链接构造 Page

15、Rank HITS(Hyperlink-Induced Topic Search ) Web运用日志的发掘运用日志的发掘1. 设计和实现了一种可扩展海量设计和实现了一种可扩展海量Web信息搜集系信息搜集系统体系构造统体系构造2. 设计实现了动态可配置方案设计实现了动态可配置方案3.增量式搜集战略和网页搜集战略增量式搜集战略和网页搜集战略4. 提出了一种分析海量数据的方法，并由此得到提出了一种分析海量数据的方法，并由此得到了了2019年初中国年初中国Web的大小、外形和构造，尤的大小、外形和构造，尤其设计了一种获得网络社区的方法。其设计了一种获得网络社区的方法。 已发表已发表 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