天网增量搜集子系统的设计与实现.doc

北京大学网络实验室硕士学位论文

硕士研究生学位论文

题目：天网增量搜集子系统的设计与实现

姓名：王东海
学号：10308155
院系：信息科技学院
专业：计算机软件与理论
研究方向：计算机网络与分布式系统
导师：严伟副教授，韩华

二〇〇六年五月

版权声明

任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。

北京大学硕士学位论文
-PAGEI-

摘要

互联网中的网页呈几何级数的增长。对搜索引擎而言，及时搜集互联网中新出现和变化的网页是核心工作之一。
本文首先总结了当前有关搜集系统主要问题的解决方法。其后主要介绍天网增量搜集子系统中结点协作、URL调度、网页指纹、网页变化预测、URL缓冲等算法设计实现以及相关算法的性能测试。
在系统设计实现章节中较为详细说明了系统的体系结构和各主要模块的设计实现。通过良好设计，我们保证了系统具有良好的扩展性，并对内存和其它硬件资源利用等做了较好的优化。
为检测算法的有效性，我们跟踪了近50万的网页在一个月内的变化，并以此为测试集。在此测试集上对比了我们系统中实现的算法与其它算法，结论表明系统实现的动态选择算法在预测效果上要优于其它三个独立的算法。
论文最后总结了增量搜集子系统的运行情况：天网增量搜集子系统从2005年10月开始在单结点运行，平均每天提供约100万左右的新出现网页，有效地保证了天网搜索引擎的时新性。

关键字：天网，搜索引擎，增量搜集，网页变化预测

Master'sThesisofPekingUniversity
--

TheDesignandImplementationofTiwangincrementalcrawler
DonghaiWang(ComputerSoftwareandTheory)
DirectedbyWeiYan,HuaHan
Abstract

Thenumberofwebpages,whichfollowspower-lawdistribution,inInternetalwaysincreasessharply,anditiscrucialforamodernsearchenginetocollectnewwebpagesassoonaspossible.
Inthisarticlewe’llfirstintroducetherelatedworkaboutcrawlingandincrementalcrawlingtechnology,andthenwe’llstatethedesignandrealizationofseveralkeyalgorithms,namelynode-collaborationalgorithm,URLschedulingalgorithm,webpagefingerpointgenerationalgorithm,URLcachingalrogirhm,webpagechangeforcastalgortithm,etc.Besides,weevaluatetheperformanceoftheabovealgorithms.
We’llalsodescribethemainarchitectureofTianwangincrementalsub-systemandthedesignandimplementationofchiefcomponents.
Inordertoverifytheefficiencyofourwebpagechangeforcastalgorithm,we’vetracedabout500,000URLstorecordthehistoryoftheirchangingwithinonemonthasatest-set.Basedonthistest-set,wehavemadeacomprisonbetweenouralgothmandotherthreealgorithms.Wedrawaconclusionthatthealgorithmproposedinthisarticleismoreeffectivethantheotherthree.
Atlast,we’llsummarizetherunningconditionofthissub-system,whichhasbeenrunningonasinglecomputersinceOct.,2005.Wefindthatthesub-systemhasgreatlyenhancedthepreforcementoforiginalTianwan