一种基于编码压缩的数据广播关键字索引方法

张 健,孙未未

(复旦大学计算机科学技术学院,上海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.