2008-07-22

《Recrawl Scheduling Based on Information Longevity》阅读笔记

Posted in 实验室, Web Data Management at 14:35 Author:仲远

标签:

《Recrawl Scheduling Based on Information Longevity》是发表在WWW2008上面的一篇论文,其作者是Yahoo的高级工程师,因此可以在一定程度上看作是Yahoo搜索引擎在未来可能改进的方向。这篇论文的中文题目可以译为《基于信息生命周期的重新抓取调度》。

我们知道,当前搜索引擎在互联网中扮演越来越重要的角色。面对繁杂海量的Web数据,如果没有搜索引擎的存在,Web用户在信息获取上将存在很大的难度。从初期以PageRank算法为核心的Google的出现,使得互联网进入了一个新的时代。而搜索引擎在爬取页面之后,面临的一个重要问题就是:何时重新访问这个页面,以维护针对此页面的索引。这就是搜索引擎爬虫的重新抓取问题。

面对这一问题,目前比较通用的两个解决办法是:第一,可以根据页面改变频率来决定重新爬取的频率;第二,可以根据页面的重要程度来决定重新爬取的频率。这两种方法应该来说都还是比较直观的,大家也都能够很容易理解。不过本文就提出,应该根据页面上各个信息片段的生命周期来考虑重新爬取的调度。并且,本文通过一个数据集的研究证明,页面上的信息片段的生命周期与页面改变频率并没有非常明显的相关性。

作者将页面上的信息片段分为三类:第一种是静态(Static)信息,也就是在相当长一段时间都不会改变的信息,比如页面的导航条、标题、模板等;第二种是易流失(Churn)信息,也就是每一次访问都不相同的信息,比如当前时间显示、广告习性你等;第三种是滚动(Scroll)信息,就是类似博客首页的信息显示一样,一条新的信息加入,取代了一条当前存在最久的信息,但是总的信息显示条数不变,例如都是10条信息。

在这三类信息中,作者比较关注与易流失信息与滚动信息,并且使用泊松分布在为这些信息的生命周期建模。然后就可以产生两种调度策略:一种是曲线拟合的策略,也就是根据历史页面的信息片段生命周期更符合哪种曲线,就按照哪种曲线进行拟合,然后计算出下一次爬取的时间;第二种是基于边界的策略,这种策略会计算出历史页面上信息片段生命周期效用的上界与下界,然后据此计算出来的最大效用与最小效用与阀值之间的关系,来决定下一次爬取该页面的时间。

这篇文章应该来说是比较有实际意义的一篇文章。从中也可以看到,通用搜索引擎虽然已经发展很多年了,但是仍然有许多问题需要解决。同时,我们也应该注意,目前的搜索引擎正在面临着变革的到来!

本文可以自由转载,转载时请保留全文并注明出处:
转载自仲子说 [ http://www.wangzhongyuan.com/ ]
原文链接:

1 Comment »

  1. whiteshirt said,

    2011年April3日 at 2:39

    Like your blog~

Leave a Comment

*
To prove you're a person (not a spam script), type the security text shown in the picture. Click here to regenerate some new text.
Click to hear an audio file of the anti-spam word