張 健,孫未未

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

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

張 健,孫未未

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

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

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

1 概述

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

周期數(shù)據(jù)廣播技術(shù)的特點能夠使它很好地利用到無線環(huán)境的數(shù)據(jù)通信中,而且數(shù)據(jù)廣播特別適用于公共信息的發(fā)布,如新聞廣播和地理交通信息,因為面向的用戶群體非常大?；陉P(guān)鍵字的查詢作為一種常用的查詢方式成為了數(shù)據(jù)廣播的一個重要的研究問題。

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

關(guān)于文本數(shù)據(jù)中關(guān)鍵字檢索的問題,目前已有大批的索引結(jié)構(gòu)和查詢方法[3-8]。另一方面,在文本檢索中,一個關(guān)鍵字往往對應(yīng)多個文檔,可以將文檔調(diào)度問題等同于數(shù)據(jù)廣播中的多數(shù)據(jù)項廣播調(diào)度問題(如文獻(xiàn)[9-11])。但已有的數(shù)據(jù)調(diào)度算法都存在一定的局限性。為此,本文提出無線數(shù)據(jù)廣播環(huán)境下基于編碼壓縮的關(guān)鍵字查找索引方法,并與新型關(guān)鍵字索引相結(jié)合,對周期數(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)化方法,但這些方法都是基于磁盤訪問數(shù)據(jù)的,而在無線廣播環(huán)境中,文檔是根據(jù)時間線性地存儲在廣播信道中的,傳統(tǒng)方法不能夠直接地應(yīng)用于無線環(huán)境中。文獻(xiàn)[7]針對無線環(huán)境提出了B+-tree-倒排表的兩層索引結(jié)構(gòu)和(1,α(1,β))的分布策略。文獻(xiàn)[8]把關(guān)鍵字索引按哈希值映射到數(shù)據(jù)流中,并根據(jù)數(shù)據(jù)廣播的特點提出了優(yōu)化后效率較高的Merged-Hash索引方法。本文提出了一種新型的索引方法,它對倒排表進(jìn)行編碼壓縮,大大減小了索引結(jié)構(gòu),提高了系統(tǒng)的性能。

另一方面,可以把文檔調(diào)度問題等同于數(shù)據(jù)廣播中的多數(shù)據(jù)項廣播調(diào)度問題,例如,文獻(xiàn)[9]提出基于數(shù)據(jù)項的訪問頻率進(jìn)行調(diào)度以減少訪問延遲;文獻(xiàn)[10]針對多數(shù)據(jù)項廣播結(jié)合訪問頻率和請求需要來生成調(diào)度序列;文獻(xiàn)[11]就多信道廣播環(huán)境下提出了數(shù)據(jù)項的廣播調(diào)度方法。已有的數(shù)據(jù)調(diào)度算法都存在一定的局限性:服務(wù)器必須事先知道請求的分布情況;限制了系統(tǒng)在實時環(huán)境下調(diào)度算法的實用性;文獻(xiàn)[12]提到了數(shù)據(jù)廣播中通過比較XML文檔的相似性來對文檔進(jìn)行調(diào)度;文獻(xiàn)[13]通過合并親密度高的文檔以減少冗余信息。不過半結(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)鍵字查詢

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

表1 符號說明

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

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

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

3.2 二元組

本文把文檔ID按照某種順序排列放到一個序列中,記作S={i1,i2,…,in}。舉例假設(shè)序列是按照ID的大小順序依次放置的,即ij=j。相比于倒排索引中關(guān)鍵字直接對應(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),通過調(diào)整序列S中文檔的排列順序可以改變集合Fi中二元組的數(shù)目。面臨的問題是怎么樣去安排序列S中文檔ID的排列順序能夠使集合Fi中的二元組的數(shù)目最少,因為縮減二元組數(shù)目的大小能夠有效地縮減索引大小,從而減少訪問時間。

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

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

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

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

3.4 文檔調(diào)度

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

圖1 文檔調(diào)度

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

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

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

3.5 索引構(gòu)造

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

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

圖2 查詢處理過程

3.6 用戶查詢處理

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

4 實驗與結(jié)果分析

4.1 實驗配置

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

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

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

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

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

4.2 性能比較與分析

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

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

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

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

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

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

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

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

5 結(jié)束語

本文研究了無線廣播環(huán)境下關(guān)鍵字檢索的問題,提出了一種新型的關(guān)鍵字索引結(jié)構(gòu)——編碼壓縮關(guān)鍵字索引。關(guān)鍵字檢索在過去已經(jīng)有了大量的研究和發(fā)展,但是無線環(huán)境的特殊性導(dǎo)致了傳統(tǒng)的方法不能適用于數(shù)據(jù)廣播,而目前提出的倒排表索引和基于哈希的索引還無法解決索引結(jié)構(gòu)過大的問題。本文提出的關(guān)鍵字索引,針對倒排表進(jìn)行編碼壓縮,縮減索引結(jié)構(gòu),并結(jié)合索引結(jié)構(gòu)對文檔進(jìn)行調(diào)度,使訪問時間和調(diào)諧時間方面的性能都得到提升。最后通過真實數(shù)據(jù)的模擬實驗,驗證了本文提出的關(guān)鍵字索引能夠?qū)σ缘古疟頌榛A(chǔ)的索引結(jié)構(gòu)進(jìn)行明顯縮減,降低訪問時間。下一步工作是將該索引結(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].計算機工程,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無線數(shù)據(jù)廣播調(diào)度算法[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

國家自然科學(xué)基金資助項目(61073001)。

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

2014-02-25

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

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

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