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

1、可扩展Web信息搜集系统的设计、实现与应用初探闫宏飞北京大学网络与分布式实验室2002年6月14日提纲问题提出可扩展网页搜集系统网页搜集系统的动态配置海量网页应用研究初步工作总结2工作的背景和意义Web发展1989年提出-1993Mosaic-1997年底(3亿2000万） -2000年1月(超过10亿) - 2002年5月(超过20亿) ，中国的Web 发展1995年底(10万到100万之间)每年以指数形式增长2002年1月(超过5000万)，.3搜索引擎工作流程起源于传统的信息全文检索理论包括如下3个工作过程 搜集Web信息建立索引库检索查询www用户4应用到下列方面：搜索引擎网页存档其它

2、方面确认网页的有效性，站点结构分析，更新通知，镜像，个人Web助理 搜集方式目标尽快高效地获取网页搜集Web信息可扩展Web信息搜集系统为处理海量数据而设计主题Web信息搜集系统 为发现专业信息而设计5提纲问题提出可扩展网页搜集系统分布式系统搜集策略增量式搜集网页搜集系统的动态配置海量网页应用研究初步工作总结6天网系统体系结构控制器搜集器索引器索引数据库检索器用户接口WWW用户原始数据库制定搜集策略过滤IP地址执行Robot协议存储所抓取得网页7集中式搜集系统8分布式搜集系统分布式并行尽可能减少主控之间网络通信量各节点负载均衡具有可扩展性系统可以动态变化系统具有如下特点分布式策略物理上分散IP

3、分段主控通信策略环形通信网状通信高效搜集尽可能多的网页目标搜集器主控2主控1主控3调度搜集器搜集器主控N搜集器9模拟系统实验模拟数据：大小为507MB-761,129个网页的模拟Web数据模拟实验机器配置：一台PC机，配有双Intel550 CPU，内存为512MB，硬盘36GB，运行的操作系统为Solaris 8.0基于上述实验环境，分别模拟实验了主控数n为2，4，8，16时四种情况10负载平衡参照序列11模拟系统负载平衡Hash函数：H ( URL ) = ( DNS ( URL中主机部分 ) ) MOD n 参考序列可扩展搜集系统负载方差 12模拟系统可扩展性13实际系统实验机器配置：四

4、台PC机，配有双Intel550 CPU，内存为512MB，硬盘36GB，运行的操作系统为Solaris 8.0基于上述实验环境，分别实验了主控数n为1，2，3，4时四种情况14实际系统负载平衡模拟实验方差 实际实验方差15实际系统可扩展性16搜集策略表面深层17增量式搜集为什么要增量式搜集设计目标消除已经搜集到的网页中已经失效的网页 重新搜集更新过的网页 搜集没有访问过的网页18检查全部网页重新访问的网页数量不大检查中与服务器建立连接网页平均生命周期1.43年，同一时间存在的网页总体的半衰期大约0.99年有选择性的检查网页实现增量式搜集的两种策略 19搜集部分相关研究Harvest搜索引擎G

5、oogle搜索引擎Internet ArchiveInktomi搜索引擎20提纲问题提出可扩展网页搜集系统网页搜集系统的动态配置海量网页应用研究初步工作总结21实现动态可配置的三种方法采用全局Hash函数在所有运行节点间动态分配未访问URL。基于第一种方法，同时每个主控记录着一张Web主机表，这张表在各个主控中是相同的，其中每一条记录包含一个Web主机及其所对应主控信息。采用两阶段映射的方法 22两阶段映射模型已知：H : hosts on the web ; N : main-controllers; M : elements in the Array A.则有： (h , n) | m =

6、f1(h), n=f2(m), hH, mM, nN 要求：(Ui Uj) = ；(Hi Hj) = ；(Ni Nj) = 负载平衡通信量低各主控之间不重复工作 有利于后续工作23两阶段映射举例11229911229911111122111110101111N1111221010N2(5001.10000)N2 shift (9546.10000)N10 shift (49546.50000)N1 shift (4546.5000)N1 (45001.45555) Array AURLsN2 (45556.46110)N9 (49440.50000)N1(1.5000)N10(45001.50

7、000)N1(1.4545)N2(5001.9545)N10(45001.49545)N1(1.5000)N2(5001.10000)N9(40001.45000)a) 稳定状态b)增加节点 c) 减少节点设N = 10 and M = 5000024提纲问题提出可扩展网页搜集系统网页搜集系统的动态配置海量网页应用研究初步中国Web大小、形状和结构工作总结25术语介绍Web直径网页出度，网页入度存在于导航功能中的称为导航影响入度存在于认可功能中的称为认可影响入度有效入度权威型网页，目录型网页26天网搜集记录第三次搜集数据具有代表性覆盖了中国89.6%的网站，45.2%的网页。类似于宽度优先搜索

8、的策略覆盖了93.2%有影响力的网站27基本统计数据平均每个网站有网页548.72个。网页文字平均为12.92 KB，网站在各省之间的分布方差为24.18。其中教育网有8144个网站，网站分布方差为16.14；科技网有732个网站，网站分布方差为27.68。 28中国Web的形状29Web页面链接实验数据是2,278,524 网页，58,625,283 个链接 网页的平均出度为25.7。在58,625,283 个链接中指向国外的链接数只有1%。 30网页有效入度/出度分布网页的度的分布（尤其是有效入度/入度分布）符合幂级数定律：拥有度为i的网页数与1/ix成正比，其中x1x=1.95x=2.3

9、731网页入度分布网页的度的分布（尤其是有效入度/入度分布）符合幂级数定律：拥有度为i的网页数与1/ix成正比，其中x1x=1.8632Web结构中国Web直径=1733Web社区 网络社区C= PI二分图定义完全二分图网络核心社区对应于完全二分图Ccore=PcoreIcore 34找出Web核心社区的方法实验数据是2,278,524 网页，58,625,283 个链接，2.5GB。即Ppotential分布于2,278,524 网页根URL中， Ipotential分布于58,625,283个URL中一个Ppotential相当于一个好的目录型网页（Hub），至少包含6个不同域名的超链接剩

10、下1/8左右的网页（数据文件的大小减少到313MB） 过滤掉后，得到118MB的链接文件 35找出Web核心社区的方法(续1)去掉网页中有效入度大于9的链接 得到71MB的链接文件数据 去掉链接中重复的部分 数据文件变成14.5MB大小 将链接数据中的根URL和超链接URL编码成整数 生成Ipotential列表和Ppotential列表以及URL和整数的对应关系表。得到Ppotential集合包含20,160个URL， Ipotential集合包含201,603个URL，Ppotential与Ipotential的元素个数比是1：10 用i表示Web核心社区中Pcore的元素数，用j表示Ic

11、ore的元素数。在Web核心社区参数i=3,j=3和i=3,j=4的情况下，从Ipotential集合中分别随机抽取100个，200个，1000，结合全部的Ppotential，利用倒排表方法找出Web核心社区 36找出Web核心社区的方法(续2)37相关研究 基于Web的链接结构PageRankHITS(Hyperlink-Induced Topic Search )Web使用日志的挖掘38回顾1. 设计和实现了一种可扩展海量Web信息搜集系统体系结构2. 设计实现了动态可配置方案3.增量式搜集策略和网页搜集策略4. 提出了一种分析海量数据的方法，并由此得到了2002年初中国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 2002. pp.185-193.YAN Hongfei, WANG Jianyong, LI Xiaoming, “A Dynam