摘 要：Web預(yù)取技術(shù)和緩存技術(shù)對(duì)緩解訪問延遲有一定的作用，但各有利弊。這里將預(yù)取技術(shù)與語義緩存技術(shù)相結(jié)合，對(duì)用戶查詢的訪問頻率進(jìn)行實(shí)時(shí)監(jiān)測(cè)，并通過多項(xiàng)式回歸算法對(duì)用戶的下一周期訪問概率進(jìn)行預(yù)測(cè)。采用基于多項(xiàng)式回歸預(yù)取技術(shù)構(gòu)建的預(yù)測(cè)模型，可以實(shí)現(xiàn)動(dòng)態(tài)在線預(yù)測(cè)，既可避免興趣漂移引起的預(yù)取不確定性，又可以減少歷史信息的存儲(chǔ)量，科學(xué)合理地解決Web訪問延遲的問題。

關(guān)鍵詞：多項(xiàng)式回歸； 預(yù)取技術(shù)； 緩存技術(shù)； 訪問延遲

中圖分類號(hào)：TN91134； TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1004373X（2012）22008403

目前互聯(lián)網(wǎng)已經(jīng)成為人們生活中不可缺少的一部分，由于搜素引擎是獲得信息的主要手段，這使得網(wǎng)絡(luò)負(fù)載增大，不斷出現(xiàn)網(wǎng)絡(luò)擁塞的現(xiàn)象。如何減少Web訪問延遲，以提高訪問Web頁(yè)面的速度是學(xué)者們關(guān)心的問題。目前緩解網(wǎng)絡(luò)延遲的有效手段主要有Web緩存技術(shù)和預(yù)取技術(shù)［1］。

Web緩存技術(shù)是根據(jù)Web訪問的時(shí)間局部性原理，將訪問過的內(nèi)容以副本的形式存放在Cache中，待該內(nèi)容再次被訪問時(shí)，則由Cache中保留的副本提供。但是對(duì)于未曾訪問過的內(nèi)容卻無法緩沖，即用戶的興趣漂移可以引起不確定性， 因此Web緩存技術(shù)具有一定的局限性。隨著WWW上動(dòng)態(tài)內(nèi)容的增加以及個(gè)性化服務(wù)需求的加巨，利用緩存技術(shù)來改善網(wǎng)絡(luò)性能已不再顯著［1］，由此可見，減少Web訪問延遲只利用Web緩存技術(shù)已經(jīng)遠(yuǎn)遠(yuǎn)不夠。

1 預(yù)取技術(shù)

1.1 預(yù)取技術(shù)概述

預(yù)取技術(shù)是根據(jù)時(shí)間局部性向空間局部性進(jìn)行擴(kuò)展的原理，是在服務(wù)器處理用戶請(qǐng)求時(shí)，利用預(yù)取算法預(yù)測(cè)用戶接下來可能訪問的內(nèi)容，并利用網(wǎng)絡(luò)空閑時(shí)間段將預(yù)測(cè)內(nèi)容取回至緩存內(nèi)［2］。因此這種技術(shù)可以擬補(bǔ)緩存技術(shù)的不足，可以較好地減少網(wǎng)絡(luò)的訪問延遲，提高響應(yīng)速度［3］。

1.2 常用預(yù)取技術(shù)

目前比較流行的預(yù)取算法主要有基于流行度的算法、基于交互的算法、基于訪問概率的算法和基于數(shù)據(jù)挖掘的算法四類。常用的預(yù)取模型有基于PPM預(yù)取模型、基于Markov鏈預(yù)取模型和基于數(shù)據(jù)挖掘的預(yù)取模型等。由于預(yù)取算法主要是利用用戶訪問的歷史信息來進(jìn)行預(yù)測(cè)的，所以要保留大量的歷史信息。正是由于這些特點(diǎn)，使得目前的預(yù)取技術(shù)有一定的不足之處，例如網(wǎng)絡(luò)用戶的興趣漂移現(xiàn)象，導(dǎo)致歷史訪問數(shù)據(jù)不能準(zhǔn)確表達(dá)用戶的最新興趣方向；為了使預(yù)取結(jié)果準(zhǔn)確、命中率高，歷史訪問數(shù)據(jù)就必須有足夠的空間和時(shí)間進(jìn)行采集；對(duì)于龐大的數(shù)據(jù)預(yù)取算法的實(shí)施需要一定的系統(tǒng)開銷；算法得到的預(yù)取頁(yè)面數(shù)量很多，而滿足用戶即將訪問需求的卻數(shù)量很少，所以根據(jù)歷史訪問信息的預(yù)取技術(shù)并不能很好地、準(zhǔn)確地、迅速地使訪問者得到查詢結(jié)果，充分達(dá)到減少網(wǎng)絡(luò)的訪問延遲的目標(biāo)。

1.3 性能評(píng)價(jià)標(biāo)準(zhǔn)

衡量Web預(yù)取性能的度量最主要的有兩個(gè)，即準(zhǔn)確率和查全率。若不考慮緩存、網(wǎng)絡(luò)或時(shí)間等物理限制的情況，正確預(yù)測(cè)對(duì)象數(shù)目和總預(yù)測(cè)數(shù)目比值即為準(zhǔn)確率，也可以稱之為正確率或命中率；正確預(yù)測(cè)對(duì)象數(shù)目和用戶請(qǐng)求對(duì)象數(shù)目的比值即為查全率，也可以稱之為有用性［4］。

假設(shè)有N個(gè)請(qǐng)求序列，由預(yù)測(cè)模型產(chǎn)生共P個(gè)預(yù)測(cè)結(jié)果，其中P+個(gè)預(yù)測(cè)是正確的，則準(zhǔn)確率為 P+/P；查全率［5］為P+/N。

這兩種性能評(píng)價(jià)標(biāo)準(zhǔn)主要側(cè)重于預(yù)測(cè)效率和有效性兩個(gè)方面的性能評(píng)價(jià)。準(zhǔn)確率主要用來衡量預(yù)測(cè)算法正確性，而查全率主要用來衡量預(yù)測(cè)模型的適用性［6］。研究一個(gè)科學(xué)合理的Web預(yù)取技術(shù)，需要依據(jù)這兩個(gè)重要的評(píng)價(jià)標(biāo)準(zhǔn)。

2 關(guān)鍵技術(shù)實(shí)現(xiàn)

2.1 技術(shù)原理

預(yù)取技術(shù)是對(duì)Web緩存技術(shù)的有力補(bǔ)充，其目的是使有限的網(wǎng)絡(luò)資源得到合理的利用［7］。目前已經(jīng)存在利用隨機(jī)Petri網(wǎng)使Web緩存和預(yù)取技術(shù)相結(jié)合的技術(shù)［8］，而且證明了緩存與預(yù)取結(jié)合技術(shù)比單純的緩存技術(shù)或預(yù)取技術(shù)更能有效減少平均延遲、提高服務(wù)器的吞吐量［910］。緩存技術(shù)是數(shù)據(jù)庫(kù)優(yōu)化方法之一，尤其語義緩存技術(shù)很好地彌補(bǔ)了頁(yè)緩存和元組緩存對(duì)支持關(guān)系數(shù)據(jù)庫(kù)方面不夠完美的缺陷，語義緩存是將用戶的查詢信息及相應(yīng)結(jié)果保存到緩存中，重用緩存數(shù)據(jù)主要是利用查詢之間語義的相關(guān)性，根據(jù)與其對(duì)應(yīng)的語義描述來進(jìn)行。

2.2 基本思想

多項(xiàng)式回歸預(yù)取技術(shù)基本思想是把Web預(yù)取技術(shù)與語義緩存技術(shù)相結(jié)合，根據(jù)用戶訪問興趣度來進(jìn)行預(yù)取，主要是通過建立多項(xiàng)式回歸模型對(duì)用戶訪問頻率進(jìn)行預(yù)測(cè)，既而將用戶興趣度高的內(nèi)容取回至本地緩存中供用戶訪問。

2.3 預(yù)測(cè)模型的建立

首先設(shè)定統(tǒng)計(jì)周期，一般以24 h為一個(gè)統(tǒng)計(jì)周期。對(duì)各周期的各條語義緩存項(xiàng)訪問概率進(jìn)行統(tǒng)計(jì)，利用最近N個(gè)周期內(nèi)各語義緩存項(xiàng)的訪問概率來建立多項(xiàng)式回歸模型，在緩存中存儲(chǔ)語義緩存項(xiàng){K，P，T，Z}i最近N個(gè)周期的訪問頻率pij（j=1～N），及其在下一周期的訪問概率預(yù)測(cè)值POP。語義緩存項(xiàng)中K為用戶提交的查詢關(guān)鍵字集合，p為訪問概率預(yù)測(cè)值，t為該查詢語句有效期，z為查詢語句是否被預(yù)取。

假設(shè)某一訪問周期內(nèi)，Count為語義緩存項(xiàng)總訪問數(shù)量， Counti為每條語義緩存項(xiàng)的訪問數(shù)量，由此可定義第i個(gè)訪問周期內(nèi)各語義緩存項(xiàng)訪問概率為pi，pi為Counti與Count的比值。

2.4 訪問概率值預(yù)測(cè)

回歸預(yù)測(cè)法常用在市場(chǎng)預(yù)測(cè)方面。這種預(yù)測(cè)方法是把對(duì)因果關(guān)系的影響因素作為自變量，把預(yù)測(cè)對(duì)象作為因變量，用數(shù)學(xué)方法找出自變量與因變量之間近似的函數(shù)關(guān)系表達(dá)，利用樣本數(shù)據(jù)對(duì)模型參數(shù)進(jìn)行估計(jì)。其中具有多個(gè)自變量的稱為多元回歸分析。不管因變量與自變量存在何種關(guān)系，采用多項(xiàng)式回歸均可以接近某一函數(shù)。

計(jì)算緩存中各語義緩存項(xiàng)在下一周期的訪問概率預(yù)測(cè)值POP，首先建立多項(xiàng)式回歸模型，利用已經(jīng)統(tǒng)計(jì)的N個(gè)訪問周期的概率值對(duì)下一個(gè)周期的訪問概率進(jìn)行預(yù)測(cè)。假設(shè)在n個(gè)試驗(yàn)點(diǎn)x1，x2，…，xn獲得y的n個(gè)觀測(cè)值，建立模型如式（1）所示：yi = β0 + β1xi + β2x2i+…+ βpxpi + ei

i=1，2，…，n

（1） 假設(shè)誤差項(xiàng)為獨(dú)立、N（0，δ2）分布的，模型（1）用最小二乘法對(duì)參數(shù)進(jìn)行估計(jì)得到式（2）：fi＝0+1xN+1+...+pxpN+1

j=0，1，…p

（2）式中：j為βj的無偏估計(jì)；f即為某一語義緩存項(xiàng)第N+1周期訪問概率預(yù)測(cè)值。

2.5 預(yù)取隊(duì)列的生成

若第N+1周期預(yù)測(cè)的訪問概率POP大于閾值α，則可根據(jù)數(shù)據(jù)存儲(chǔ)標(biāo)識(shí)、數(shù)據(jù)有效期標(biāo)識(shí)來判斷哪些語義緩存項(xiàng)需要預(yù)取，從而生成預(yù)取隊(duì)列。

若數(shù)據(jù)有效期在有效范圍內(nèi)，如果語義緩存項(xiàng)是存儲(chǔ)在內(nèi)緩存的有效語義緩存區(qū)內(nèi)，且結(jié)果集存儲(chǔ)在外緩存有效數(shù)據(jù)區(qū)，則不需要重新預(yù)??；如果語義緩存項(xiàng)是存儲(chǔ)在外緩存的臨時(shí)語義緩存區(qū)內(nèi)，且結(jié)果集存儲(chǔ)在臨時(shí)數(shù)據(jù)區(qū)，則將語義緩存項(xiàng)移動(dòng)至內(nèi)緩存有效語義緩存項(xiàng)存儲(chǔ)區(qū)內(nèi)，結(jié)果集移動(dòng)至外緩存有效數(shù)據(jù)區(qū)內(nèi)。

若數(shù)據(jù)有效期不在有效范圍內(nèi)，且語義緩存項(xiàng)滿足預(yù)取條件，如果數(shù)據(jù)已經(jīng)失效則需要重新預(yù)取，即將語義緩存項(xiàng)填加至預(yù)取隊(duì)列中；如果數(shù)據(jù)保存在臨時(shí)數(shù)據(jù)區(qū)且數(shù)據(jù)失效則需要重新預(yù)取，即將語義緩存項(xiàng)填加至預(yù)取隊(duì)列表中。

2.6 預(yù)取技術(shù)的實(shí)施

當(dāng)用戶提交查詢請(qǐng)求時(shí)，同時(shí)在內(nèi)緩存和外緩存中進(jìn)行查詢匹配，若匹配結(jié)果為相交匹配，根據(jù)情況從有效或臨時(shí)數(shù)據(jù)區(qū)或是Web數(shù)據(jù)庫(kù)得到的查詢結(jié)果合并后返回給用戶，并把生成的新語義緩存項(xiàng)及其結(jié)果集保存到臨時(shí)數(shù)據(jù)區(qū)。當(dāng)外緩存的臨時(shí)語義緩存區(qū)滿時(shí)，則需要進(jìn)行替換。統(tǒng)計(jì)各語義緩存項(xiàng)在各周期的訪問量，建立預(yù)測(cè)模型并采用多項(xiàng)式回歸預(yù)測(cè)算法，預(yù)測(cè)下一周期各語義緩存項(xiàng)訪問概率并生成預(yù)取隊(duì)列，并訪問Web數(shù)據(jù)庫(kù)，由此獲取的結(jié)果集保存至外緩存有效數(shù)據(jù)區(qū)內(nèi)。

3 結(jié) 語

在Web數(shù)據(jù)集成環(huán)境下采用基于多項(xiàng)式回歸預(yù)取技術(shù)，根據(jù)用戶訪問的興趣度來進(jìn)行預(yù)取，可以實(shí)現(xiàn)動(dòng)態(tài)在線預(yù)測(cè)。對(duì)網(wǎng)絡(luò)銷售管理系統(tǒng)進(jìn)行商品查詢，從查詢響應(yīng)時(shí)間和預(yù)取準(zhǔn)確率兩方面進(jìn)行測(cè)試。實(shí)驗(yàn)表明基于多項(xiàng)式的預(yù)取技術(shù)，可有效提高用戶查詢響應(yīng)速度，減少網(wǎng)絡(luò)延遲，在性能評(píng)價(jià)的準(zhǔn)確率和查全率兩個(gè)方面達(dá)到了理想的標(biāo)準(zhǔn)值。

參 考 文 獻(xiàn)

［1］ XU Huanqing， WANG Yongcheng.A Web prefetching model based on analyzing user access pattern［J］.Journal of Software， 2003， 14（6）： 11421147.

［2］ 王世克，吳集，金士堯．Web預(yù)取模型分析＼[J＼]．微機(jī)發(fā)展，2005，15（8）：13.

［3］ NANOPOULO S A， KAT SARO S D， MANOLOPOULOS Y. A data mining algorithm for generalized Web prefetching ＼[J＼]. IEEE Trans. on Knowledge and Data Engineering， 2003， 15（5）： 11551169.

［4］ CHRISTOS B. Predictive prefetching on the Web and its potential impact in the wide area ＼[J＼]. World Wide Web， 2004， 7（2）： 143179.

［5］ 韓英杰，石磊，劉楊.Web 預(yù)取性能指標(biāo)準(zhǔn)確率與查全率的關(guān)系＼[J＼].計(jì)算機(jī)工程，2010，36（3）：6162.

［6］ SHI Lei， HAN Yingjie， DING Xiaoguang， et al. An SPNbased integrated model for Web prefetching and caching ＼[J＼]. Journal of Computer Science and Technology， 2006， 21（4）： 482489.

［7］ XU Baowen ， ZHANG Weifeng. Applying data mining to Web prefetching ＼[J＼]. Chinese Journal of Computers， 2001， 24（4）： 430436.

［8］ SHI L， HAN Y， DING X， et al. An SPN based integrated model for Web prefetching and caching ＼[J＼]. Journal of Computer Science and Technology， 2006， 21（4）： 482489.

［9］ 班志杰，古志民，金瑜.Web預(yù)取技術(shù)綜述＼[J＼].計(jì)算機(jī)研究與發(fā)展，2009，46（2）：202210.

［10］ DOMENECH J， GIL J A， SAHUQUILLO J， et al. Web prefetching performance metrics： a survey ＼[J＼]. Performance Evaluation， 2006， 63（9）： 9881004.

作者簡(jiǎn)介： 李春潔 女，1977年出生，黑龍江佳木斯人，講師，在讀碩士研究生。研究方向?yàn)閿?shù)據(jù)庫(kù)與知識(shí)庫(kù)。

王 銳 女，1974年出生，黑龍江佳木斯人，副教授，碩士。研究方向?yàn)閿?shù)據(jù)庫(kù)應(yīng)用。

李美珊 女，1982年出生，黑龍江七臺(tái)河人，講師，碩士。研究方向?yàn)檐浖こ獭?/p>