第三种存储方式为当一些新的网页进入系统后,会根据某种权重算法,淘汰网页库中的某些网页.淘汰算法可以有根据pagerank值,或根据最近连续未访问到的次数等.
其它相关的搜集系统
除了通用搜集系统外,目前还有诸如主题式搜集系统, 用户定制的搜集系统, 基于代理的搜集系统等.这些系统的实现技术基于和上述类似,只是关注的内容不同.文[Francis Crimmins,2001]指出应用的环境很大程度上决定了上述搜集系统的设计.
系统主要算法设计
在软件设计开发时,我们总会考虑它们的应用环境.在不同的环境下,相同的实现带来的效果可能会迥然不同.在本文中实现的增量搜集系统中关注的是中国的互联网,或其中的某一部分.这也影响了我们算法的设计:我们在设计算法时关心的问题和其它算法有些差异.
对增量系统来说,总是希望能够用尽可能少的资源来获取尽可能多的变化的网页.在上一章中介绍的几个增量系统及相关预测和调度算法中,更多的都在试图找一个最优或次优的算法,尽可能满足其所关心的性能指标(如重要网页时新度高或平均时新度高,变化网页发现及时等等).本文的实现基于另一种考虑:在已有机器性能的基础上,尽可能快的感知变化的网页,对带宽等只要在允许范围内,将不再考虑.换而言之,当我们系统有3000万搜集能力,我们以此3000万的访问能力能够快速感知到互联网上90%以上的变化网页,对我们系统是允许的.对网页的时新度是用来衡量该系统性能的一个重要标准.这种思路和贪心法有类似之处.
文[2005中国互联网报告,2006]给出中国互联网网中网页的更新周期如下表:
表4-1 中国互联网网页更新周期
我国互联网一周内的更新比率约为18%, 一个月内约有35%左右的网页进行了更新;三个月内60%以上的网页都进行了更新;80%的网页半年内都更新了内容.国内可索引的网页超过25亿,我们取其下限25亿.根据上表中的数据,我们可以估算到平均每天变化的网页为:
对于具有1Gbit带宽的搜集系统而言,如果仅以带宽利用率来衡量,新网页搜集只占带宽的30%左右.
在天网系统中,因为性能原因,我们关注的网页数不到3亿.这样,我们网页集合中平均每天需要更新的网页不到1000万.
网页更新时间的预测算法
在上一章中我们介绍到对于网页变化规律的研究多是网页变化符合泊松过程.但在一些实现的增量搜集系统中,采用的方法则不一定基于这一假设,如有的简单使用邻近法,有的实现基于把网页按某种规则分类,根据优先级,采用某种调度算法进行搜集.
互联网上的网页变化纷繁复杂,难以一种算法来对所有的网页都适用.于是我们希望能够根据不同网页的特点来选择不同的算法预测其网页更新时间.这是最初的想法.下面介绍我们系统中使用的几种算法,以及这些算法如何在我们系统中协同工作.
邻近法
该算法即为[Knut Magne Risvik, et al., 2002]文中提到的算法.对新搜集到的网页,系统根据属性设置初始的更新时间.如果网页在该时间内更新,则把更新时间减半;反之,则加倍.算法原理如下:
Half_estimate(webpage &page)
{
page.last_interval *= page.changed 0.5:1;
Page.refresh_time += page.last_interval;
}
邻近法比较适合于没有变化规律的网站.在这种情况下,我们可以使用较小的资源感知网页的变化.对网页变化最大的延迟为最近一次的访问间隔.平均的话应该为这一间隔的1/2.
等间隔
等间隔比较简单.即每隔一段时间去访问互联网中的这一网页.该方法在[Junghoo Cho, et al, 2003]文中提及,不过在其文章中对访问间隔的选择有一个比较复杂的算法.在本系统中,考虑到性能及可实现性,没有采用他提供的算法来取间隔.系统使用的是记录最近几次的变化时间,然后简单取其平值,对平均值乘以某一系数即做为此网页的变化间隔.
该方法对规律变化的网页比较适用.所谓有规律的变化,我们通常指的是宏观上的,比如按小时,半天,一天为度量,而并不是严格的时间间隔.举例而言,如果以天为度量标准,那么在一天内变化的网页我们都认为它是符合这一规律,虽然他们变化时间不同,在一天内变化的次数也有差别.按此约束,当我们选择变化度量为1天时,则可以认为中国互联网中至少2.5%左右的网页是符合规律变化的.其它有规律的变化其周期可以是n天,其它的网页则可能是没有规律的.
及时返回法
算法思想为当一个连续未变化的网页按照邻近法加倍设置下次访问时间.不过一旦发现该网页发生变化,即把更新时间设置为某一个

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]  ... 下一页  >> 

   

上一篇文章： 天网增量搜集子系统的设计与实现（1）