（计算机软件与理论专业论文）基于web挖掘的proxy端预取技术的研究与实现.pdf

东北大学硕士学位论文摘 要 基于， t e b 挖掘的p r o x y 端预取 技术的 研究与 实现 摘要 的迅速发展，改变了信息创建和交换的方式。虽然网络速度在近几年 有了 很大的提高， 但网络带宽的增长却总是滞后于对其需求的增长，使得人们在 访问www时总是要忍受较长的等待时间。w e b 预取作为一种最流行和最有效的 减少访问延迟的手段，已 经越来越受到研究者的关注。 由于荃于w e b 挖掘的预取能够更加准确地反映用户的访问模式， 从而取得更 好的预取性能， 所以， 它一直是w e b 预取研究的热点。 而代理服务器作为i n t e r n e t 基础构架的中间层，本身就具备了减少w e b 访问延迟的作用。如果在代理服务器 端实现基于w e b 挖掘的预取，无疑会取得最佳的效果. 在本文中， 我们 研究了基于w e b 挖掘的p r o x y 端预取技术，目 的是减少用户 访问we b时所感知的延迟，为用户提供个性化的 预测预取服务。我们用代理服务 器上的访问日 志作为训练数据集，努力以 最小的数据集来建立高效的预测预取模 型。为了提高预取模型的性能，我们还根据w e b 的变化特点，引入了新闻性网页 的概念，并以 此为基础，在w e b 挖掘的事务识别阶段，象剔除噪声数据一样，把 这些新闻性网页去除，实验表明，它不仅可以有效地缩减预测预取模型的体积， 而且能够提高预测预取的性能。为了 追踪w e b 的 变化更新，弥补基于日 志挖掘的 预测模型只能反映用户过去的访问行为和只能为已有的用户提供预取服务的缺 憾，我们还提出了动态预测预取模型和增强型动态预测预取模型的方法，以预测 we b的最新变化，并为新增加的用户提供预测预取服务，实验表明，它们可以进 一步提高预测预取系统的性能。为了保证预测预取模型的效率，我们还采用 h a s h 函数、 链表等来组织模型文件和索引结构。 虽然我们在本文中所实现的几种预测预取模型都是以关系图为基础，但它同 样适用于p p m模型，并且在p p m上会取得更佳的性能。 关键词:we b 预取、we b 代理、 we b日志挖掘、关系图模型、p p m模型 东 北大学硕士学位论文 s t 叻 a n d l m p fe m e n t a t io n o n f ef e t c h t e c h n iq u e a t f o g y b a s e d o n 吩6 .m i n i n g ab s t r a c t t h e r a p i d d e v e l o p m e n t o f www c h a n g e d t h e m e t h o d t h a t t h e in f o r m a t i o n w as f o u n d e d a n d e x c h a n g e d . a l t h o u g h t h e s p e e d o f n e t w o r k h a s b e e n i m p r o v e d c o n s i d e r a b l y i n r e c e n t y e a r s , b u t t h e n e t w o r k b a n d - w i d t h d o e s n t c o m e u p w i t h t h e i n c r e as e o f u s e r s d e m a n d . l i m i t e d b y t h e n e t w o r k b a n d - w i d th , u s e r s a l w a y s s u ff e r fr o m l o n g t i m e w a i t i n g . w e b p re f e t c h i n g i s o n e o f t h e m o s t p o p u l a r a n d e ff e c t i v e s t r a t e g i e s f o r r e d u c in g t h e p e r c e i v e d a c c e s s d e l a y , i t h a s d r a w n e x t e n s i v e r e s e a r c h a tt e n t i o n r e c e n t l y . t h e w e b p r e f e t c h i n g b as e d o n w e b m i n i n g c a n g a i n i n g b e t t e r p e r f o r m a n c e , b e c a u s e it c a n s h o w u s e r a c c e s s b e h a v i o r m o r e a c c u r a t e , s o i t i s t h e f o c u s o f we b p r e f e t c h i n g re s e a r c h c o n t i n u o u s l y . t h e p r o x y s e r v e r , s i t t i n g i n t h e m i d d l e - t i e r i n t h e i n t e rne t i n fr as t r u c t u r e , h as t h e e ff e c t t h a t r e d u c in g t h e we b l a t e n c y , i f w e im p l e m e n t w e b p r e f e t c h i n g b as e d o n w e b l o g m i n in g a t p r o x y , i t m u s t t a k e s o p t i m iz a t i o n p e r f o r m a n c e . i n t h i s t h e s i s , w e d i s u s s e s a n d s u m m a ry s w e b p r e f e t c h i n g t e c h n o l o g y b a s e d o n w e b m i n i n g a t p r o x y , i t s p u r p o s e i s r e d u c i n g t h e w e b l a t e n c y a n d p r o v i d e s w e b p r e f e t c h i n g s e r v i c e o f i n d i v i d u a l i z a t i o n f o r u s e r . i n o r d e r t o i m p r o v e t h e p e r f o r m a n c e o f w e b p r e f e t c h i n g m o d e l , w e p r o p o s e t h e c o n c e p t o f n e w s we b p a g e a c c o r d in g t o th e c h a r a c t e r i s t i c o f we b , a n d r e m o v e t h e s e n e w s w e b p a g e s a s n o i s e d a t a w h e n m o d e l i s c r e a t e d , t h e e x p e r i m e n t i n d i c a t e s t h a t i t n o t o n l y c a n r e d u c e e ff e c t i v e l y t h e s i z e o f t h e m o d e l s , b u t c a n i m p r o v e th e p e r f o r m a n c e o f t h e p r e d i c t i o n m o d e l s a s w e l l 玩o r d e r to t r a c e t h e in c r e m e n t a ll y u p d a t e d o f w e b , a n d m e n d t h e d i s a d v a n t a g e o f w e b p r e f e t c h i n g m o d e l b as e d o n w e b l o g m i n i n g t h a t i t c a n t t r a c e t h e n e w e s t c h a n g e o f we b s c o n t e n t a n d u s e r s b e h a v i o r , w e p r o p o s e t h e m o d e l o f d y n a m i c p r e d i c t i o n l i s t a n d t h e m o d e l o f e x t e n d d y n a m i c p r e d i c t i o n l i s t , t h e y c a n p r o v i d e p r e f e t c h s e r v e r f o r n e w l y i n c re as e s u s e r s a c c o r d i n g t o t h e c h a n g e o f w e b , t h e e x p e r i m e n t i n d i c a t e s t h a t t h e y c a n f a r t h e r i m p r o v e t h e p e r f o r m a n c e o f p r e d i c t i o n e n g i n e . i n o r d e r t o g u a r a n t e e t h e e ff i c i e n c y o f we b p r e f e t c h i n g m o d e l , w e a d o p t h as h f u n c t i o n a n d l in k e d l i s t s t r u c t u r e t o o r g a n i z e mo d e l s d o c u me n t s a n d i n d e x . t h o u g h t h e m o d e l t h a t w e d e s i g n a n d im p l e m e n t i s b a s e d o n d e p e n d e n c y g r a p h i n t h i s t h e s i s , i t i s s u i t a b l e f o r p p m m o d e l t o o , a n d m u s t g a i n t h e b e t t e r p e r f o r m a n c e . k e y w o r d : w e b p r e f e t c h in g , we b p r o x y , w e b l o g m i n i n g , d e p e n d e n c y g r a p h m o d e l , p p m mo d e l 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。 论文中取得 的研究成果除加以 标注和致谢的地方外， 不包含其他人已 经发表或撰写 过的研究成果， 也不包括本人为获得其他学位而使用过的材料。 与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学 位 论 文 作 者 签 名: 除w衷 日期:2 0 0 s . / - is 学位论文版权使用授权书 本学位论文作者和指导教师完全了 解东北大学有关保留、 使用学位 论文的规定: 即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘， 允许论文被查阅和借阅。 本人授权东北大学可以 将学位论文 的全部或部分内 容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流， 请在下方签名; 否则视为不同意口 学 位 论 文 作 者 签 名 : 协淆象 签字日期:2 10 0 s . 1 - i s 导 师 签 名 :计柱 签字日 期: .-r ,- . i . r r 东北大学硕士学 位论文 第一章绪论 第一章绪 论 1 . 1 1 . 1 . 1 问题提出 背景 随着互联网技术的飞速发展和i n t e r n e t 信息量的急剧增长， 网络已成为人们获 取信息的重要来源。 近年来， 虽然网络速度得到了很大的提高， 但是， 由于i n t e rne t 的用户数量剧增以 及w w w ( w o r l d wi d e we b )信息量的爆炸式增长，使得网络 越来越拥挤， 用户的 服务质量( q o 5 ) 得不到很好的 保证， 用户在访问网 页之前往往 要忍受较长的等待时间，以 至于有人形象地将www戏称为w o l d w i d e w a i t . 据统计， i n t e rn e t 上数据流量增长的首要原因是www的增长。自 第一个we b 浏览器和服务器于1 9 9 1 年问世以 来， 它便以 惊人的 速度发展。 1 9 9 3 年初， we b 仅 由约5 0 台服务器组成。 在1 9 9 3 年底， we b 的流量也仅占i n t e rn e t 通信总量的1 %, 而到2 0 世纪9 0年代末时，we b的用户数目己经增至数亿，we b 站点的数量则达 到几百万， w e b 流量已占 有了i n t e rn e t 通信总量的7 5 % l 。 目 前， 在许多地方， i n t e r n e t 上数据流量的7 5 0% r -8 0 % 是h t t p即w e b 流量。 由于w e b 的分布式特性， 使得我们很难准确预计它的规模。目前， i n t e r n e t 上 用户和信息的增长依然强劲，而且必将持续一个相当长的时间，而网络带宽的增 长却总是滞后于用户对其需求的增长。 i n t e rn e t 上w w w用 户 和信息 量持续指数 级的 增长， 必然导 致网 络的 沉重 负载 和网络响应时间的延迟。近几年，虽然宽带接入技术和网络带宽的增长，使网络 延迟在一定程度上得到了缓解，但对网络服务质量的影响仍然存在。 特别地，由 于各方面条件的限制， i n t e rn e t 上的许多用户在享用w ) v w服务时， 还不得不采用 传统的拨号方式上网，再加上无线上网技术的迅速发展，这就决定了在可预见的 将来，许多用户还不得不继续忍受we b 延迟所带来的困扰。we b 延迟，即用户从 发送一个请求到他收到响应之间的时间差， 现在已 经成为衡童www服务性能的 一个重要参数。 事实上，w e b延迟问题，并非只受到用户的关心，i n t e rne t的运营商特别是 i c p ( i n t e m e t c o n t e n t p r o v i d e r ) 也迫切地要求减少用户的 访问延迟， 提高服务质量。 有一 个被 广泛引 用的 称为“ 八秒钟 规则” 的 统计 2 1 表明: 在电 子 通信中， 如果一个 w e b 站点的装载时间超过8 秒， 用户就更可能感到失败而离开这个站点。 因此， i c p 东北大学硕士学 位论文 第一章绪论 第一章绪 论 1 . 1 1 . 1 . 1 问题提出 背景 随着互联网技术的飞速发展和i n t e r n e t 信息量的急剧增长， 网络已成为人们获 取信息的重要来源。 近年来， 虽然网络速度得到了很大的提高， 但是， 由于i n t e rne t 的用户数量剧增以 及w w w ( w o r l d wi d e we b )信息量的爆炸式增长，使得网络 越来越拥挤， 用户的 服务质量( q o 5 ) 得不到很好的 保证， 用户在访问网 页之前往往 要忍受较长的等待时间，以 至于有人形象地将www戏称为w o l d w i d e w a i t . 据统计， i n t e rn e t 上数据流量增长的首要原因是www的增长。自 第一个we b 浏览器和服务器于1 9 9 1 年问世以 来， 它便以 惊人的 速度发展。 1 9 9 3 年初， we b 仅 由约5 0 台服务器组成。 在1 9 9 3 年底， we b 的流量也仅占i n t e rn e t 通信总量的1 %, 而到2 0 世纪9 0年代末时，we b的用户数目己经增至数亿，we b 站点的数量则达 到几百万， w e b 流量已占 有了i n t e rn e t 通信总量的7 5 % l 。 目 前， 在许多地方， i n t e r n e t 上数据流量的7 5 0% r -8 0 % 是h t t p即w e b 流量。 由于w e b 的分布式特性， 使得我们很难准确预计它的规模。目前， i n t e r n e t 上 用户和信息的增长依然强劲，而且必将持续一个相当长的时间，而网络带宽的增 长却总是滞后于用户对其需求的增长。 i n t e rn e t 上w w w用 户 和信息 量持续指数 级的 增长， 必然导 致网 络的 沉重 负载 和网络响应时间的延迟。近几年，虽然宽带接入技术和网络带宽的增长，使网络 延迟在一定程度上得到了缓解，但对网络服务质量的影响仍然存在。 特别地，由 于各方面条件的限制， i n t e rn e t 上的许多用户在享用w ) v w服务时， 还不得不采用 传统的拨号方式上网，再加上无线上网技术的迅速发展，这就决定了在可预见的 将来，许多用户还不得不继续忍受we b 延迟所带来的困扰。we b 延迟，即用户从 发送一个请求到他收到响应之间的时间差， 现在已 经成为衡童www服务性能的 一个重要参数。 事实上，w e b延迟问题，并非只受到用户的关心，i n t e rne t的运营商特别是 i c p ( i n t e m e t c o n t e n t p r o v i d e r ) 也迫切地要求减少用户的 访问延迟， 提高服务质量。 有一 个被 广泛引 用的 称为“ 八秒钟 规则” 的 统计 2 1 表明: 在电 子 通信中， 如果一个 w e b 站点的装载时间超过8 秒， 用户就更可能感到失败而离开这个站点。 因此， i c p 东 北大学 硕士学 位论文第一章绪 论 巴 巴 旦 旦 旦 口 口 目 巨 旦 组 组 旦 目 旦 巴 . 巨旦 旦 旦 口 口 出于经济利益的目的以 及商业竞争的需要，也迫切 地要求提高www月 及 务的响应 速度。 为了缓解网络带宽的需求与其增长之间的矛盾， 减少we b 延迟， 从9 0 年代初 期开始，i n t e rne t 的运营商和研究者们就一直在探索各种有效的方法。实践证明， 单纯依靠增加硬件和带宽，如提高网络主干线带宽、采用宽带接入方式等，不仅 代价高昂，而且也无法从根本上解决问题。目前，用于减少 we b访问延迟的主要 技术有两种，即we b 高速缓存和we b 预取技术。 受益于c p u高速缓存和文件系统高速缓存的成功， 在目 前的we b中广泛地采 用了高 速缓存技术，以 此来缩短用户所感知的访问 延迟。 w e b高速缓存，即w e b c a c h e ， 它利用ww w访问的时间局部性， 将最近访问 过的 文档保存在非服务器站 点，当用户再次访问 这些网 页时，浏览器直接从w e b 高速缓存中读取信息， 从而 避免了向 远程服务器发送请求，或者避免由 远程服务器发送完整的响应。 研究表 明， w e b高 速缓存的 命中 率可达到 3 0 % - 5 0 % (3 1 ， 它对节省网络带宽、 减少用户 感知的延迟时间是显而易见的。 然而， w e b高速缓存是一种单纯被动的高 速缓存技术， 它只能缓存用户最近 己 经访问 过的网页，而 对于用户未曾 访问 过的内 容则无法缓存，这样，当 用户访 问 新的w e b 站点 或没 有被缓存的内 容时， 其响 应性能 依 然得不到改 善。 为了 进一 步减少网 络的 延 迟时 间 ， 提高 网 络性能 和高 速 缓 存的 命中 率， 研究 者 们又 提出了 网页预取即w e b 预取技术。 w e b 预取是一种主动高 速缓存技术， 它利用ww w访 问 的空间 局部 性， 根 据 用户当 前的 请 求， 主 动 预 测 用 户下 一步 可能 浏览的 页 面， 然 后利 用网 络的 空闲 时间 预先 取出 存 放 在高 速缓 存中，以 此 来减少 用 户感 知 的 访 问延迟。 1 . 1 .2 w e b 代理与高速缓存 we b 预取是建立在w e b 高速缓存基础之上的， 所以， 要研究w e b 预取， 就必 须对we b 组件和w e b 高速缓存有深入透彻的了解。 w e b 消息最初是在用户和原始服务器之间直接传输的，它是传统的客户枷服 务器通信模式， 在客户机与服务器之间的路径上没有中间媒体。但随着w e b 的迅 速发展， 代理服务器( p r o x y ) 作为一种中间 媒体，己 逐渐成为i n t e rn e t 不可分割的一 个基础构件。 i n t e r n e t 最简单的结构如图 1 . 1 所示。即一个集团、一个单位或一个局域网内 的用户， 通过代理服务器作为访问i n t e rne t 的中转， 代理服务器通常放在防火墙内， 并且常常与防火墙放在同一台机器上。这样，当一个客户向服务器发起请求时， 东北大学硕士学位论文第一章 绪论 出于经济利益的目的以及商业竞争的需要，也迫切地要求提高w w w 服务的响应 速度。 为了缓解网络带宽的需求与其增长之间的矛盾，减少w e b 延迟，从9 0 年代初 期开始，i n t e m e t 的运营商和研究者们就一直在探索各种有效的方法。实践证明， 单纯依靠增加硬件和带宽，如提高网络主干线带宽、采用宽带接入方式等，不仅 代价高昂，而且也无法从根本上解决问题。目前，用于减少w e b 访问延迟的主要 技术有两种，即w e b 高速缓存和w e b 预取技术。 受益于c p u 高速缓存和文件系统高速缓存的成功，在目前的w e b 中广泛地采 用了高速缓存技术，以此来缩短用户所感知的访问延迟。w e b 高速缓存，即w e b c a c h e ，它利用w w w 访问的时间局部性，将最近访问过的文档保存在非服务器站 点，当用户再次访问这些网页时，浏览器直接从w e b 高速缓存中读取信息，从而 避免了向远程服务器发送请求，或者避免由远程服务器发送完整的响应。研究表 明，w e b 高速缓存的命中率可达到3 0 5 0 t 3 1 ，它对节省网络带宽、减少用户 感知的延迟时间是显而易见的。 然而，w e b 高速缓存是一种单纯被动的高速缓存技术，它只能缓存用户最近 已经访问过的网页，而对于用户未曾访问过的内容则无法缓存，这样，当用户访 问新的w e b 站点或没有被缓存的内容时，其响应性能依然得不到改善。为了进一 步减少网络的延迟时间，提高网络性能和高速缓存的命中率，研究者们又提出了 网页预取即w 曲预取技术。w e b 预取是一种主动高速缓存技术，它利用w w w 访 问钓空间局部性，根据用户当前的请求，主动预测用户下一步可能浏览的页面， 然后利用网络的空闲时间预先取出存放在高速缓存中，以此来减少用户感知的访 问延迟。 1 1 2w 曲代理与高速缓存 w e b 预取是建立在w e b 高速缓存基础之上的，所以，要研究w 曲预取，就必 须对w e b 组件和w e b 高速缓存有深入透彻的了解。 w e b 消息最初是在用户和原始服务器之间直接传输的，它是传统的客户机朋匪 务器通信模式，在客户机与服务器之间的路径上没有中间媒体。但随着w e b 的迅 速发展，代理服务器( p m x y ) 作为一种中间媒体，已逐渐成为i n t e m e t 不可分割的 个基础构件。 i n t e m e t 最简单的结构如图1 1 所示。即一个集团、一个单位或一个局域网内 的用户，通过代理服务器作为访问i n t e r n e t 的中转，代理服务器通常放在防火墙内， 并且常常与防火墙放在同台机器上。这样，当一个客户向服务器发起请求时， 7 东北大学硕士学位论文 第一章绪论 该请求被首先送到代理服务器，代理服务器分析该请求，假如代理服务器配有高 速缓存，并且代理服务器的高速缓存中有该请求数据，代理服务器就将高速缓存 中的数据直接发送给客户，对客户请求的响应也就到此为止；否则，代理服务器 将客户的请求转发给服务器或下一级代理服务器，当收到响应后，代理服务器再 将响应的数据传送给客户，同时在自己的高速缓存中保存一份该数据的拷贝。这 样，当再有客户请求相同的数据时，代理服务器就可以直接传送给客户，而不必 再向该服务器发起请求。很明显，当用户距离代理服务器比较近时，不仅用户感 知的网络延迟大大减少，而且也避免了冗余通信，节省了网络带宽。 翻1 1 a t c r n e t 最简单的结构 f i g u r e1 i t h es i m p l e s ta r c h i t e c t u r eo f i n t e m e t 严格来讲，w e b 代理与w e b 高速缓存是两种不同的技术，常规的代理只是转 发请求和响应，并不一定要求配备高速缓存。然而，由于目前的w e b 代理总是配 备了高速缓存，除了浏览器端的高速缓存外，w e b 高速缓存的使用总是与w e b 代 理相结合，以至于许多人都将它们视为同一实体。 w e b 代理或高速缓存有三种工作方式，即正向代理、透明代明和反向代理， 其中，我们平常所说的w e b 服务器高速缓存实际上就是指反向代理上的高速缓存， 它在本质上也是一种代理服务器高速缓存，只是被设定为一种特定的工作方式。 1 1 _ 3 高速缓存一致性 w e b 预取是建立在高速缓存基础之上的，w e b 预取可以提高高速缓存的命中 率，那么，通过增加高速缓存的体积，将高速缓存设置得足够大，使它缓存更多 的数据，是否也可以达到这目的呢? 如果这样，不是可以取消预取工作，或者 至少降低对预取的要求吗? 事实上并非如此简单。 。 3 东北大学硕士学位论文 第一章 绪论 高速缓存中保存的是原始服务器网页内容的拷贝，但是，服务器中的网页内 容却并非静止不变的，它始终处于不断的更新之中。换句话说，从上一次高速缓 存开始，高速缓存下来的内容有可能已经被修改了。假定我们有一台配有巨大容 量的代理服务器，有一用户在几天前访问了某个网页，且此后没有其它用户访问 更新过该网页，那么高速缓存中保存的是该网页几天前的内容，如果我们现在发 出对该网页的请求，代理服务器返回的将是一个不再“新鲜”的内容，显然，这 并非我们所期望的。要保持高速缓存中的内容始终是原始服务器的最新备份，并 不是一件容易的事，因为原始服务器在网页内容发生改变时，并没有什么机制来 通知代理服务器，高速缓存一致性( c a c h ec o h e r e n c e ) 就是解决这一问题的。 对于计算机各种形式的高速缓存，高速缓存一致性都是一个被深入研究的问 题。对于w e b 高速缓存，在过去几年中，已经有多种高速缓存一致性算法被提出。 例如，h t t p 1 1 协议提供了几种方法来维护高速缓存的一致性。如果原始服务器 为资源设置了指定的过期时间，则提供高速缓存服务的代理服务器必须遵守到期 时间。唯一的例外是在客户的请求上加入c a c h e c o n t r o l ：o n l y - i s c a c h e d 限制，这 些限制强迫代理返回一个未经原始服务器重检验的响应。如果原始服务器没有设 定到期时间，代理可以使用试探到期时间。试探到期经常与一致性检验联系在一 起。在w e b 上最常用的方法是用i f - m o d i f i e d s i n c e 请求标头发送g e t 或h e a d 请 求。i f - m o d i f i e d - s i n c e 标头传送资源上次修改的时间戳，该时间戳由原始服务器提 供。原始服务器会将i f - m o d i f i e d - s i n c e 标头中指定的时间戳与资源的最后一次修改 时问进行比较，如果资源没有改变，服务器将仅返回3 0 4n o tm o d i f i e d 响应，而无 响应主体；如果资源已经更新，服务器会返回一个恰当的状态码( 通常是2 0 0o k ) ， 并附上完整的响应主体。对于不经常改变的资源，这有助于减少不必要的数据传 输，缩短用户所感知的延迟。 维护w e b 高速缓存一致性的策略可分为两类：强一致性策略和弱一致性策略。 如果在每次高速缓存命中发生时，高速缓存代理服务器都发送一个重校验的请求， 则这种策略就叫作强一致性；如果高速缓存利用试探法来确定高速缓存响应是否 是新鲜的，丽不是每次高速缓存命中发生时都询问原始服务器，则这样的策略就 叫作弱一致性。 弱一致性策略又可分为基于租用的试探和基于时间的试探两种方法。对于基 于租用的方法，由服务器为每个响应设定一个租用期( 一个固定的时间量) ，代理 服务器高速缓存在其租用期内存储响应而不必重校验，如果在租用期内高速缓存 的资源发生改变，服务器就会通知高速缓存。这种方法把系统开销转移到了服务 器上，而且要求高速缓存和服务器的合作，服务器必须跟踪所有它许诺通知的高 4 东北大学硕士学位论文 第一辛绪论 速缓存代理，实现起来非常困难，所以，这种算法只是在文献中被广泛讨论，但 在实际的产品和系统中并没有得到具体的应用。对于基于时间的方法，代理服务 器为高速缓存中的每个响应设置一个t t l ( t i m e t o l i v e 生存期) 时间，当时间间 隔过去后，就认为响应已经失效；而在t t l 内，高速缓存不对响应进行重校验。 基于t t l 的方法使用起来非常灵活，对不同的响应可设置不同的t t l 值，这种方 法目前得到了广泛应用。 1 2 本文的研究目标 尽管w e b 代理和高速缓存的使用，能够有效地减少用户的访问延迟，并减轻 网络和原始服务器的负载，但是，w e b 代理和高速缓存在管理、通信等方面的复 杂性，以及高速缓存一致性的维护，又限制了其性能的进一步提高。目前，虽然 存储空间的价格越来越低，为提供超大规模的w e b 高速缓存提供了条件，但单纯 依靠增大高速缓存的体积，除了增加管理成本外，并不能持续地提升高速缓存的 命中率，这就为w e b 预取技术提供了广阔的生存空间。 w e b 预取，作为提升w e b 高速缓存命中率的种手段，已经越来越显示出它 的重要性，也越来越引起研究者和r r 厂商的重视。而代理服务器作为i n t e m e t 基 础构件的中间层，本身就具备了减少用户访问延迟的特性，在代理服务器上实施 w e b 预取，无疑会取得更佳的效果。本文的研究，即以代理服务器的预取为切入 点，我们的目标是通过识别各个用户不同的访问行为，从而为每个用户提供面向 个性化的预测预取服务，最终实现减少访问延迟、提高服务质量的目的。 1 3 课题来源 本文的研究来源于国家自然科学基金资助项目“i n t e m e t 上支持高质量 e s e r v i c e s 的零输入个性化技术的研究”( 项目批准号：6 0 1 7 3 0 5 1 ) ，该课题在对个 性数据采集技术、w e b 数据仓库技术、面向个性化的w e b 数据挖掘技术、个性化 规则解析技术以及个性化服务推荐技术等关键技术进行研究的基础之上，提出了 一种结合数据挖掘、规则解析和信息集成技术的c ( c o l l e c t i n g ) m ( m i n i n g ) r ( r e c o m m e n d i n g ) 个性化方法，并设计和实现了个个性化推荐系统s m a r t w e b 。 本文所研究的w e b 预取，就是基于面向个性化的w e b 数据挖掘技术，并最终 为用户提供个性化的预测预取服务，它是s m a r t w e b 的一个分支。 1 4 论文内容组织 本章从w e b 预取的背景入手，分析了w e b 代理与高速缓存技术的局限性，提 5 东 北大学 硕士学 位论文第一幸绪 论 . 曰. . . . . . . . 绝 口 ， . . . . . 口日 口 目 目 . . . 口 巨口.曰曰 ， 日 . . . . . 巨 曰口口. . . . . . .曰. . 口 . . . . . .口 . . . . 口 . . . . . . . 口 组 旦 速缓存代理，实现起来非常困难，所以，这种算法只是在文献中被广泛讨论，但 在实际的产品和系统中并没有得到具体的应用。对于基于时间的方法，代理服务 器为高速缓存中的每个响应设置一个 t t l ( t i m e - t o - li v e生存期)时间，当时间间 隔过去后，就认为响应已经失效;而在 t t l内，高速缓存不对响应进行重校验。 基于ttl的方法使用起来非常灵活， 对不同的响应可设置不同的t t l值， 这种方 法目前得到了广泛应用。 1 .2本文的研究目 标 尽管w e b 代理和高速缓存的使用，能够有效地减少用户的访问延迟，并减轻 网络和原始服务器的负载，但是，w e b代理和高速缓存在管理、通信等方面的复 杂性，以 及高速缓存一致性的维护，又限制了 其性能的进一步提高。目 前，虽然 存储空间的价格越来越低，为提供超大规模的we b高速缓存提供了条件，但单纯 依靠增大高速缓存的体积，除了 增加管理成本外，并不能持续地提升高速缓存的 命中率，这就为we b 预取技术提供了广阔的生存空间。 w e b 预取，作为提升we b 高速缓存命中率的一种手段，已经越来越显示出它 的重要性，也越来越引起研究者和 r r厂商的重视。而代理服务器作为i n t e rne t 基 础构件的中间层，本身就具备了 减少用户访问延迟的特性，在代理服务器上实施 w e b预取，无疑会取得更佳的效果.本文的研究，即以 代理服务器的预取为切入 点，我们的目 标是通过识别各个用户不同的访问 行为，从而为每个用户提供面向 个性化的 预测预取服务，最终实现减少访问延迟、提高服务质量的目的。 1 .3课题来源 本文的研究来源于国家自然科学基金资助项目“ i n t e rn e t上支持高质量 e - s e r v i c e s 的零输入个性化技术的研究”( 项目 批准号: 6 0 1 7 3 0 5 1 ) ，该课题在对个 性数据采集技术、we b 数据仓库技术、面向个性化的we b 数据挖掘技术、个性化 规则解析技术以 及个性化服务推荐技术等关键技术进行研究的基础之上，提出了 一 种结 合数 据 挖掘、 规 则 解 析和 信息 集成技 术的c ( c o ll e c t in g ) m ( m in i n g ) r ( r e c o m m e n d i n g ) 个性化方法， 并设计和实现了 一个个性化推荐系统s m a r t w e b . 本文所研究的we b 预取， 就是基于面向个性化的we b 数据挖掘技术， 并最终 为用户提供个性化的预测预取服务，它是s m a r t w e b的一个分支。 1 . 4论文内容组织 本章从 we b 预取的背景入手 分析了we b . 5 . 代理与高速缓存技术的局限性， 提 东 北大学 硕士学 位论文第一幸绪 论 . 曰. . . . . . . . 绝 口 ， . . . . . 口日 口 目 目 . . . 口 巨口.曰曰 ， 日 . . . . . 巨 曰口口. . . . . . .曰. . 口 . . . . . .口 . . . . 口 . . . . . . . 口 组 旦 速缓存代理，实现起来非常困难，所以，这种算法只是在文献中被广泛讨论，但 在实际的产品和系统中并没有得到具体的应用。对于基于时间的方法，代理服务 器为高速缓存中的每个响应设置一个 t t l ( t i m e - t o - li v e生存期)时间，当时间间 隔过去后，就认为响应已经失效;而在 t t l内，高速缓存不对响应进行重校验。 基于ttl的方法使用起来非常灵活， 对不同的响应可设置不同的t t l值， 这种方 法目前得到了广泛应用。 1 .2本文的研究目 标 尽管w e b 代理和高速缓存的使用，能够有效地减少用户的访问延迟，并减轻 网络和原始服务器的负载，但是，w e b代理和高速缓存在管理、通信等方面的复 杂性，以 及高速缓存一致性的维护，又限制了 其性能的进一步提高。目 前，虽然 存储空间的价格越来越低，为提供超大规模的we b高速缓存提供了条件，但单纯 依靠增大高速缓存的体积，除了 增加管理成本外，并不能持续地提升高速缓存的 命中率，这就为we b 预取技术提供了广阔的生存空间。 w e b 预取，作为提升we b 高速缓存命中率的一种手段，已经越来越显示出它 的重要性，也越来越引起研究者和 r r厂商的重视。而代理服务器作为i n t e rne t 基 础构件的中间层，本身就具备了 减少用户访问延迟的特性，在代理服务器上实施 w e b预取，无疑会取得更佳的效果.本文的研究，即以 代理服务器的预取为切入 点，我们的目 标是通过识别各个用户不同的访问 行为，从而为每个用户提供面向 个性化的 预测预取服务，最终实现减少访问延迟、提高服务质量的目的。 1 .3课题来源 本文的研究来源于国家自然科学基金资助项目“ i n t e rn e t上支持高质量 e - s e r v i c e s 的零输入个性化技术的研究”( 项目 批准号: 6 0 1 7 3 0 5 1 ) ，该课题在对个 性数据采集技术、we b 数据仓库技术、面向个性化的we b 数据挖掘技术、个性化 规则解析技术以 及个性化服务推荐技术等关键技术进行研究的基础之上，提出了 一 种结 合数 据 挖掘、 规 则 解 析和 信息 集成技 术的c ( c o ll e c t in g ) m ( m in i n g ) r ( r e c o m m e n d i n g ) 个性化方法， 并设计和实现了 一个个性化推荐系统s m a r t w e b . 本文所研究的we b 预取， 就是基于面向个性化的we b 数据挖掘技术， 并最终 为用户提供个性化的预测预取服务，它是s m a r t w e b的一个分支。 1 . 4论文内容组织 本章从 we b 预取的背景入手 分析了we b . 5 . 代理与高速缓存技术的局限性， 提 东北大学硕士学位论文第一章绪论 .口.口.口.口.口坦 鱼 ，. . . . . . .口 甲. 鱼旦. . . . . . . . . 门 . . . . 坦旦 旦 旦 ， . . 出了我们研究的方向。其后续各章节的内容安排如下: 第二章，w e b 预取的特点及研究进展。主要讲述we b 预取的特点、预取所采 用的主要方法、 在各个 位置实现预取的优劣、 基于日 志挖掘的w e b 预取特点、 w e b 预取目 前的应用研究进展和主要模型等。 第三章， 基于w e b 挖掘的p r o x y 端预取技术。 着重分析了在代理服务 器端实 现基于日 志挖掘的w e b 预 取时 所用到的 关键 技术及基本原理， 引 入了 新闻 性网 页 的 概念， 并以 此为基 础， 提出了 三种对现有的 基于日 志挖掘的 预测预取模型进行 改进的方案。 第四 章 ， 基 于w e b 挖 掘的p r o x y 端 预取 实 现。 以 关系图 模型为 基 础， 构 建了 一 个 代理 服务 器 端的 预 取 模 拟环 境， 模拟实 现了 我 们所 提出 的 几 种 预 测 预 取 系 统。 第五 章， 预 取 原 型 系 统 性能 检验。 用 真实的 代理 服 务器日 志， 检 验我 们 所提 出 的几 种预测 预取模型与 标准关系图 模型的 性能。 最 后， 是结 论 及 未 来 工作。 对代 理 服务 器 端 基于日 志 挖掘的w e b 预 测 预 取作 一个简单的总结，并提出未来研究的方向。 东 北大学 硕士学位论文第二章 we b 预取的 特点及研究进 展 第二章 we b 预取的 特点及研究进展 2 . 1 we b 预取的特点 在w e b中，预取技术是通过预测用户将来可能要访问的网页，并将它预先取 回到高速缓存中， 从而提高高速缓存的效率。 we b 预取是一种主动高速缓存技术， 它可以有效地降低网络延迟，增加高速缓存的命中率。但是，we b预取是以增加 网络流1a 和we b 组件的负载为代价的，一方面，执行预取算法要占用网络原有的 资源;另一方面，预取的内容并不能保证总是正确的，总有一部分用户所不需要 的冗余信息;此外，为了保证预取的性能，可能还需要在网络上传输一些除预取 内 容之外的其它附加信息。因此，如果预取算法的性能太差，不仅不能优化网络 性能，减少用户感知的网络延迟，反而会加重网络负担，使用户感知的网络延迟 增大。 要保证预取的性能，除设计高效的预取算法外，还必须尽量提高预取的准确 性，减少冗余信息和附加信息的传输。这实际上是一个矛盾的统一体，往往需要 设计者在各个问题之间进行平衡折衷。we b预取的应用主要取决于性能上的收获 是否大于代价。 2 .2 we b 预取的方法 w e b 预取的关键在于所使用的预测算法， 而预测算法的信息来源主要有两个: 访问 历史的统计信息或者是来自 于被访问的 对象本身( 例如 h t m l页面中的 超链 接) 。 根据w e b预取时 所采用的 预测算法，可将