一種基于編碼壓縮的數(shù)據(jù)廣播關(guān)鍵字索引方法

張 健,孫未未

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海201203)

一種基于編碼壓縮的數(shù)據(jù)廣播關(guān)鍵字索引方法

張 健,孫未未

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海201203)

無(wú)線環(huán)境的特殊性導(dǎo)致傳統(tǒng)的關(guān)鍵字檢索方法不能很好地用于周期數(shù)據(jù)廣播之中。倒排表是全文檢索中廣泛使用的一種索引技術(shù),但倒排表索引和基于哈希的數(shù)據(jù)索引無(wú)法解決索引結(jié)構(gòu)過(guò)大的問(wèn)題。為此,在周期數(shù)據(jù)廣播環(huán)境下,提出一種新型的關(guān)鍵字索引結(jié)構(gòu),對(duì)倒排表進(jìn)行編碼壓縮,縮減索引結(jié)構(gòu)來(lái)減少訪問(wèn)時(shí)間和調(diào)諧時(shí)間。同時(shí),與編碼壓縮索引相結(jié)合,設(shè)計(jì)一種周期數(shù)據(jù)廣播下的文檔調(diào)度方法。在真實(shí)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)結(jié)果表明,該方法可縮減索引結(jié)構(gòu)的規(guī)模,降低訪問(wèn)延遲和能耗。

無(wú)線環(huán)境;數(shù)據(jù)廣播;關(guān)鍵字檢索;索引;編碼壓縮;倒排表

1 概述

隨著無(wú)線設(shè)備的快速推廣和第4代無(wú)線網(wǎng)絡(luò)(4G)的迅速崛起,無(wú)線通信由于其靈活方便的特性而變得越來(lái)越重要。無(wú)線通信中的有限的帶寬和無(wú)線設(shè)備的電池續(xù)航能力成為了移動(dòng)計(jì)算中較為主要的關(guān)注點(diǎn),這使無(wú)線數(shù)據(jù)廣播會(huì)變成移動(dòng)通信領(lǐng)域一個(gè)比較重要的數(shù)據(jù)傳輸技術(shù)。一般來(lái)說(shuō),按照調(diào)度模式的不同,無(wú)線數(shù)據(jù)廣播可分成2種類型:Ondemand模式和周期廣播模式[1]。對(duì)于前者,用戶通過(guò)上行信道將請(qǐng)求發(fā)送給服務(wù)器端,服務(wù)器根據(jù)所有用戶的情況安排調(diào)度數(shù)據(jù)到信道當(dāng)中;在后者中,服務(wù)器端將存儲(chǔ)的數(shù)據(jù)按照某種調(diào)度方式在廣播信道上循環(huán)廣播,用戶端只需在廣播信道上偵聽(tīng),一旦發(fā)現(xiàn)自己感興趣的數(shù)據(jù)則下載到本地。本文的索引結(jié)構(gòu)面向的是周期數(shù)據(jù)廣播。周期數(shù)據(jù)廣播技術(shù)具有如下的優(yōu)點(diǎn):(1)周期數(shù)據(jù)廣播具有很高的帶寬利用率,它充分利用了廣播信道的帶寬作為下行信道,而且對(duì)上行信道幾乎沒(méi)有影響;(2)周期數(shù)據(jù)廣播具有良好的擴(kuò)展性,能夠支持一個(gè)區(qū)域內(nèi)任意數(shù)量的用戶同時(shí)訪問(wèn)數(shù)據(jù);(3)周期數(shù)據(jù)廣播對(duì)用戶的隱私提供很好的保護(hù)[2]。

周期數(shù)據(jù)廣播技術(shù)的特點(diǎn)能夠使它很好地利用到無(wú)線環(huán)境的數(shù)據(jù)通信中,而且數(shù)據(jù)廣播特別適用于公共信息的發(fā)布,如新聞廣播和地理交通信息,因?yàn)槊嫦虻挠脩羧后w非常大。基于關(guān)鍵字的查詢作為一種常用的查詢方式成為了數(shù)據(jù)廣播的一個(gè)重要的研究問(wèn)題。

周期廣播通常會(huì)使用一定的索引方法,把索引和數(shù)據(jù)一同插入到廣播的數(shù)據(jù)流中。通過(guò)索引信息,用戶被告知自己需求的數(shù)據(jù)包的到達(dá)時(shí)間,跳過(guò)不必要的下載。移動(dòng)設(shè)備可在無(wú)關(guān)數(shù)據(jù)的廣播時(shí)隙啟用休眠模式,節(jié)省能耗。無(wú)線數(shù)據(jù)廣播中有2個(gè)主要的性能指標(biāo):訪問(wèn)時(shí)間(Access Time)和調(diào)諧時(shí)間(Tuning Time),分別定義為從用戶提交查詢到最終獲得查詢結(jié)果的時(shí)間間隔和用戶保持監(jiān)聽(tīng)狀態(tài)的時(shí)間。

關(guān)于文本數(shù)據(jù)中關(guān)鍵字檢索的問(wèn)題,目前已有大批的索引結(jié)構(gòu)和查詢方法[3-8]。另一方面,在文本檢索中,一個(gè)關(guān)鍵字往往對(duì)應(yīng)多個(gè)文檔,可以將文檔調(diào)度問(wèn)題等同于數(shù)據(jù)廣播中的多數(shù)據(jù)項(xiàng)廣播調(diào)度問(wèn)題(如文獻(xiàn)[9-11])。但已有的數(shù)據(jù)調(diào)度算法都存在一定的局限性。為此,本文提出無(wú)線數(shù)據(jù)廣播環(huán)境下基于編碼壓縮的關(guān)鍵字查找索引方法,并與新型關(guān)鍵字索引相結(jié)合,對(duì)周期數(shù)據(jù)廣播中的文檔進(jìn)行調(diào)度。

2 相關(guān)研究

目前關(guān)于文本數(shù)據(jù)的索引結(jié)構(gòu)和查詢方法較多,例如,文獻(xiàn)[3]提出了能增量更新的查詢索引;文獻(xiàn)[4]討論了關(guān)鍵字檢索中的索引壓縮方法;文獻(xiàn)[5]研究了文本搜索引擎中倒排表的應(yīng)用;文獻(xiàn)[6]提出分布式系統(tǒng)的文本檢索優(yōu)化方法,但這些方法都是基于磁盤訪問(wèn)數(shù)據(jù)的,而在無(wú)線廣播環(huán)境中,文檔是根據(jù)時(shí)間線性地存儲(chǔ)在廣播信道中的,傳統(tǒng)方法不能夠直接地應(yīng)用于無(wú)線環(huán)境中。文獻(xiàn)[7]針對(duì)無(wú)線環(huán)境提出了B+-tree-倒排表的兩層索引結(jié)構(gòu)和(1,α(1,β))的分布策略。文獻(xiàn)[8]把關(guān)鍵字索引按哈希值映射到數(shù)據(jù)流中,并根據(jù)數(shù)據(jù)廣播的特點(diǎn)提出了優(yōu)化后效率較高的Merged-Hash索引方法。本文提出了一種新型的索引方法,它對(duì)倒排表進(jìn)行編碼壓縮,大大減小了索引結(jié)構(gòu),提高了系統(tǒng)的性能。

另一方面,可以把文檔調(diào)度問(wèn)題等同于數(shù)據(jù)廣播中的多數(shù)據(jù)項(xiàng)廣播調(diào)度問(wèn)題,例如,文獻(xiàn)[9]提出基于數(shù)據(jù)項(xiàng)的訪問(wèn)頻率進(jìn)行調(diào)度以減少訪問(wèn)延遲;文獻(xiàn)[10]針對(duì)多數(shù)據(jù)項(xiàng)廣播結(jié)合訪問(wèn)頻率和請(qǐng)求需要來(lái)生成調(diào)度序列;文獻(xiàn)[11]就多信道廣播環(huán)境下提出了數(shù)據(jù)項(xiàng)的廣播調(diào)度方法。已有的數(shù)據(jù)調(diào)度算法都存在一定的局限性:服務(wù)器必須事先知道請(qǐng)求的分布情況;限制了系統(tǒng)在實(shí)時(shí)環(huán)境下調(diào)度算法的實(shí)用性;文獻(xiàn)[12]提到了數(shù)據(jù)廣播中通過(guò)比較XML文檔的相似性來(lái)對(duì)文檔進(jìn)行調(diào)度;文獻(xiàn)[13]通過(guò)合并親密度高的文檔以減少冗余信息。不過(guò)半結(jié)構(gòu)化的XML文檔與非結(jié)構(gòu)化的純文本數(shù)據(jù)有所區(qū)別,不能直接使用到純文本數(shù)據(jù)的調(diào)度中。為此,本文提出一種基于編碼壓縮的數(shù)據(jù)廣播關(guān)鍵字索引方法。

3 編碼壓縮索引

3.1 數(shù)據(jù)廣播中的關(guān)鍵字查詢

為簡(jiǎn)化模型,本文考慮只具有一個(gè)基站和用戶共同使用一個(gè)廣播傳輸信道的場(chǎng)景。在廣播數(shù)據(jù)過(guò)程中,廣播的內(nèi)容在相當(dāng)長(zhǎng)的一段時(shí)間不會(huì)發(fā)生更新?；緯?huì)在每一個(gè)廣播周期廣播若干個(gè)文檔。每個(gè)文檔只在該廣播周期中出現(xiàn)一次,文檔集合記作D={doc1,doc2,…,docn}。每個(gè)文檔doci都會(huì)通過(guò)若干個(gè)數(shù)據(jù)包發(fā)送到廣播信道中。在此,數(shù)據(jù)包是廣播信道中最小的邏輯單元,每個(gè)數(shù)據(jù)包都具有相同的大小。為了方便,表1列出了下文中用到的符號(hào)。

表1 符號(hào)說(shuō)明

在文本檢索的應(yīng)用中,每個(gè)關(guān)鍵字都可能對(duì)應(yīng)數(shù)據(jù)流中的多個(gè)文檔?；蛘哒f(shuō),一個(gè)文檔會(huì)包含多個(gè)關(guān)鍵字。為了提供對(duì)這種關(guān)鍵字和文檔之間的多對(duì)多關(guān)系的支持,倒排表就被提出來(lái)應(yīng)用于文檔檢索系統(tǒng)中。倒排表的每個(gè)表項(xiàng)都包含一個(gè)關(guān)鍵字和包含該關(guān)鍵字的文檔的地址。在數(shù)據(jù)傳輸過(guò)程中,服務(wù)器通過(guò)流的形式來(lái)廣播倒排表索引和文檔。

通過(guò)上述介紹可以直觀地看出,每個(gè)關(guān)鍵字都是直接和文檔的地址相聯(lián)系起來(lái)的。如果文檔的數(shù)目比較大,而且部分關(guān)鍵字頻繁在不同的文檔中出現(xiàn),那么這部分的關(guān)鍵字對(duì)應(yīng)的表項(xiàng)將會(huì)有一個(gè)非常長(zhǎng)的文檔地址列表。這樣會(huì)導(dǎo)致整個(gè)索引結(jié)構(gòu)變得比較大,對(duì)整個(gè)系統(tǒng)的性能特別是訪問(wèn)時(shí)間會(huì)帶來(lái)負(fù)面影響。

本文提出了一個(gè)改進(jìn)的方法來(lái)克服原來(lái)的倒排列表在索引構(gòu)建方面的缺陷。相比于原來(lái)的倒排表索引,該方法采取了另一種方法來(lái)表示某個(gè)關(guān)鍵字對(duì)應(yīng)的文檔地址列表。

3.2 二元組

本文把文檔ID按照某種順序排列放到一個(gè)序列中,記作S={i1,i2,…,in}。舉例假設(shè)序列是按照ID的大小順序依次放置的,即ij=j。相比于倒排索引中關(guān)鍵字直接對(duì)應(yīng)到文檔偏移位置,編碼壓縮索引中的關(guān)鍵字ki是和一組偏移量二元組相聯(lián)系的,記作Fi={＜si1,ei1＞,＜si2,ei2＞,…,＜sin,ein＞} 。二元組＜si1,ei1＞表示的是在序列S中下標(biāo)由si1到ei1的所有文檔,這些文檔都包含關(guān)鍵字ki。

可直觀發(fā)現(xiàn),通過(guò)調(diào)整序列S中文檔的排列順序可以改變集合Fi中二元組的數(shù)目。面臨的問(wèn)題是怎么樣去安排序列S中文檔ID的排列順序能夠使集合Fi中的二元組的數(shù)目最少,因?yàn)榭s減二元組數(shù)目的大小能夠有效地縮減索引大小,從而減少訪問(wèn)時(shí)間。

3.3 最優(yōu)序列構(gòu)造

需求解的問(wèn)題是如何選擇序列S,使得達(dá)到最小。構(gòu)造一個(gè)圖G(V,E),圖上的每個(gè)節(jié)點(diǎn)都代表集合D中的一個(gè)文檔。也就是說(shuō),對(duì)于任何docj∈D,1≤j≤n,都有一個(gè)對(duì)應(yīng)的vj∈V(G)。對(duì)于任意2個(gè)節(jié)點(diǎn)vi和vj中間都有一條無(wú)向邊eij=(vi,vj)∈E(G),邊的權(quán)值w(eij)是該2個(gè)節(jié)點(diǎn)對(duì)應(yīng)的文檔所擁有的共同的關(guān)鍵字的數(shù)目。

定義θ(S)={(vi,vj)|doci和docj在序列S中相鄰}。由于序列S中沒(méi)有重復(fù)的文檔,故|S|=|V|,因此θ(S)構(gòu)成圖G的一條哈密頓回路。定義是關(guān)鍵字ki對(duì)應(yīng)文檔集合中任意2個(gè)文檔在序列S中是相鄰的次數(shù)。例如序列S={doc1,doc2,doc5,doc3,doc4},KD1={doc1,doc2,doc5},其中在序列S相鄰的文檔對(duì)有(doc1,doc2)和(doc2,doc5),可得MS(KD1)=2。

由于對(duì)于任意sj≤k≤ej和任意的l≠j,必然有dock不與＜sl,el＞中表示的任意文檔相鄰。否則＜sj,ej＞和＜sl,el＞可以合并為一個(gè)二元組。而在＜sj,ej＞中,相互相鄰的文檔對(duì)數(shù)為ej-sj。證明得:

3.4 文檔調(diào)度

假設(shè)查詢關(guān)鍵字ki對(duì)應(yīng)的文檔個(gè)數(shù)為N,廣播周期長(zhǎng)度是L,而且每個(gè)文檔的固定長(zhǎng)度記作LD,則滿足查詢關(guān)鍵字的文檔集合的總長(zhǎng)度是N×LD。又假設(shè)文檔隨機(jī)分布在信道上,docj和docj+1都屬于滿足關(guān)鍵字ki的查詢文檔,分布情況如圖1(a)所示?，F(xiàn)把docj和docj+1連續(xù)放置,如圖1(b)所示。按照查詢隨機(jī)進(jìn)入的條件,平均的訪問(wèn)時(shí)間的差值為:

圖1 文檔調(diào)度

可以看出,把具有相同關(guān)鍵字的文檔毗鄰放置時(shí),平均訪問(wèn)時(shí)間會(huì)相比下降。最優(yōu)的情況是查詢關(guān)鍵字ki對(duì)應(yīng)的文檔被連續(xù)廣播。此時(shí)的平均訪問(wèn)時(shí)間為:

在沒(méi)有進(jìn)行文檔的調(diào)度,只是隨機(jī)地把文檔插入到數(shù)據(jù)流中,可以近似看成文檔是均勻分布,此時(shí)的ki的平均訪問(wèn)時(shí)間為:

當(dāng)(N×LD)較小時(shí),訪問(wèn)時(shí)間ATavg′接近于廣播周期L,而進(jìn)行過(guò)調(diào)度后的ATavg接近于L/2,訪問(wèn)時(shí)間會(huì)大大減少。普遍來(lái)說(shuō)不能做到對(duì)于所有關(guān)鍵字都能把相應(yīng)的文檔聚集到相鄰位置,盡可能地把滿足同一關(guān)鍵字查詢的文檔歸置到一起有利于減少訪問(wèn)時(shí)間,而在解決尋求最優(yōu)序列使得最小的過(guò)程中,已將帶有相同關(guān)鍵字的文檔盡可能地放置在一起,從而使訪問(wèn)時(shí)間接近ATavg。

3.5 索引構(gòu)造

索引構(gòu)造先構(gòu)建倒排表,同時(shí)對(duì)于所有的文檔求出它們之間共有的關(guān)鍵字?jǐn)?shù)目,并根據(jù)其結(jié)果構(gòu)造圖G(V,E),求出最優(yōu)的哈密頓回路。此時(shí)獲得哈密頓回路上的節(jié)點(diǎn)對(duì)應(yīng)的文檔序列。根據(jù)文檔序列來(lái)把原始的倒排表轉(zhuǎn)化為編碼壓縮的表示。

索引部分按照獲得的序列把文檔按順序排放到數(shù)據(jù)流中,按照(1,α(1,β))的方法把索引樹(shù)和倒排表的索引插入到數(shù)據(jù)流中并廣播出去。在二元組＜s,e＞的具體表示方面,本文定義了2種指針表示方法,一種是如果s=e,即表示單個(gè)文檔時(shí),用單個(gè)指針來(lái)表示這個(gè)文檔,否則就用＜Offset1,Offset2＞的形式來(lái)表示,分別表示文檔區(qū)間中的第一個(gè)和最后一個(gè)文檔的到達(dá)時(shí)間。而在這2個(gè)時(shí)間之間所有到達(dá)的文檔都是符合查詢關(guān)鍵字的文檔。具體實(shí)現(xiàn)如圖2所示。

圖2 查詢處理過(guò)程

3.6 用戶查詢處理

查詢過(guò)程中用戶首先進(jìn)入信道下載第一個(gè)包,如果不是索引樹(shù)根節(jié)點(diǎn),則等待到下一個(gè)索引樹(shù)開(kāi)端的索引包到達(dá)時(shí)下載。然后用戶在索引樹(shù)上搜索自己需要的節(jié)點(diǎn)。對(duì)于索引樹(shù)節(jié)點(diǎn),用戶會(huì)把包含QS中關(guān)鍵字的孩子節(jié)點(diǎn)或?qū)?yīng)倒排表表項(xiàng)的指針插入到待下載隊(duì)列中;而對(duì)于倒排表節(jié)點(diǎn),用戶直接讀出文檔到達(dá)時(shí)間的區(qū)間,然后對(duì)關(guān)鍵字對(duì)應(yīng)的文檔集合取交集。最后用戶把文檔集合的所有數(shù)據(jù)包都下載下來(lái)。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)配置

本節(jié)通過(guò)實(shí)驗(yàn)對(duì)編碼優(yōu)化倒排表索引(CCKI)、倒排索引(IL)[7]和哈希索引(MBHS)[8]的性能進(jìn)行了比較。由于數(shù)據(jù)廣播可廣泛地使用于包括新聞和交通信息等方面的公共信息的發(fā)布,因此本文實(shí)驗(yàn)采用2個(gè)不同類型的數(shù)據(jù)集:澳大利亞地圖數(shù)據(jù)集(AU)[16]和《洛杉磯時(shí)報(bào)》的新聞文章(LA)[17]。2個(gè)數(shù)據(jù)集的詳細(xì)信息如表2所示。

表2 數(shù)據(jù)集詳細(xì)信息

模擬實(shí)驗(yàn)比較的性能包括訪問(wèn)時(shí)間(AT)和調(diào)諧時(shí)間(TT),實(shí)驗(yàn)中使用的數(shù)據(jù)的默認(rèn)參數(shù)值如表3所示。

表3 實(shí)驗(yàn)?zāi)J(rèn)參數(shù)說(shuō)明

實(shí)驗(yàn)?zāi)M進(jìn)行組織廣播索引和數(shù)據(jù),并周期性地通過(guò)一個(gè)信道將數(shù)據(jù)廣播給用戶。實(shí)驗(yàn)中有多個(gè)用戶在周期內(nèi)的任意一個(gè)時(shí)刻進(jìn)入信道,他們的查詢包括隨機(jī)生成的多個(gè)關(guān)鍵字。在下載完請(qǐng)求的文檔后,統(tǒng)計(jì)該用戶的訪問(wèn)時(shí)間和調(diào)諧時(shí)間。

4.2 性能比較與分析

本文首先通過(guò)實(shí)驗(yàn)評(píng)估對(duì)索引進(jìn)行編碼壓縮的效果;然后驗(yàn)證提出的文檔調(diào)度算法的優(yōu)化效果;最后分別針對(duì)不同文檔數(shù)目和不同關(guān)鍵字個(gè)數(shù),對(duì)編碼壓縮索引和倒排索引、哈希索引進(jìn)行訪問(wèn)時(shí)間和調(diào)諧時(shí)間的性能比較。

實(shí)驗(yàn)1比較經(jīng)過(guò)編碼壓縮前后的倒排表大小和原倒排表大小。由圖3可以看出,經(jīng)過(guò)壓縮后,索引大小相比原始倒排表明顯降低,而且隨著文檔數(shù)目的增多,壓縮效率更高。AU地圖數(shù)據(jù)集的壓縮率在55%～67%的范圍內(nèi),LA數(shù)據(jù)集文檔含關(guān)鍵字的數(shù)目較多且分布相對(duì)比較均勻,壓縮效果稍差,不過(guò)壓縮率也在74%～76%范圍內(nèi)。

圖3 壓縮前后倒排表大小比較

實(shí)驗(yàn)2通過(guò)與平坦調(diào)度(即文檔隨機(jī)均勻分布)在不同關(guān)鍵字條件下的比較,評(píng)估本文提出的調(diào)度算法對(duì)訪問(wèn)時(shí)間的優(yōu)化效果。從圖4可以看出,相比于平坦調(diào)度,本文提出的調(diào)度算法在訪問(wèn)時(shí)間方面占優(yōu),AU數(shù)據(jù)集和LA數(shù)據(jù)集的訪問(wèn)時(shí)間分別縮短了10%和1% ～4%。由于關(guān)鍵字?jǐn)?shù)目較少,AU數(shù)據(jù)集文檔調(diào)度產(chǎn)生的聚類效果相對(duì)更顯著。隨著關(guān)鍵字的數(shù)目增多,滿足查詢的文檔數(shù)目會(huì)減少,訪問(wèn)時(shí)間的優(yōu)化更加明顯。

圖4 壓縮前后文檔調(diào)度效果比較

實(shí)驗(yàn)3比較不同的索引方法在不同文檔數(shù)目和不同關(guān)鍵字個(gè)數(shù)條件下的性能。圖5顯示了隨著文檔數(shù)的增加,查詢的訪問(wèn)時(shí)間和調(diào)諧時(shí)間會(huì)呈上升趨勢(shì),原因是讀取的索引和文檔數(shù)據(jù)的增長(zhǎng)導(dǎo)致廣播周期變長(zhǎng)。而編碼壓縮索引在訪問(wèn)時(shí)間方面一直都優(yōu)于原始的倒排索引和哈希索引,因?yàn)樗饕笮〉拇蠓陆凳沟迷L問(wèn)時(shí)間有了明顯的減少。另一方面,編碼壓縮索引的調(diào)諧時(shí)間明顯低于其他方法,因?yàn)榈古疟肀粔嚎s,讀一個(gè)關(guān)鍵字所需下載的索引數(shù)據(jù)包數(shù)目減少,同時(shí)經(jīng)過(guò)調(diào)度能降低文檔數(shù)據(jù)包數(shù)量。從圖6可以看出,隨著關(guān)鍵字?jǐn)?shù)目上升,平均訪問(wèn)時(shí)間和調(diào)諧時(shí)間都會(huì)下降,因?yàn)闈M足查詢的文檔數(shù)目會(huì)逐漸減少。在不同的關(guān)鍵字?jǐn)?shù)目的情況下,編碼壓縮索引訪問(wèn)時(shí)間的表現(xiàn)有較大的優(yōu)勢(shì)。文檔類型的原因,AU數(shù)據(jù)在調(diào)諧時(shí)間方面相比大幅下降,LA數(shù)據(jù)集優(yōu)化效果稍差。

圖5 不同文檔數(shù)目時(shí)各調(diào)度方法的性能比較

圖6 不同關(guān)鍵字?jǐn)?shù)目時(shí)各調(diào)度方法的性能比較

5 結(jié)束語(yǔ)

本文研究了無(wú)線廣播環(huán)境下關(guān)鍵字檢索的問(wèn)題,提出了一種新型的關(guān)鍵字索引結(jié)構(gòu)——編碼壓縮關(guān)鍵字索引。關(guān)鍵字檢索在過(guò)去已經(jīng)有了大量的研究和發(fā)展,但是無(wú)線環(huán)境的特殊性導(dǎo)致了傳統(tǒng)的方法不能適用于數(shù)據(jù)廣播,而目前提出的倒排表索引和基于哈希的索引還無(wú)法解決索引結(jié)構(gòu)過(guò)大的問(wèn)題。本文提出的關(guān)鍵字索引,針對(duì)倒排表進(jìn)行編碼壓縮,縮減索引結(jié)構(gòu),并結(jié)合索引結(jié)構(gòu)對(duì)文檔進(jìn)行調(diào)度,使訪問(wèn)時(shí)間和調(diào)諧時(shí)間方面的性能都得到提升。最后通過(guò)真實(shí)數(shù)據(jù)的模擬實(shí)驗(yàn),驗(yàn)證了本文提出的關(guān)鍵字索引能夠?qū)σ缘古疟頌榛A(chǔ)的索引結(jié)構(gòu)進(jìn)行明顯縮減,降低訪問(wèn)時(shí)間。下一步工作是將該索引結(jié)構(gòu)從布爾模型擴(kuò)展到其他信息檢索模型,使其具有更廣的適用性;另一方面,在周期廣播中進(jìn)一步改進(jìn)純文本文件的調(diào)度方法,提高系統(tǒng)效率。

[1] Lee X J,Hu D L,Lee Q,et al.Data Broadcast.[M]// StojmenoviI.Handbook of Wireless Networks and Mobile Computing.[S.l.]:John Wiley&Sons,2002.

[2] Ku W S,ZimmermannR,WangH.Location-based Spatial Query Processing with Data Sharing in Wireless Broadcast Environments[J].IEEE Transactions on Mobile Computing,2008,7(6):778-791.

[3] Tomasic A,Garcia-Molina H,Shoens K A.Incremental Updates of Inverted Lists for TextDocumentRetrieval[J].SIGMOD Record,1994,23(2):289-300.

[4] Scholer F,Williams H E,Yiannis J,et al.Compression of Inverted Indexes for Fast Query Evaluation[C]// Proceedings of the 21st ACM SIGIR Conference on Research and Development in Information Retrieval. [S.l.]:ACM Press,2002:222-229.

[5] Zobel J,MoffatA.Inverted FilesforTextSearch Engines[J].ACM Computing Surveys,2006,38(2):1-56.

[6] Zhang J,Suel T.Optimized Inverted List Assignment in Distributed Search Engine Architectures[C]//Proceedings of International Parallel and Distributed Processing Symposium/International Parallel Processing Symposium.[S.l.]: IEEE Press,2007:1-10.

[7] Chung Y,Yoo S,Kim M H.Energy-and Latencyefficient Processing of Full-text Searches on a Wireless Broadcast Stream[J].IEEE Transactions on Knowledge and Data Engineering,2010,22(2):207-218.

[8] Yang Kai,Shi Yan,Wu Weili,et al.A Novel Hashbased Streaming Scheme for Energy Efficient Full-text Search in Wireless Data Broadcast[C]//Proceedings of the 16th International Conference on Database Systems for Advanced Applications.Hong Kong,China:[s.n.], 2011:372-388.

[9] Acharya S,Alonso R,Franklin M J,et al.Broadcast Disks: Data Management for Asymmetric Communications Environments[C]//Proceedings of International Conference on Management of Data.Melbourne,Australia:[s.n.],1995: 199-210.

[10] Chung Y,Kim M H.QEM:A Scheduling Method for Wireless Broadcast Data[C]//Proceedings of the 14th InternationalConference on Database Systems for Advanced Applications.Brisbane,Australia:[s.n.], 1999:135-142.

[11] 王豐亮,呂衛(wèi)鋒,諸彤宇,等.基于貪心策略的多信道數(shù)據(jù)廣播調(diào)度算法[J].計(jì)算機(jī)工程,2011,37(12): 179-181.

[12] Qin Y,Wang H,Sun L.Cluster-based Scheduling Algorithm for Periodic XML Data Broadcast in Wireless Environments[C]//Proceedings of IEEE International Conference on Advanced Information Networking and Applications. Ginowan City,Japan:IEEE Press,2011:855-860.

[13] 吳晶晶,毛鼎鼎,朱 良,等.基于文檔合并的XML無(wú)線數(shù)據(jù)廣播調(diào)度算法[J].計(jì)算機(jī)工程,2011,37(14):31-33.

[14] Garey M R,Johnson D S.Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. San Francisco,USA:[s.n.],1979.

[15] Applegate D,Bixby R,Chvátal V,et al.Concorde:A Code for Solving Traveling Salesman Problems[EB/OL]. [2013-10-11].http://www.tsp.gatech.edu/concorde. html.

[16] Rocha-Junior J B,N?rv?g K.Top-k Spatial Keyword Queries on Road Networks[C]//Proceedings of the 15th International Conference on Extending Database Technology.[S.l.]:ACM Press,2012:168-179.

[17] Los Angeles Times[EB/OL].[2013-10-11].http:// www.latimes.com/.

編輯 金胡考

A Keyword Index Method for Data Broadcast Based on Coding Compression

ZHANG Jian,SUN Weiwei
(School of Computer Science,Fudan University,Shanghai 201203,China)

The traditional keyword index methods are unable to be properly applied in the wireless data broadcast. Inverted list is an index technique widely used in the keyword search.Inverted list index and hash-based stream index can not be able to deal with the problem of a too large index structure.This paper proposes a new type of keyword index structure,and it manages to make the index structure smaller and shorten the tuning time by a way of coding compression.At the same time,it proposes a document scheduling method in the environment of periodic data broadcast. The experimental results demonstrate that the index structure is latency and energy-efficient,and outperforms inverted list index and hash-based stream index.

wireless environment;data broadcast;key word search;index;coding compression;inverted list

1000-3428(2015)01-0075-07

A

TP393

10.3969/j.issn.1000-3428.2015.01.014

國(guó)家自然科學(xué)基金資助項(xiàng)目(61073001)。

張 健(1988-),男,碩士研究生,主研方向:移動(dòng)數(shù)據(jù)管理;孫未未,副教授。

2014-02-25

2014-03-23 E-mail:zhang_jian@fudan.edu.cn

中文引用格式:張 健,孫未未.一種基于編碼壓縮的數(shù)據(jù)廣播關(guān)鍵字索引方法[J].計(jì)算機(jī)工程,2015,41(1):75-81.

英文引用格式:ZhangJian,SunWeiwei.A KeywordIndexMethodforDataBroadcastBasedonCoding Compression[J].Computer Engineering,2015,41(1):75-81.