浙江警官职业学院目前搜索引擎系统的性能评价指标分析

　　浙江警官职业学院目前搜索引擎系统的性能评价指标分析

　　收稿日期：2004-10-17；修订日期：2005-07-04：一种*敏*感*词*业学院，浙江杭州310018； 2.浙江大学电脑科技系浙江杭州310027）重要提示：基于对现有网页更新策略的比较分析：统一页面更新策略、个别更新策略和分类更新策略，改进组合重要性和最新的页面分类更新策略在理论上证明了其优化和有效性。 关键词：搜索引擎；重要性;与时俱进；更新策略 中文图书馆分类编号：TP393. 09 文档识别码：A 文章 编号：1001-3695 (2005）11-0212-02 一个网页刷新策略根据新鲜度 LV Han-fei, WANGShen-kang Police Vocational School浙江，杭州浙江 310018；2. 浙江大学计算机科学系，浙江杭州 310027) 摘要：基于现有刷新策略：统一刷新策略、角色刷新策略、cassifiedrefresh 策略，我们提出了新的 cassified 刷新策略。使用两个网页 此外，我们展示了它的优化理论 关键词：搜索引擎；受欢迎程度；新鲜;刷新策略随着互联网的快速发展和普及，互联网上的信息量呈几何指数级增长，但不断膨胀的信息海量不利于有用信息的发现，因此解决这一问题的关键技术--- 搜索引擎应运而生。

　　搜索引擎可以简单地理解为互联网上网页的索引。由于网页随时可能被修改或删除，搜索引擎系统的采集程序或爬虫必须不断下载。 ”，更新系统的索引库，满足用户对“新鲜”信息的需求。目前搜索引擎系统的性能评价指标主要包括：响应时间、准确率、召回率、查询结果的相关性排名等。因为没有搜索引擎系统可以采集所有网页，召回率很难计算，现在搜索引擎更关心搜索结果的“重要性”和搜索结果的“新鲜度”，这需要Crawer能够搜索到重要的和最新的网页 网页更新的基本概念 一旦机器人 Crawer 检索到一些网页，它必须更新这些页面。页面更新的几个基本概念定义如下：（1）importance 假设一个本地网页集合，因为网页的重要性符合 Zipf 分布 n。这就定义了网页的重要性。定义 1 p 本地网页的集合，我们的重要性bpage 集合也大致符合 Zipf 分布。根据重要性访问这些网页集合 j 的概率 P(j) 需要满足以下条件： 1, 2, ..., N)，本地网页集合的平均访问概率应定义为 P 2 重要性本地网页集合j的定义如下：（2）时新性定义3本地网页p更新是指使本地网页的内容等于当前网页的内容的过程现实世界，所以本地集合 S n。

　　实际上，当前性是本地集合中更新的页面占集合中总页面的百分比。 (3）岁（Age） 定义4 本地网页的年龄p为本地集合中网页的平均年龄。网页更新的基本策略 目前现有的方案大致分为以下几类，不同的更新策略会得到不同的更新结果。 （1）统一更新策略。机器人Crawer使用相同频率对2005新合集中所有网页进行研究，不考虑这些网页的变化频率。（2）个别更新策略。变化频率对于不同的网页不同，机器人Crawier根据单个页面变化的频率来更新各个页面，即机器人Crawier为每个页面分配一个更新频率，页面变化频率与更新频率之比为对任何单个网页都一样。（3）分类更新策略。该策略是在分析前两种策略的优缺点后提出的。主要思想在2.分类更新策略[3]提出的背景文献中. 在所有网页中都很重要，在性别相同的情况下，频繁访问变化过快的网页并不能显着提高搜索效率。相反，资源应该e 专注于能够跟上变化速度的网页。这与个人更新的想法相反。因此，一般来说，统一更新策略优于个别更新策略。但是，如果采用统一的更新策略，就会造成那些频繁变化的网页长时间无法更新的问题。因此，文献[3]基于该方案提出了一种折衷的更新策略，即分类更新策略。

　　分类更新策略的基本思想假设所有网页的重要性相同。有一个I网页，其变化频率的估计值为平均变化频率。根据网页的变化频率，将网页分为两类：将频率大于或等于平均变化频率的网页归为一类F a2，然后将两类网页分别归为一类根据两个平均变化频率访问。通过验证，得出以下结论： 对于所有网页重要性相同的分类访问策略，在系统资源允许的情况下，变化频率大于或等于平均变化频率的网页集合F1应该以最快的速度访问这些网页。速度5f a1；对于变化频率小于平均变化频率的网页集合F2，可以在频率a2下直接访问这些网页。这是因为这种类型的集合变化速度比较慢，用a2访问可以满足要求，也可以减少系统开销。本文算法是在文献[3]提出的分类更新策略的基础上提出的。该算法综合考虑了网页的重要性和及时性。分类算法的改进算法文献[3]提出的分类更新算法是基于所有网页集合的重要性相同的假设。事实上，网页的重要性在不同的主题和不同的时间是不同的。对于重要的网页，即使平均变化频率不是很快，考虑到变化频率突然变快或者变化频率分布不均，需要提高更新频率，保证网页的新鲜度。对于不重要的网页，即使频繁更改，也无需增加更新频率，而是降低更新频率以节省系统资源。

　　因此，我们提出了一种结合重要性和及时性的更新算法。首先，我们从重要性和及时性的角度描述了分类更新方法，最后描述了将两者结合起来的更新算法。 （1）从重要性的角度对网页进行分类和更新的方法。将网页集合S按照网页的重要性分为五类后：非常重要。因为网页的重要性符合Zpf分布，所以根据重要性访问这五类集合的概率 P() 应满足以下条件： P() = 437956. 大约进行访问次数，较重要的集合大约访问 S 次，重要的set S(S) 应该分别为2.2F，这样可以增加输出网页的重要性。 437956 218978 145985 109489 087591 189781 094891 729927 547445 @437276 更新网页的新方法@k分别采集在这五类中 S 如果不考虑重要性，则在这五类集合中变化频率大于或等于平均变化频率的网页s 分为一种类型 F1。取更新频率 5f a1 1, 2, 3, 4, 5）。实际上是10个类别S的集合（因为5个类别中的每一个都分为两组，即大于平均更新频率，小于平均更新频率）分别使用更新频率5f a1 (3）结合分类更新算法的重要性和及时性。

　　基于重要性，提出如下分类更新算法： 由表1可知，因为集合根据其重要性计算出的更新频率大于平均更新频率（S）。因此，集合S 11 22的更新频率根据下式计算： (S), 5fa1 (S), 5fa1 根据其重要性计算的更新频率小于平均更新频率52的更新频率，分别根据以下公式： (S ), 5fa1 (S), 5fa1 (S), 5fa1 函数max(a,6）定义如下：max函数mn(a,6）定义如下:max) 对于重要度高的网页，使用了两个类别 算法中更新频率越高，使得重要度高的网页的时间新鲜度比（翻到第218号，卢汉非等） .: 一种结合重要性和时间新鲜度的网页更新策略变化显着，因此大数据量内容分发速度比TCP协议传输速度快很多。（4）扩展性好。在从多个同时下载的过程中来源，服务器不需要维护t的状态客户端，可以支持非常大量的并发请求。发送。接收方可以随时退出内容发送，接收方也可以随时加入接收内容数据，不会导致内容分发重启。更重要的是，纠错码在传输过程中无需反馈信息，不受速率限制，使其更适用于多种网络带宽条件下的内容分发，如互联网、移动网络、卫星网络和 Ad hoc。

　　Summary 这个新的内容分发网络充分利用了 CDN 和 P2P 网络在内容分发方面的优势。采用基于无限制比率的纠错编码传输机制，大大增强了内容分发网络的鲁棒性和可扩展性。可以适用于多网络带宽条件下的大并发请求用户的内容分发。但是还有一些方面需要逐步完善：（1）良好的传输拥塞控制机制。一般非TCP传输协议没有拥塞控制机制。一方面，没有限速纠错编码机制在传输中引入一定量的冗余数据信息，这些冗余数据信息的存在理论上会增加网络拥塞的概率；另一方面，在发生拥塞的网络路径上，如果没有合理的拥塞控制机制，没有比限制纠错编码数据会影响其他基于TCP传输协议的应用程序，特别是在使用组播传输的网络中，需要一种拥塞传输控制机制，可以避免反馈崩溃的影响(Response Coiiapse). 对此，IETF RMT 研究组做了大量的研究工作，形成了多个RFC文档（RFC3450、3451、3452），该技术已经在一些实际的服务系统中得到应用。 （2）高效率内容分发数据真实性验证。在新内容分发网络的客户端内容共享阶段，客户端共享内容兼具客户端和服务器功能，但这些客户端很容易被伪造，恶意用户替换下载的内容对于其他恶意内容（如病毒文件、垃圾干扰文件等），将极大影响内容分发网络的性能和安全。

　　因此，必须保证客户端下载的内容是源内容服务器对应内容的副本，而不是其他恶意内容。对此，纽约大学的Max Krohn等人有相关研究[10]，可在内容分发网络中借鉴。总之，原有的CDN和P2P内容分发网络技术在实际应用中暴露了很多弊端和不足。本文介绍的基于无与伦比的限速纠错编码实现和CDN P2P网络拓扑优势的新型内容分发网络在一定程度上解决了这些存在的问题，并表现出许多良好的性能特点。随着其相关技术的逐步深入研究和不断完善，这种内容分发网络技术必将发挥其优良的特性。参考资料：DougKaye。 Peer-to-Peer Content Deivery Usng Informaton Addtve Codecs Kuikarn, CRosenberg CDN-P2PHybrd Architecture Cost-EffectveStreamng Meda Dstrbuton［C］。 SPIE/ACM MMCN 2003，加利福尼亚州圣西亚拉，2003. Low、FernandoPagann、John Doyie。 Internet Conges - IEEEControi Systems Magazne，2002，2.PetarMaymounkov。 Davd Mazres Rateiess Codes Down-ioads IPTPS'03 (Berkeiey)，2003.1-6 Day，等。 MeasuredPer-formance ContentDstron Networks 5th Internatonai Web Cachng ContentDeivery Workshop，2000 1-10.MchaeiLuby、Vvek Goyai、SmonSkara 等。 Wave Eua-ton-based Rate Controi Usng Muitcast Round Trp Tme AcmsIGCOMM 2002, Pttsburgh, PA, 2002. TraceyHo，RaptorCodes 摘要［EB/OL］。 www 彼塔尔梅蒙科夫。在线代码［R］．纽约大学，Techncai 报告 TR2002-833，2002 年 Hefeeda、AHabb、B Botev 等。 PROMISE: Peer-to-Peer Meda Streamng Usng CoiiectCast 11thACM Inter-natonai Conference ［10］MaxKrohn, Mchaei FreedmanOn-the-Fiy Verfcaton Erasure-Encoded Fie Transfers, IRIS Student Workshop［M］Cambrdge, MA, 2003. 关于作者：王峰（1977-），男，山东济宁人，博士生，主要研究方向为计算机网络技术；钱华林（1940-），男，研究员，博士生导师，主要研究方向为计算机网络、网络工程和网络运行服务。

　　（上接第213页）原分类算法的新鲜度应该是高或相等的，即理论上保证了重要性和新鲜度。但是，这样做的代价是越重要的网页消耗的系统资源比原来的分类算法更多或相等。重要性较低的网页使用两种分类算法的较低更新频率。优点是重要性较低的网页会比原来的分类算法消耗更少的系统资源。总的来说，这种算法的优点是越重要的网页越是最新，但消耗的系统资源越多；不太重要的网页更新较少，但可以节省系统资源。结论 该算法是在文献[3]中的分类算法的基础上提出的。它是一种新的分类更新算法，结合了网页的重要性和及时性。与仅按重要性或时效性进行分类的算法相比，该算法在系统资源相似的情况下，使较重要的网页更新，而较不重要的网页更新较慢。理论上，这是一个很好的解决方案。由于实验需要较长的统计周期，下一个目标是使用长期的实验统计来证明算法的有效性。另外，根据重要性分为五个等级，根据重要性可以扩展到I等级，I 1, 2, ..., N。 对于不同的尺度和不同类型的S集，如何获得最好的价值也是一个值得研究的问题。参考文献：VjayGupta 等。 Internet Search Engne Freshness WebServer Heip［R］ Unversty Urbana-Champagn.114 JunghooCho, Hector Garca-Moina IncrementaiCrawier［D］ 斯坦福大学，2002 JunghooCho 抓取大型 ScaieWeb 数据［D］斯坦福大学，2001 北京：高等教育出版社，1989.99-116.国内综合搜索引擎的新鲜度计算［J］.计算机工程与应用, 2003, (21）:47- 49. 作者简介：吕汉飞(1977- )，女，硕士*敏*感*词*，主要研究方向为人工智能、计算机网络；王申康，男教授，博士生导师，主要研究方向为人工智能、计算机网络计算机应用研究2005