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

《可扩展Web信息搜集系统的设计、实现与应用初探.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

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信息建立

2、索引库检索查询www用户4应用到下列方面：搜索引擎网页存档其它方面确认网页的有效性，站点结构分析，更新通知，镜像，个人Web助理搜集方式目标尽快高效地获取网页搜集Web信息可扩展Web信息搜集系统为处理海量数据而设计主题Web信息搜集系统为发现专业信息而设计5提纲问题提出可扩展网页搜集系统分布式系统搜集策略增量式搜集网页搜集系统的动态配置海量网页应用研究初步工作总结6天网系统体系结构控制器搜集器索引器索引数据库检索器用户接口WWW用户原始数据库制定搜集策略过滤IP地址执行Robot协议存储所抓取得网页7集中式搜集系统8分布式搜集系统分布

3、式并行尽可能减少主控之间网络通信量各节点负载均衡具有可扩展性系统可以动态变化系统具有如下特点分布式策略物理上分散IP分段主控通信策略环形通信网状通信高效搜集尽可能多的网页目标搜集器主控2主控1主控3调度搜集器搜集器主控N搜集器9模拟系统实验模拟数据：大小为507MB->761,129个网页的模拟Web数据模拟实验机器配置：一台PC机，配有双Intel550CPU，内存为512MB，硬盘36GB，运行的操作系统为Solaris8.0基于上述实验环境，分别模拟实验了主控数n为2，4，8，16时四种情况10负载平衡参照序列11模拟系统负载平衡

4、Hash函数：H(URL)=(DNS(URL中主机部分))MODn参考序列可扩展搜集系统负载方差12模拟系统可扩展性13实际系统实验机器配置：四台PC机，配有双Intel550CPU，内存为512MB，硬盘36GB，运行的操作系统为Solaris8.0基于上述实验环境，分别实验了主控数n为1，2，3，4时四种情况14实际系统负载平衡模拟实验方差实际实验方差15实际系统可扩展性16搜集策略表面深层17增量式搜集为什么要增量式搜集设计目标消除已经搜集到的网页中已经失效的网页重新搜集更新过的网页搜集没有访问过的网页18检查全部网页重新访问的网

5、页数量不大检查中与服务器建立连接网页平均生命周期1.43年，同一时间存在的网页总体的半衰期大约0.99年有选择性的检查网页实现增量式搜集的两种策略19搜集部分相关研究Harvest搜索引擎Google搜索引擎InternetArchiveInktomi搜索引擎20提纲问题提出可扩展网页搜集系统网页搜集系统的动态配置海量网页应用研究初步工作总结21实现动态可配置的三种方法采用全局Hash函数在所有运行节点间动态分配未访问URL。基于第一种方法，同时每个主控记录着一张Web主机表，这张表在各个主控中是相同的，其中每一条记录包含一个Web主机

6、及其所对应主控信息。采用两阶段映射的方法22两阶段映射模型已知：H:hostsontheweb;N:main-controllers;M:elementsintheArrayA.则有：{(h,n)

7、m=f1(h),n=f2(m),h∈H,m∈M,n∈N}要求：(Ui∩Uj)=Ø；(Hi∩Hj)=Ø；(Ni∩Nj)=Ø负载平衡通信量低各主控之间不重复工作有利于后续工作23两阶段映射举例1…12…2……9…91…12…2……9…91…111…112…211…11……10…1011…11N111…12…2……10…10N2(5001..100

8、00)N2shift(9546..10000)N10shift(49546..50000)N1shift(4546..5000)N1(45001..45555)ArrayAURLsN2(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)a)稳定状态b)增加节点c)减少节点设N=10andM=5000024提纲

9、问题提出可扩展网页搜集系统网页搜集系统的动态配置海量网页应用研究初步中国Web大小、形状和结构工作总结25术语介绍Web直径网页出度，网页入度存在于导航功能中的称为导航影响入度存在于认可功能中的称为认可影响