空间百度关键词工具

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2014,25(Suppl.
(2)):157168http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel/Fax:+86-10-62562563一种支持Top-k空间关键词检索的高效压缩索引周新1,2,张孝1,2,安润功1,2,薛忠斌1,2,王珊1,21(数据工程与知识工程教育部重点实验室(中国人民大学),北京100872)2(中国人民大学信息学院,北京100872)通讯作者:张孝,E-mail:zhangxiao@ruc.
edu.
cn,http://www.
ruc.
edu.
cn摘要:基于位置的服务可以指引用户找到在特定位置或区域内能够提供所需要服务的对象(比如找某个高校附近(经纬度标识)的咖啡店).
向这类服务提交一个查询位置和多个关键词,该类服务返回k个最相关的对象,对象和查询的相关性同时考虑空间相近性和文本相似性.
为了支持高效的top-k空间关键词查询,出现了多种混合索引,然而现有的这些索引为了提供实时响应均耗费大量存储空间.
提出一种基于压缩技术的索引CSTI,该索引显著减少了存储开销(至少减少80%甚至到两个数据量级),同时保持高效的查询性能.
大量基于真实和仿真数据集的实验结果表明,CSTI在空间开销和响应时间上均优于已有方法.
关键词:压缩索引;top-k;空间关键词检索中文引用格式:周新,张孝,安润功,薛忠斌,王珊.
一种支持Top-k空间关键词检索的高效压缩索引.
软件学报,2014,25(Suppl.
(2)):157168.
http://www.
jos.
org.
cn/1000-9825/14034.
htm英文引用格式:ZhouX,ZhangX,AnRG,XueZB,WangS.
Efficientcompressedindexfortop-kspatialkeywordquery.
RuanJianXueBao/JournalofSoftware,2014,25(Suppl.
(2)):157168(inChinese).
http://www.
jos.
org.
cn/1000-9825/14034.
htmEfficientCompressedIndexforTop-kSpatialKeywordQueryZHOUXin1,2,ZHANGXiao1,2,ANRun-Gong1,2,XUEZhong-Bin1,2,WANGShan1,21(KeyLaboratoryofDataEngineeringandKnowledgeEngineeringoftheMinistryofEducation(RenminUniversityofChina),Beijing100872,China)2(SchoolofInformation,RenminUniversity,Beijing100872,China)Correspondingauthor:ZHANGXiao,E-mail:zhangxiao@ruc.
edu.
cn,http://www.
ruc.
edu.
cnAbstract:Location-Basedservicesguideausertofindtheobjectwhichprovidesserviceslocatedinaparticularpositionorregion(e.
g.
,lookingforacoffeeshopnearauniversity).
Givenaquerylocationandmultiplekeywords,location-basedservicesreturnthemostrelevantobjectsrankedaccordingtolocationproximityandtextrelevancy.
VarioushybridindexeshavebeenproposedinrecentyearswhichcombineR-treeandinvertedindextoimprovequeryefficiency.
Unfortunately,thestate-of-the-artapproachesrequiremorespaceinordertoreduceresponsetime.
Cachemechanismisinefficientduetohugestorageoverhead.
Inthispaper,anovelindexbasedonindexcompressedtechnology(CSTI)isproposed,toanswertop-kSKQ.
CSTIsignificantlyreducesstorageoverhead(byatleast80%),whilemaintainingefficientqueryperformance.
ExtensiveexperimentsbasedonrealdatasetandsimulateddatasetconfirmCSTIiseffectiveandefficient.
Keywords:indexcompress;top-k;spatialkeywordquery位置信息的重要性日益显著,据统计,搜索引擎中20%的查询和位置相关,大量基于位置的服务方便了人们的生活.
广泛使用的移动和GPS设备令定位和获取位置信息更容易,而社交网络的快速发展使得分享位置信息基金项目:国家自然科学基金(61070054);国家重点基础研究发展计划(973)(2014CB340403);国家高技术研究发展计划(863)(2012AA011001);中央高校基本科研业务费专项资金(10XNI018)收稿时间:2014-05-07;定稿时间:2014-08-19158JournalofSoftware软件学报Vol.
25,Supplement(2),December2014变得普遍.
带有空间与文本信息的对象大量出现在网络中,通过位置和关键词访问对象的需求日益广泛.
为了支持高效的空间关键词检索,学者们提出多种索引方法.
现有方法主要采用紧耦合空间索引和文本索引的方式来提高查询性能,在空间剪枝的同时进行文本过滤[38].
然而目前这些方法普遍存在以下缺点:(1)存储开销大.
无论空间优先的索引(空间索引的节点集合倒排文件),还是文本优先的索引(关键词集成空间索引Tree),为了提高检索性能,重复存储大量信息,索引的存储空间超过原始数据的几十倍甚至上百倍.
(2)缓存机制无效.
由于紧耦合的混合索引占用大量存储空间,很难对其进行有效缓存.
而缓存机制是提供实时响应的关键技术.
(3)维护开销大.
基于空间索引R-tree的更新代价高,而空间索引和文本索引的紧耦合增大了代价.
因此,本文提出一种新的基于压缩技术的索引,以支持top-k空间关键词查询.
本文主要贡献如下:(1)新的高效压缩的索引结构.
本文提出基于压缩技术的新索引结构——CSTI(compressedspatial-textualindex).
CSTI采用文本优先的方式划分对象,对高频词,PCTree索引其倒排列表,能够显著降低存储开销,提高缓存命中率,进而缩短响应时间.
(2)新的快速top-k空间关键词检索算法.
基于CSTI,本文设计新的高效检索算法,快速响应top-k空间关键词查询.
(3)理论和实验证明了方法的有效性和高效性.
对于空间开销,本文给出了代价模型,估算CSTI节省的空间开销.
基于真实和仿真数据集,本文做了大量实验评估.
实验结果表明,CSTI在空间开销、磁盘I/O、响应时间上都优于目前的索引方法.
空间最多减少两个数量级,最少也降低80%.
1问题阐述基于位置的服务方便了我们的生活,利用百度、高德地图等容易查找感兴趣的地方,导航旅游路线.
我们感兴趣的地方不仅包含空间位置信息,还包含文本描述,称其为空间文本对象.
现在的手机均有定位功能,我们提交的请求不仅包含关键词信息,同时隐藏位置信息,基于位置的服务将返回和文本最相关且离查询位置最相近的对象.
定义1(空间文本对象).
每个空间-文本对象o(id,loc,doc)包含对象标识、空间属性和文本属性.
o.
id是对象标识;o.
loc是2维的空间位置点,常用经纬度表示;o.
doc标记对象的文本属性,由多个关键词组成.
定义2(查询请求).
查询请求q(loc,doc,k)包含3个属性.
q.
loc是用经纬度表示的2维空间点;q.
doc是查询的关键词;q.
k指定返回的结果数.
定义3(top-k空间关键词检索).
给定空间-文本对象集合O,空间关键词查询q(loc,doc,k),从O中检索k个最相关的空间-文本对象.
相关性同时考虑了空间相近性和文本相似性.
公式(1)~公式(3)分别给出查询和对象的相关性、空间相近性和文本相似性的计算方法.
1oqolocqlocodocqdocταδαθ1)max1dolocqlocolocqlocdδ=(2).
.
.
.
.
22.
.
.
.
.
.
todoctqdoctqdoctodoctqdoctodoctqdocodocqdocωωθωω∈∈∈=∑∑∑(3)其中,σ是调节因子,调节空间相近性和文本相关性的重要性.
d(o.
loc,q.
loc)是对象o和查询q的空间距离.
dmax是对象间最大距离.
ωt,doc是词t在文档doc中所占的权重.
例1:图1给出一个top-k空间关键词查询的示例.
空间范围内共有8个对象,位于q的旅游者寻找离自己最近且带自助的KTV.
不考虑文本相似性,对象o3离旅游者最近,但o3不是KTV.
虽然对象o6距离旅游者稍远,然而满足关键词的查询要求,综合距离的相近性和关键词的相似性,o6作为top1返回.
周新等:一种支持Top-k空间关键词检索的高效压缩索引159Fig.
1Asampleofspatialkeywordquery图1空间关键词查询示例2相关工作IR领域的学者们发现,仅用关键词不足以表示位置信息的邻接特性,于是探索了位置信息的表示和空间-关键词信息的检索方法[15].
此外,为了获得空间数据库中有用的文本信息,空间数据库提供空间关键词检索,返回满足查询的空间文本对象.
数据库中的空间关键词检索主要关注传统查询的性能改善和新型查询的应用.
空间关键词检索主要有3种传统查询[10]:Boolean范围查询,BooleankNN查询和top-kkNN查询(定义3).
为了提高检索性能,空间剪枝的同时进行文本过滤,组合不同空间索引(R-tree,Quad-tree,Grid,SpaceFillingCurve)和文本索引(invertedindex,signaturefile),从而,支持不同传统查询的混合索引被提了出来.
文献[10]对这些索引进行综合对比,并给出实验评估.
下面详细介绍两种支持top-k空间关键词查询的索引.
IR-tree[7],一种空间索引优先的混合索引方式,在R-tree的每个节点中加入invertedfile索引文本信息,达到空间剪枝的同时进行文本过滤.
文献[8]提出一种新的混合索引——S2I.
S2I采用文本优先的方法,为具有相同关键词的对象创建倒排列表.
对于非频繁词,使用文件块存储相应的倒排列表;对频繁词,S2I构建aR-tree[9]索引包含该频繁词的对象.
相对于IR-Tree,S2I减少了大量的磁盘I/O,提高了检索性能,然而随着数据量的增大,每个对象的文本信息增多,S2I检索性能迅速下降.
除以上传统查询外,学者们(特别是国内学者)探索了新型查询,提出相应的索引架构和检索算法[1115].
本文致力于top-k空间关键词检索的性能改善.
目前支持top-k空间关键词查询的索引均是紧耦合的混合索引,为了降低响应时间而牺牲了大量空间.
而本文所提出的基于压缩的空间-文本索引——CSTI则采用另外的技术路线,即:通过压缩记录提高空间利用率降低树高、提高缓存命中率,从而改善检索性能.
3基于压缩的空间-文本索引(CSTI)减少索引的空间消耗不仅节省存储代价,同时缩短数据从磁盘到内存的传输时间,提高缓存命中率,改善查询性能.
因此,本文提出基于压缩的空间-文本索引——CSTI.
CST是基于倒排关键词的索引,对不同频率关键词的倒排列表区别存储,集成了S2I的优点.
然而对于频繁词的检索,CSTI采用了新的索引结构——前缀压缩树(PCTree).
对于非频繁词的检索,CSTI采用Block结构存储其倒排列表.
为了支持高效的压缩,空间查找表用来维护位置信息.
CSTI主要包括4个组件:字典表、空间查找表、PCTree和Block.
图2给出了对应于图1中示例的CSTI索引架构.
CSTI的Block结构相对简单,对于倒排列表中的每个对象,记录对象标志id和关键词在对象中的权重(用TF表示),如图2(c)所示.
下面详细介绍CSTI的其他组件.
3.
1字典表作为CSTI的重要组件,字典表存储关键词的元信息,主要包括:文档频率(df)、类型标志(type)和文件指针(pointer).
文档频率表示某个关键词在所有对象中出现的次数;类型标志表明关键词对应的倒排列表采用何种方式索引;文件指针指向存储倒排列表的文件.
例2:图2(a)给出例1对应的字典表,假设文档频率大于3的关键词是频繁的,"buffet"采用PCTree索引其倒160JournalofSoftware软件学报Vol.
25,Supplement(2),December2014排列表,其他关键词采用Block索引其倒排列表.
Fig.
2StructureofCSTI图2CSTI索引架构3.
2空间查找表为了便于压缩,CSTI采用空间填充曲线技术将2维空间坐标转换为1维.
常用的Zorder,Hilbert等空间填充曲线均可用来编码位置信息,CSTI采用Zorder编码.
为了有效地利用压缩机制,保证空间位置相近的对象在倒排列表中位置也相近,同时减少索引的空间消耗,CSTI按照Zorder编码的连续性重新为每个对象分配id,形成空间查找表.
实际存储时,对象id将代替Zorder编码表示空间特性.
图2(b)显示了例1对应的空间查找表.
相应的Zorder编码和对象id映射关系如图2所示.
3.
3前缀压缩树(PCTree)依据Zipf规律,少量的关键词频繁出现,大量的关键词不频繁出现,因此分开存储不同频率关键词的倒排列表具有重要意义.
CSTI分别采用PCTree和Block存储频繁词和非频繁词的倒排列表.
降低索引的存储开销,有效利用缓存机制是CSTI的核心工作.
CSTI的空间查找表重新分配对象id,因此,可以高效地利用倒排索引的压缩技术.
倒排索引常用的压缩算法有变长字节、Gammacoding、S9、S16、PFD等编码方法[16].
本文采用PFD压缩算法对频繁词的倒排列表进行压缩.
为了防止每次都要从头解压倒排列表,同时高效地进行空间剪枝,CSTI采用前缀压缩树(prefix-basedcompressedtree,简称PCTree,)合理地组织压缩数据块.
PCTree是一棵自底向上构建的aR-tree变种(构建方法参照文献[17]).
依据Zorder填充曲线的特性:(a)如果子空间A包含子空间B,那么子空间A的Zorder编码是子空间B的Z-order编码的前缀;(b)如果空间A和空间B没有共同前缀,那么A和B一定不相交.
因此,PCTree将具有公共前缀编码的空间坐标划分到一起,形成aR-tree的叶节点.
相比较传统的aR-tree,该方法避免了R-Tree节点间的重叠,增强了空间剪枝能力.
同时,CSTI对aR-tree每个叶节点进行PFD压缩,进一步减少了空间开销.
PCTree不仅具有aR-tree的优点,还增强了aRtree的空间剪枝能力;PCTree压缩了叶节点,树高和节点数远少于aR-tree,存储和检索性能均优于aR-tree.
例3:图2(d)给出关键词"buffet"对应的PCTree,左边是平面表示,右边是树形结构.
对象o4和o5的Zorder编码分别为100111和101110,二者具有公共前缀10*1**.
类似地,对象o6和o8的公共前缀为11****,对象o2自成一个叶子节点,前缀是其Zorder编码本身.
PCTree的节点中还存储了子树中关键词的最大权重,可以高效地计算节点和查询的相关性,空间剪枝的同时进行文本过滤.
3.
4空间开销分析一棵存储N条记录的aR-Tree,最大可能的树高如公式(4)所示,这棵aR-tree的节点总数可以通过公式(5)获得.
PCTree的叶节点包括元信息和压缩的数据.
假设PFD算法的平均压缩比是γ(大于1),叶节点的存储代价如公式(7)所示,其中,entrySize是元信息占用的空间,(5m*8)/γ表示压缩后的数据量.
同时,公式(8)和公式(9)分别给出周新等:一种支持Top-k空间关键词检索的高效压缩索引161aR-Tree和PCTree的空间代价模型,公式(10)计算节省的空间开销.
公式(8)给出的中间节点和叶节点的总和(见公式(5))乘以每个节点的块大小即为aR-Tree的空间消耗;而PCTree的叶节点与中间节点的存储模型不同,公式(9)需要组合中间节点的空间消耗和叶节点的空间消耗.
maxlog1mhN=(4)max21.
.
.
1hiiNNNmmm==+++∑(5)blockSizementrySizeβ=*(6)(,)58/cleafpctreeentrySizemγ=+*(7)max1()hiiNcrtreeblockSizem==*∑(8)max1155hiiNNcpctreeblockSizecleafpctreemm==*+*∑(9)max1()()4184()5555savehiicrtreecpctreeNrcrtreementrySizeNmmββγ=**∑(10)其中,hmax表示最大树高;m是aR-tree节点能容纳的最少entry数,PCTree叶节点的容量为5m(每个entry占8B),中间节点的容量与aR-tree一致.
blockSize表示aR-tree节点的空间代价,通常设为4096B;β表示节点填充率,公式(6)给出m,blockSize,β,entrySize的关系;entrySize表示aR-tree节点中entry的大小,本文为54B.
从以上推导公式可以看出,PCTree的空间代价至少比aR-tree节省80%.
同时PCTree叶节点减少为原来的20%,中间节点也大量减少,导致部分PCTree的树高降低.
同时,PCTree避免节点间的重叠,因此,PCTree的性能优于aR-Tree,CSTI能够支持快速响应top-k空间关键词查询.
下面的第4节将详细阐述top-k空间关键词检索算法.
4Top-k空间关键词检索算法本文提出的索引架构CSTI支持实时响应top-k空间关键词查询.
对于单关键词检索和多关键词检索,本文给出SSKQ算法和MSKQ算法以响应查询.
4.
1单关键词检索算法算法SSKQ维护一个堆H存放候选结果.
对于查询q,首先查找字典表,找到关键词类型,如果是非频繁词(行3),依据文件指针找到存储位置,插入数据块中的所有对象到堆(行4~行7),返回前k个结果(行27);如果是频繁词(行8),遍历PCTree找到相应的压缩块,解压数据,插入到堆H中(行9~行21).
PCTree维护了关键词的最大权重和对象的MBR信息,采用best-first搜索策略,因此最相关的结果总是排在H的最前面.
当找到top-k结果时,终止查询,返回结果(行22~行27).
算法1.
单关键词检索SSKQ(Algorithm1.
SSKQ(CSTS,q)).
Input:indexCSTI,queryq(loc,ti,k);Output:top-kobjectswhichhavehighestscore.
1:MaxHeapH←φ2:type←lookupDictionary(term)3:iftypeisno-compressedthen4:Listl←traverseBlock(term,type)5:foreachspatial-textualobjecto∈ldo6:H.
insert(o,τ(o,q))162JournalofSoftware软件学报Vol.
25,Supplement(2),December20147:endfor8:else9:H.
insert(PCTreeti.
root);10:whileH.
isNotEmpty()do11:Entrye←H.
pop();12:ifeisinternalnodethen13:foreachnoden∈edo14:H.
insert(n,τ(n,q));15:endfor16:else//eisaleaf-node17:Entryd←decompressNode(e);18:foreachspatio-textualobjecto∈ddo19:H.
insert(o,τ(o,q))20:endfor21:endif22:ifH.
kisavailablethen23:break;24:endif25:endwhile26:endif27:returntop-kobjectinHasresult例4:对应于例1的top-1查询q(buffet),"buffet"检索对应的PCTree.
首先,将根节点加入大顶堆H中,计算其孩子和q的相关性,由图可知,最相关的孩子为节点e1,因e1是叶子节点,计算叶子对象和查询的相关性,可知对象o2最相关,返回结果o2.
4.
2多关键词检索算法公式(1)中的相关性函数依照公式(11)分解,多关键词检索分解为多个单关键词检索,通过集成每个单关键词的部分得分(公式(12))来完成检索过程.
因为对象和查询的位置信息不会发生变化,所以检索关键词i得出的位置信息将成为检索关键词j时的参照,公式(13)给出对象和查询相关性的下界.
,.
.
,.
.
11)()(1)().
todoctqdoctodoctqdocoqolocqlocodocqdocolocqlocIDFtplocqlocIDFtqdocταδαθαδαλδααλ∈∈∑∑(11),.
(,)(1)().
itodocplocqlocoqIDFtqdocδτααλ12)(,).
iplocqlocoqqdocδτα=(13)::jjiiioLjoLOoqoqττ∈=+∑∑(14)::(,)max(jjijioLjoLOoqoqτμτ∈=+∑∑(15)MSKQ算法的检索过程如下:首先为每个单关键词维护元信息(行2~行4).
选择关键词检索源Si,访问其中的对象p,计算p的相关性和下界p_,更新Si的上界ui,加入p到候选集C(行6~行11)中.
更新C中每个对象的上周新等:一种支持Top-k空间关键词检索的高效压缩索引163界(行13),当一个对象的下界大于C中所有对象的上界时,报告该对象为结果,返回k个结果则终止检索过程(行15~行17).
当结果数m小于k时,则返回C中有最高下界的(km)个对象(行21).
多关键词检索面临的挑战是如何选择每次要集成的单关键词检索源以尽快找到top-k结果,提前终止检索.
本文给出两种策略用于选择检索源:(1)轮回选择.
该策略顺序选择和查询对应的关键词检索源,每轮访问检索源的顺序是一致的.
该选择策略简单易行,然而它没有考虑候选结果的相关性,多次迭代才能找到最终结果.
下面给出优化的选择策略.
(2)最优选择.
每次迭代,该策略均要为每个检索源预取一个对象,和查询相关性最大的对象所在的检索源将被访问.
因为最相关的对象最先访问,该策略可以尽快找到总体最优的最终结果,提前终止检索过程.
例5:对应例1中的查询q(KTV,buffet),表1给出采用轮回选择策略的多关键词检索过程.
加粗的数值展示候选对象的变化过程,通过5步迭代,最终o6作为top-1结果返回.
表1多关键词检索的迭代过程PCTreet3Blockt5候选集C{p[p_,p_]}τt3(o2,q)=0.
2676τt5(o6,q)=0.
4105o2[0.
3926,0.
6781],o6[0.
5355,0.
6781]τt3(o5,q)=0.
2407o2[0.
3926,0.
6781],o6[0.
5355,0.
6512],o5[0.
3234,0.
6512]τt5(o7,q)=0.
2970o2[0.
3926,0.
5646],o6[0.
5355,0.
6512],o5[0.
3234,0.
5377],o7[0.
4075,0.
5377]τt3(o6,q)=0.
2242o2[0.
3926,0.
5646],o6[0.
6346,0.
6346],o5[0.
3234,0.
5377],o7[0.
4075,0.
5212]算法2.
多关键词检索MSKQ(Algorithm2.
MSKQ(CSTI,q)).
Input:indexCSTI,queryq(loc,doc,k);Output:top-kobjectswhichhavehighestscore.
1:C←//Listofcandidateobjects.
2:foreachtermti∈q.
docdo3:Si←source(q,ti);Li←;ui←∞;4:endfor5:whileSisuchthatSi≠do6:i←selectSource(q.
doc);7:p←Si.
next();ui←τi(p,q);Li←Li∪p;8:p_←updateLowerBound(p);//Formula149:if!
(p∈C)then10:C←C∪p;11:endif12:foreachp∈Cdo13:p—←updateUpperBound(p);//Formula1514:endfor15:whilep∈C,o∈C:p_≥max(o—)do16:C←C–p;17:reportsp,haltifkobjectshavebeenreported;18:endwhile19:endwhile20:iflessthankobjectshavebeenreportedthen21:returntheobjectsinCwithhighestlowerboundscorep_22:endif164JournalofSoftware软件学报Vol.
25,Supplement(2),December20145实验评估本文使用真实和仿真数据集评估CSTI索引的性能,并与目前两种经典索引IR-tree和S2I进行了对比(感谢IR-tree和S2I的作者分享源码).
CSTI采用Java实现.
所有的实验均在配置4GB内存、2.
67GHzIntel双核处理器的PC机上完成.
5.
1数据集本文选择1个POI(pointofinterest)真实数据集和仿真多个Tweet数据集进行了实验评估.
POI数据集记录了欧洲多国的餐馆、景点等信息,然而POI的对象数有限,本文仿真4个不同数据量的Tweet测试集,分别是Tweet160K,Tweet320K,Tweet640K和Tweet1280K.
采用随机分配对象的位置的方式模拟真实Tweet中包含的位置信息.
表2给出数据集的特性.
表2数据集特性数据集对象数平均包含的关键词数总共包含关键词数总共包含词语数POI160K1600002.
7039401436901Tweet160K16000010.
04947351685357Tweet320K32000010.
291509333459213Tweet640K64000010.
242494206886321Tweet1280K128000010.
30414366138427915.
2测试结果及分析本节对比IR-Tree,S2I和CSTI的性能,评估索引的空间开销、查询的响应时间和磁盘I/O.
为了使结果可靠,每个实验都重复10次,每次响应100个查询.
分别评估了结果数(k)、查询关键词数、调节因子、数据量、buffersize、不同数据集对查询性能的影响.
表3给出实验用的参数设置,缺省值加粗显示.
表3实验的参数设置参数值查询结果数(k)10,20,40,80,160关键词个数1,2,3,4,5调节因子0.
1,0.
3,0.
5,0.
7,0.
9数据量(Tweet)160K,320K,640K,1280K数据集POI,Tweet空间开销.
表4给出基于Tweet数据集IR-Tree、S2I和CSTI的空间消耗.
从表中可以看出,IR-Tree的空间开销是S2I的40倍,CSTI的200倍.
相比IR-Tree,S2I的总体空间开销减少很多,但仍然是CSTI的5倍,尤其是对频繁词构建的树索引,CSTI的空间开销比S2I降低1个数量级.
表4索引的空间开销数据量(K)索引总大小(MB)树索引大小文件(块)索引大小元数据大小160CSTI265.
314.
36.
4S2I104.
686.
715.
32.
6IR-Tree5139.
231507632.
2320CSTI53.
7182411.
7S2I259.
3229264.
3IR-Tree11449.
46211202185.
4640CSTI98.
2373922.
2S2I534.
3486417.
3IR-Tree21938123213814341280CSTI173.
4706073.
4S2I997.
29216412.
2IR-Tree44261244424121605结果数(k)的影响.
图3(a)和图3(b)分别给出索引的响应时间和磁盘I/O随结果数k值变化的情况.
CSTI的响应时间和磁盘I/O都是最少的.
CSTI和S2I的响应时间几乎胜过IR-Tree索引1个数量级,主要是因为这两种索引采用文本优先的方式,区别对待不同频率的关键词,从而减少了大量磁盘I/O.
CSTI胜过S2I的主要原因是PCTree没有重叠,PCTree的树高和节点数较少,空间剪枝能力较强.
周新等:一种支持Top-k空间关键词检索的高效压缩索引165Fig.
3RespondtimeandI/Ovaryingthenumberofresults图3响应时间和I/O随查询结果数变化情况关键词数的影响.
关键词个数对索引性能的影响由图4绘出.
CSTI和S2I的单关键词检索算法非常高效,随着查询关键词的增多,多关键词检索算法要合并多个单关键词检索的结果,因此响应时间和磁盘I/O均有所增多.
而IR-Tree的性能相反,随着关键词的增多,R-Tree节点关联的倒排索引的文本过滤能力增强,能够更快地终止检索.
总的来说,CSTI和S2I的性能依然胜过IR-Tree很多倍.
而CSTI空间剪枝能力强,占用空间小,缓存命中率高,响应时间和磁盘I/O优于S2I.
Fig.
4RespondtimeandI/Ovaryingthenumberofquerykeywords图4响应时间和I/O随查询关键词数变化情况数据量的影响.
图5展示出不同数据量的Tweet记录对索引的性能影响.
随着数据量的增大,3种索引的响应时间和磁盘I/O均有所增加.
CSTI和S2I呈线性增长,而IR-Tree有指数增长的趋势.
对比3种索引的性能,CSTI依然超过S2I,二者都超过IR-Tree几乎1个数量级.
Fig.
5RespondtimeandI/OvaryingthecardinalityoftheTweetdataset图5响应时间和I/O随数据量(Tweet)变化情况调节因子的影响.
3种索引对调节因子都很敏感,其对索引的响应时间和磁盘I/O的影响如图6(a)和图6(b)所示.
CSTI和S2I的性能随着空间重要性的提升而有所改善.
因为增大了调节因子,CSTI和S2I的空间剪枝能力166JournalofSoftware软件学报Vol.
25,Supplement(2),December2014增强,提前终止了检索.
IR-Tree却有与之相反的表现,说明文本的过滤能力比空间的剪枝能力要强,返回k个结果的收敛速度变慢.
Fig.
6RespondtimeandI/Ovaryingthequerypreferencerate图6响应时间和I/O随调节因子变化情况Buffersize的影响.
图7给出3种索引的响应时间和磁盘I/O随buffersize的变化(从0~64MB)情况.
随着buffersize的增加,CSTI和S2I的性能均有所改善,从变化幅度可知,CSTI随buffersize的增加改善更多,这也验证了文献[10]的实验结果:随着buffersize的增加,空间开销越低的索引性能改善的越多.
IR-Tree尽管磁盘I/O有所减少(从0~1MB时显著减少),而总的响应时间没有缩短,主要原因是倒排文件占用空间太多,访问倒排文件消耗时间太久.
数据集的影响.
图8给出POI和Tweet两个不同数据集对索引性能的影响.
两种数据集中,CSTI均优于S2I和IR-Tree.
当数据集中关键词数增多时,这种优势更加明显.
Fig.
7RespondtimeandI/Ovaryingthebuffersize图7响应时间和I/O随buffersize变化情况Fig.
8RespondtimeandI/Ovaryingthedifferentdataset图8响应时间和I/O随不同数据集变化情况周新等:一种支持Top-k空间关键词检索的高效压缩索引1676总结与展望本文提出一种基于压缩的索引——CSTI和高效的检索算法以支持top-k空间关键词查询.
与已有方法相比,CSTI具有以下改进:(1)PCTree索引高频词的倒排列表.
低频词关联对象少,直接存储节省了解压的代价,有利于快速响应查询.
高频词关联对象较多,采用PCTree索引,增强了空间剪枝能力,极大地降低了存储开销,提高了缓存命中率,改善了查询性能.
(2)时空开销小.
CSTI的合理设计支持实时响应查询.
基于真实和仿真数据集的评估结果表明,CSTI的空间开销节省10倍,时间开销也优于已有方法.
(3)维护代价小.
CSTI中PCTree避免了aR-tree中的节点重叠,其前缀特性使其具有和Quad-tree相当的维护代价.
空间索引采用查找表的方式将其独立出来,空间索引的更新维护代价大为降低.
尽管本文提出的方案是可行且高效的,然而空间关键词检索还有一些问题待解决.
(a)寻找近似解.
已有的方法为了找到top-k的精确解,采用best-first的搜索策略,而这种策略的无效扫描很多,代价昂贵,需要探索depth-first的搜索策略以寻找近似解,并给出与精确解的误差.
(b)索引查询.
目前的索引方法仍以索引数据为主,由于空间关键词检索和查询的关联密切,很难使得最相关的结果总排在倒排列表的最前面以提前终止检索,下一步将探索索引查询,通过探索查询日志,依据每次查询的结果重组倒排列表,提高检索性能.
References:[1]ChenYY,SuelT,MarkowetzA.
EfcientqueryprocessingingeographicWebsearchengines.
In:ChaudhuriS,HristidisV,PolyzotisN,eds.
Proc.
oftheACMSIGMODInt'lConf.
onManagementofData.
Chicago:ACM,2006.
277288.
[2]HariharanR,HoreB,LiC,MehrotraS.
Processingspatial-keywordqueriesingeographicinformationretrievalsystems.
In:Proc.
ofthe19thInt'lConf.
onScientificandStatisticalDatabaseManagement(SSDBM2007).
Banff:IEEEComputerSociety,2007.
16.
[3]ZhouY,XieX,WangC,GongY,MaWY.
Hybridindexstructuresforlocation-basedWebsearch.
In:HerzogO,SchekHJ,FuhrN,ChowdhuryA,TeikenW,eds.
Proc.
ofthe2005ACMCIKMInt'lConf.
onInformationandKnowledgeManagement.
Bremen:ACM,2005.
155162.
[4]KhodaeiA,ShahabiA,LiC.
HybridindexingandseamlessrankingofspatialandtextualfeaturesofWebdocuments.
In:BringasPG,HameurlainA,QuirchmayrG,eds.
Proc.
ofthe21stInt'lConf.
onDatabaseandExpertSystemsApplications.
Bilbao:Springer-Verlag,2010.
450466.
[5]LiZ,LeeKCK,ZhengB,LeeWC,LeeDL,WangX.
Ir-Tree:Anefcientindexforgeographicdocumentsearch.
IEEETrans.
onKnowledgeandDataEngineering,2011,23(4):585599.
[6]FelipeID,HristidisV,RisheN.
Keywordsearchonspatialdatabases.
In:AlonsoGA,BlakeleyJLP,ChenA,eds.
Proc.
ofthe24thInt'lConf.
onDataEngineering(ICDE2008).
Cancún:IEEE,2008.
656665.
[7]CongG,JensenCS,WuD.
Efcientretrievalofthetop-kmostrelevantspatialWebobjects.
PVLDB,2009,2(1):337348.
[8]Rocha-JuniorJB,GkorgkasO,JonassenS,NrvgK.
Efcientprocessingoftop-kspatialkeywordqueries.
In:PfoserD,TaoYF,MouratidisK,NascimentoMA,MokbelMF,ShekharSS,HuangY,eds.
Proc.
ofthe12thInt'lSymp.
onAdvancesinSpatialandTemporalDatabases(SSTD2011).
Minneapolis:Springer-Verlag,2011.
205222.
[9]PapadiasD,KalnisP,ZhangJ,TaoY.
EfficientOLAPoperationsinspatialdatawarehouses.
In:JensenCS,SchneiderM,SeegerB,TsotrasVJ,eds.
Proc.
ofthe7thInt'lSymp.
onAdvancesinSpatialandTemporalDatabases(SSTD2001).
RedondoBeach:Springer-Verlag,2001.
443459.
[10]ChenL,CongG,JensenCS,WuD.
Spatialkeywordqueryprocessing:Anexperimentalevaluation.
PVLDB,2013,6(3):217228.
[11]LuJH,LuY,CongG.
Reversespatialandtextualknearestneighborsearch.
In:SellisTK,MillerRJ,KementsietsidisA,VelegrakisY,eds.
Proc.
oftheACMSIGMODInt'lConf.
onManagementofData(SIGMOD2011).
Athens:ACM,2011.
349360.
168JournalofSoftware软件学报Vol.
25,Supplement(2),December2014[12]LiGL,FengJH,XuJ.
Desks:Direction-Awarespatialkeywordsearch.
In:KementsietsidisA,SallesMAV,eds.
Proc.
oftheIEEE28thInt'lConf.
onDataEngineering(ICDE2012).
Washington:IEEEComputerSociety,2012.
474485.
[13]HuJ,FanJ,LiGL,ChenSS.
Top-kfuzzyspatialkeywordsearch.
ChineseJournalofComputers,2012,35(11):22372246(inChinesewithEnglishabstract).
[14]LuoSQ,LuoYF,ZhouSG,CongG,GuanJH:Distributedspatialkeywordqueryingonroadnetworks.
In:Amer-YahiaS,ChristophidesV,KementsietsidisA,GarofalakisMN,IdreosS,LeroyV,eds.
Proc.
ofthe17thInt'lConf.
onExtendingDatabaseTechnology(EDBT).
Athens:OpenProceedings,2014.
235246.
[15]ZhangCY,ZhangY,ZhangWJ,LinXM,CheemaMA,WangXY.
Diversifiedspatialkeywordsearchonroadnetworks.
In:Amer-YahiaS,ChristophidesV,KementsietsidisA,GarofalakisMN,IdreosS,LeroyV,eds.
Proc.
ofthe17thInt'lConf.
onExtendingDatabaseTechnology(EDBT).
Athens:OpenProceedings,2014.
367378.
[16]YanH,DingS,SuelT.
Invertedindexcompressionandqueryprocessingwithoptimizeddocumentordering.
In:QuemadaJ,LeónG,MaarekYS,NejdlW,eds.
Proc.
ofthe18thInt'lConf.
onWorldWideWeb(WWW2009).
Madrid:ACM,2009.
401410.
[17]ZhouX,ZhangX,WangYH,LiR,WangS.
Efficientdistributedmulti-dimensionalindexforbigdatamanagement.
In:WangJY,XiongH,IshikawaY,XuJL,ZhouJF,eds.
Proc.
ofthe14thInt'lConf.
onWeb-AgeInformationManagement(WAIM2013).
Beidaihe:Springer-Verlag,2013.
130141.
附中文参考文献:[13]胡骏,范举,李国良,陈姗姗.
空间数据上关键词模糊查询算法.
计算机学报,2012,35(11):22372246.
周新(1987-),女,安徽宿州人,博士生,CCF学生会员,主要研究领域为时空数据管理.
E-mail:zhouxin314159@163.
com薛忠斌(1985-),男,博士生,主要研究领域为内存数据库,移动数据管理.
E-mail:zbxue@ruc.
edu.
cn张孝(1972-),男,博士,副教授,CCF高级会员,主要研究领域为高性能数据库,非结构化数据管理,数据的智能获取与应用.
E-mail:zhangxiao@ruc.
edu.
cn王珊(1944-),女,教授,博士生导师,CCF会士,主要研究领域为高性能数据库,内存数据库,非结构化数据库,数据仓库与数据分析.
E-mail:swang@ruc.
edu.
cn安润功(1992-),男,硕士生,主要研究领域为信息检索.
E-mail:anrungong@ruc.
edu.
cn