一種基于編碼壓縮的數據廣播關鍵字索引方法

張 健,孫未未

(復旦大學計算機科學技術學院,上海201203)

一種基于編碼壓縮的數據廣播關鍵字索引方法

張 健,孫未未

(復旦大學計算機科學技術學院,上海201203)

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

無線環境;數據廣播;關鍵字檢索;索引;編碼壓縮;倒排表

1 概述

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

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

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

關于文本數據中關鍵字檢索的問題,目前已有大批的索引結構和查詢方法[3-8]。另一方面,在文本檢索中,一個關鍵字往往對應多個文檔,可以將文檔調度問題等同于數據廣播中的多數據項廣播調度問題(如文獻[9-11])。但已有的數據調度算法都存在一定的局限性。為此,本文提出無線數據廣播環境下基于編碼壓縮的關鍵字查找索引方法,并與新型關鍵字索引相結合,對周期數據廣播中的文檔進行調度。

2 相關研究

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

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

3 編碼壓縮索引

3.1 數據廣播中的關鍵字查詢

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

表1 符號說明

在文本檢索的應用中,每個關鍵字都可能對應數據流中的多個文檔。或者說,一個文檔會包含多個關鍵字。為了提供對這種關鍵字和文檔之間的多對多關系的支持,倒排表就被提出來應用于文檔檢索系統中。倒排表的每個表項都包含一個關鍵字和包含該關鍵字的文檔的地址。在數據傳輸過程中,服務器通過流的形式來廣播倒排表索引和文檔。

通過上述介紹可以直觀地看出,每個關鍵字都是直接和文檔的地址相聯系起來的。如果文檔的數目比較大,而且部分關鍵字頻繁在不同的文檔中出現,那么這部分的關鍵字對應的表項將會有一個非常長的文檔地址列表。這樣會導致整個索引結構變得比較大,對整個系統的性能特別是訪問時間會帶來負面影響。

本文提出了一個改進的方法來克服原來的倒排列表在索引構建方面的缺陷。相比于原來的倒排表索引,該方法采取了另一種方法來表示某個關鍵字對應的文檔地址列表。

3.2 二元組

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

可直觀發現,通過調整序列S中文檔的排列順序可以改變集合Fi中二元組的數目。面臨的問題是怎么樣去安排序列S中文檔ID的排列順序能夠使集合Fi中的二元組的數目最少,因為縮減二元組數目的大小能夠有效地縮減索引大小,從而減少訪問時間。

3.3 最優序列構造

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

定義θ(S)={(vi,vj)|doci和docj在序列S中相鄰}。由于序列S中沒有重復的文檔,故|S|=|V|,因此θ(S)構成圖G的一條哈密頓回路。定義是關鍵字ki對應文檔集合中任意2個文檔在序列S中是相鄰的次數。例如序列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＞中,相互相鄰的文檔對數為ej-sj。證明得:

3.4 文檔調度

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

圖1 文檔調度

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

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

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

3.5 索引構造

索引構造先構建倒排表,同時對于所有的文檔求出它們之間共有的關鍵字數目,并根據其結果構造圖G(V,E),求出最優的哈密頓回路。此時獲得哈密頓回路上的節點對應的文檔序列。根據文檔序列來把原始的倒排表轉化為編碼壓縮的表示。

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

圖2 查詢處理過程

3.6 用戶查詢處理

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

4 實驗與結果分析

4.1 實驗配置

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

表2 數據集詳細信息

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

表3 實驗默認參數說明

實驗模擬進行組織廣播索引和數據,并周期性地通過一個信道將數據廣播給用戶。實驗中有多個用戶在周期內的任意一個時刻進入信道,他們的查詢包括隨機生成的多個關鍵字。在下載完請求的文檔后,統計該用戶的訪問時間和調諧時間。

4.2 性能比較與分析

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

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

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

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

圖4 壓縮前后文檔調度效果比較

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

圖5 不同文檔數目時各調度方法的性能比較

圖6 不同關鍵字數目時各調度方法的性能比較

5 結束語

本文研究了無線廣播環境下關鍵字檢索的問題,提出了一種新型的關鍵字索引結構——編碼壓縮關鍵字索引。關鍵字檢索在過去已經有了大量的研究和發展,但是無線環境的特殊性導致了傳統的方法不能適用于數據廣播,而目前提出的倒排表索引和基于哈希的索引還無法解決索引結構過大的問題。本文提出的關鍵字索引,針對倒排表進行編碼壓縮,縮減索引結構,并結合索引結構對文檔進行調度,使訪問時間和調諧時間方面的性能都得到提升。最后通過真實數據的模擬實驗,驗證了本文提出的關鍵字索引能夠對以倒排表為基礎的索引結構進行明顯縮減,降低訪問時間。下一步工作是將該索引結構從布爾模型擴展到其他信息檢索模型,使其具有更廣的適用性;另一方面,在周期廣播中進一步改進純文本文件的調度方法,提高系統效率。

[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] 王豐亮,呂衛鋒,諸彤宇,等.基于貪心策略的多信道數據廣播調度算法[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無線數據廣播調度算法[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

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

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

2014-02-25

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

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

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