PDF《第一章背景介绍》

目录-1-摘要2

第一章背景介绍31.

1 万维网和海量信息31.2 搜索引擎概述41.3 Cache 概述5

第二章相关研究62.1 Cache 替换算法62.2 Cache 在搜索引擎中的应用8

第三章一种通用Cache 的设计和实现93.1 通用Cache 的设计目标93.3.1 通用性目标93.3.2 高效性要求10 3.3.3 自评测目标10 3.2 通用Cache 的设计10 3.2.1 总控器11 3.2.2 层次控制器12 3.2.3 数据存储器13 3.2.4 分层Cache 设计的优点13

第四章通用Cache 的搜索引擎检索端应用15 4.1 实验环境15 4.2 用户查询日志的分析16 4.2.1 查询的总体分布16 4.2.2 查询的时间局部性性质18 4.3.3 用户查询结果翻页的考察19 4.3 通用Cache 应用结构和配置21 4.3.1 总体结构21 4.3.2 缓存配置23 4.3.3 时间分析25

第五章总结和进一步工作28 参考文献29 致谢31 摘要-2-摘要在处理Web 海量信息的过程中,有 两个问题制约着性能的提高.一方面,由 于信息量非常大,只 能把所有数据存放在磁盘等相对慢速的设备上,或 者放在多台不同的机器上.对 于数据的读取和保存只能从这些慢速设备或者分布式的机器上获得.另 一方面,信 息量的庞大也造成了大量的计算,消 耗大量计算时间.在 很多应用中,存 在着引用的局部性规律,即大量的操作需要访问少量的数据.本文工作包括:1) 本文设计了一种通用的缓存(Cache)结构.其主要特点是通用性,在各种应用中,用户可以自由地对该Cache 的容量,替换算法,数据项结构,预 取策略,体 系结构进行配置.同 时提供一个模拟接口,用户可以通过这个接口执行模拟操作,对算法、容量进行评估.2) 分析天网用户查询日志,发现对于用户的查询,无论是否考虑翻页的情况,都满足类Zipf 分布,这样的具有比较强的局部性的分布形式,提示我们如果采用Cache 结构可以带来很大的好处.3) 在天网搜索引擎中检索模块中加入这种通用Cache 模块.通过选取适当的Cache 大小,替 换算法,预 取策略和层次结构,进 一步提高搜索引擎检索端的性能.关键词:海量信息 缓存技术 分布特征 搜索引擎

第一章 背景介绍 -

3 -

第一章 背景介绍 1.1 万维网和海量信息 万维网(WWW,即World Wide Web) 是因特网(Internet) 最成功的应用之一.因 特网的前身是美国国防部高级研究计划署的研究试验性网ARPANET. 1983年TCP/IP 成为ARPANET上事实上的协议.此后,ARPANET上连接的网络、机 器和用户快速增长.1988年NSFNET 和ARPANET互联,它的规模以指数增长,很多地区网络开始加入,并且开始与加拿大、欧 洲和太平洋地区的网络连接.从而Internet逐渐形成和壮大.万维网起源于1989年的欧洲粒子物理研究室(CERN) . 1989年3月,由物理学家Tim Berners-Lee提出万维网的计划.1990年 9月 , 第一个文本原型正式运行.此 后 ,许 多的大专院校和业界公司纷纷加入到万维网的研究中来,开 发大量的基于万维网的应用程序.在 九十年代这短短几年时间里,万 维网吸引了的大量的用户和开发者,使 得它不断地完善和发展.万维网是一个分布式的信息系统,它由超文本(hypertext)和超媒体(Hyper- media)组成.超文本一般由文本信息和链接信息组成,文本信息是供人们浏览阅读的,链 接信息又称为超链接(Hyperlink),它们是指向别的超文本信息的指针,可 以指向万维网上一个位置.超 媒体是超文本的扩展,包括在万维网上的各种资源,包括视频,音频,图像等等.在这样一个系统中,一 方面,用 户可以通过超链接的指引,非 常容易地获取分布在不同机器上的信息.另 一方面,各 种不同地区,职 业的人们可以自由地把本地的信息放到这个系统中去.这 样 ,这 个系统就成为一个全球区域的,包 括大量信息的系统.根 据Google搜索引擎的统计,截至到2002年 4月 , 全球的网页数已经超过20亿[Google]. 在中国,万 维网也以惊人的速度发展.万 维网于1994年正式在中国建立,2003年中国互联网络信息资源数量调查报告显示,截至2003年底,中国的网页总数已经超过3亿 , 总字节数超过了6T, 总网站数达到59.6