查询静态空间

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
18,No.
2,February2007,pp.
268278http://www.
jos.
org.
cnDOI:10.
1360/jos180268Tel/Fax:+86-10-625625632007byJournalofSoftware.
Allrightsreserved.
可伸缩的增量连续k近邻查询处理廖巍+,熊伟,王钧,景宁,钟志农(国防科学技术大学电子科学与工程学院,湖南长沙410073)ScalableProcessingofIncrementalContinuousk-NearestNeighborQueriesLIAOWei+,XIONGWei,WANGJun,JINGNing,ZHONGZhi-Nong(CollegeofElectronicScienceandEngineering,NationalUniversityofDefenseTechnology,Changsha410073,China)+Correspondingauthor:Phn:+86-731-4573480,Fax:+86-731-4575798,E-mail:liaowei_2000@163.
com,http://ww.
nudt.
edu.
cnLiaoW,XiongW,WangJ,JingN,ZhongZN.
Scalableprocessingofincrementalcontinuousk-nearestneighborqueries.
JournalofSoftware,2007,18(2):268278.
http://www.
jos.
org.
cn/1000-9825/18/268.
htmAbstract:ToevaluatethelargecollectionofconcurrentCKNN(continuousk-nearestneighbor)queriescontinuously,ascalableprocessingoftheincrementalcontinuousk-nearestneighbor(SI-CNN)frameworkisproposedbyintroducingsearchingregiontofilterthevisitingTPR-tree(time-parameterizedR-tree)nodes.
SI-CNNframeworkexploitstheincrementalresultstabletobufferthecandidateobjects,flushestheobjectsintoqueryresultsinbulk,efficientlyprocessesthelargenumberofCKNNqueriesconcurrently,andhasaperfectscalability.
AnincrementalSI-CNNqueryupdatealgorithmispresented,whichevaluatesincrementallybasedontheformerqueryanswersandsupportstheinsertionordeletionofbothquerycollectionandmovingobjects.
ExperimentalresultsandanalysisshowthatSI-CNNalgorithmbasedonSI-CNNframeworkcansupportalargesetofconcurrentCKNNqueriesperfectly,andhasagoodpracticalapplication.
Keywords:CKNN(continuousk-nearestneighbor)query;TPR-tree(time-parameterizedR-tree);SI-CNN(scalableprocessingofincrementalcontinuousk-nearestneighborqueries)framework;SI-CNNalgorithm;incrementalprocessing摘要:针对基于TPR树(time-parameterizedR-tree)索引的大量并发CKNN(continuousk-nearestneighbor)查询处理,提出了一种可伸缩的增量连续k近邻查询处理(scalableprocessingofincrementalcontinuousk-nearestneighborqueries,简称SI-CNN)框架,通过引入搜索区域进行预裁剪以减少查询更新所需要的TPR树节点访问代价,并引入了增量结果表以保存候选对象,批量地更新查询结果集,具有良好的可伸缩性.
基于SI-CNN框架提出了一种增量更新的SI-CNN查询处理算法,能够基于上次查询结果增量的更新查询,支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作.
实验结果与分析表明,基于SI-CNN框架的SI-CNN算法可以很好地支持大量并发的CKNN查询处理,具有良好的实用价值.
关键词:连续k近邻查询;TPR树;SI-CNN框架;SI-CNN算法;增量处理中图法分类号:TP311文献标识码:ASupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.
60472031(国家自然科学基金)Received2005-05-11;Accepted2006-04-03廖巍等:可伸缩的增量连续k近邻查询处理269连续k近邻(continuousk-nearestneighbor,简称CKNN)查询[1]是时空数据库中重要的查询类型之一,用于连续查找k个距离查询位置最近的对象.
在交通调度控制、位置服务等领域,CKNN查询得到了广泛的关注和应用.
与传统静态空间KNN(k-nearestneighbor)查询一次计算得到的查询结果不同,CKNN查询要求结果必须及时更新,以反映移动对象和/或查询本身的变化,因而查询处理算法更加复杂[1].
CKNN查询所处理的对象通常为位置动态变化的移动对象数据集,并以TPR树(time-parameterizedR-tree)[2]索引进行存储管理,而查询本身也是动态的.
针对基于TPR树索引的大量移动对象CNN查询问题,Benetis等人首先提出了Find-NN算法[3],利用最小距离函数裁剪准则对TPR树进行深度优先搜索遍历,以获得最近邻对象.
Tao等人[4]对Find-NN算法进行了扩展,以支持CKNN查询.
Glenn等人提出的CW-KNN算法[5]则利用搜索区域对TPR树索引节点进行搜索预裁剪,以提高CKNN查询的更新性能.
Tao等人提出的TP-KNN算法[6]能够有效地处理时间参数化k近邻查询,但对于CKNN查询算法则必须重复提交TP-KNN查询,以获得连续查询结果集,其效率非常低下.
针对实际应用中大量并发的CKNN查询处理问题,Mokbel等人首先提出了SINA框架[7],以处理大量并发时空查询;Hu等人提出了查询驱动更新的通用连续查询处理框架[8];Yu等人提出了层次网格移动对象索引和查询索引,以改善CKNN的查询性能[9].
到目前为止,Xiong等人提出的SEA-CNN(scalableevaluationofcontinuousnearestneighbor)算法[10]以及Mortifies等人提出的CPM(conceptionalpartitionmodel)算法[11]是支持大量并发的连续k近邻查询处理的具有代表性的成果.
SEA-CNN算法通过引入搜索区域和共享查询执行的思想来处理CKNN查询的更新操作,具有良好的可伸缩性;CPM算法则使用概念空间划分(conceptualspacepartitioning)技术来提高查询更新时的空间搜索性能.
上述两种算法均采用静态空间规则划分的格网(gridcell)结构来索引移动对象集,索引更新性能较差,且不支持目前通用的TPR树索引.
本文主要研究基于TPR树索引移动对象集的大量并发CKNN查询,提出了一种高效而实用的可伸缩的增量连续k近邻查询处理框架和相关算法.
本文的主要贡献如下:1)提出了一种可伸缩的增量连续k近邻查询处理(scalableprocessingofincrementalcontinuousk-nearestneighborqueries,简称SI-CNN)框架,通过引入搜索区域对TPR树索引节点进行预裁剪以减少查询更新所需要的磁盘访问代价,并引入了基于内存的增量结果表对查询结果进行批量更新.

2)基于SI-CNN框架提出了一种支持更新的SI-CNN查询处理算法.
该算法能够基于上次查询结果进行增量更新查询,支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作.

3)在仿真实验环境下,对本文提出的SI-CNN算法进行了大量的实验测试.
实验结果与分析表明,基于SI-CNN框架的SI-CNN算法具有良好的查询和更新性能.
本文第1节介绍连续k近邻查询的相关基本概念.
第2节介绍基于TPR树索引的SI-CNN查询处理框架以及SI-CNN查询处理算法.
第3节给出实验结果比较与分析.
最后是结论与展望.
1连续k近邻查询的基本概念本节给出了文献[4]与文献[10]中引出的相关概念.
本文后续部分将直接使用这些基本定义.

定义1(连续k近邻查询)[10].
连续k近邻查询定义如下:q=(At+B,k,T),其中:At+B表示查询位置q.
Loct的线性运动轨迹;k表示查询q的最近邻对象个数;T表示查询的时间窗口范围.
定义2(查询提交时刻)[10].
客户端向服务端提交CKNN查询的时刻tisu.
定义3(查询更新时刻)[10].
服务端周期性地或当缓冲区中移动对象数目超出阈值时查询进行更新的时刻tupt.
定义4(查询参考时刻)[10].
CKNN查询提交时刻tisu或查询更新时刻tupt,表示为tref.
CKNN查询在查询更新时刻tupt进行更新,由于在客户端提交新的CKNN查询时刻tisu,服务端并不立即计算当前查询的初始结果集,而是加入到查询集合中,并在查询更新时刻tupt与其他需要更新的查询一起进行处理.
因此,通常将查询参考时刻定义为查询更新时刻,即tref=tupt,出于简单考虑,我们令tref=0.
270JournalofSoftware软件学报Vol.
18,No.
2,February2007定义5(距离函数)[4].
在d维欧式空间中,给定在参考时刻tref以线性速度矢量运动的查询q与移动点对象p,则在未来任意时刻t,查询位置q.
Loct与对象p之间的距离定义为查询q与移动对象p之间的距离函数,dist(q,p,t)=At2+Bt+C,其中A,B,C均为常量.
距离函数dist(q,p,t)为关于时间t的二次凹函数,A,B,C与在参考时刻tref=0时查询q的位置和速度矢量、移动对象p的位置和速度矢量有关.
定义6(最近邻距离)[4].
在d维欧式空间中,给定CKNN查询q,在任意时刻t查询位置q.
Loct到k最近邻对象p的距离定义为查询q的最近邻距离.
mindist(t)={dist(t),T},dist(t)=At2+Bt+C.
最近邻距离mindist(t)为元组dist(t),T的集合,dist(t)表示在T时间间隔内查询q到k最近邻对象p之间的距离函数.
最近邻距离mindist(t)给出了CKNN查询q在查询窗口范围q.
T=[tref,tref+TL]内近邻搜索的上界,只有当更新、插入或删除的移动对象p在某个时间间隔[ts,te][tref,tref+TL]内与查询位置q的距离函数dist(q,p,t)小于mindist(t)时,移动对象p才会对CKNN查询q的结果产生影响.
2可伸缩的增量连续k近邻(SI-CNN)查询处理算法2.
1SI-CNN查询处理思想给定以线性速度矢量运动的CKNN查询q,利用扩展Find-NN算法[4]对TPR树索引进行搜索,可以得到查询初始结果集.
在查询q的时间窗口范围内,若存储移动对象的数据库发生变化,包括移动对象运动的更新(如速度大小和/或运动方向的改变)、移动对象的插入或删除操作等,则可能会对查询q的初始结果集产生影响,因此,必须对CKNN查询结果进行更新,以保证查询的正确性.
在理想情况下,一旦数据库发生变化,则应立即更新CKNN查询结果.
但是,当查询的数据库移动对象规模非常大时,这种方式是不切实际且不必要的.
与文献[10]中采用的方法类似,为了避免数据库频繁更新所带来的TPR树索引和CKNN查询结果的频繁更新操作,SI-CNN查询处理将客户端提交的更新、插入和删除的移动对象缓存在缓冲区中,并按照一定的时间间隔周期性地或当缓冲区中移动对象数目超过阈值时,将缓冲区中的移动对象更新到物理磁盘(数据页面和TPR树索引页面)中,并更新所有的CKNN查询.
根据实际应用,通过设置更新时间间隔和缓冲区大小,可以获得用户所需要的准确度和查询更新效率.

定义7(搜索半径).
给定CKNN查询q的时间窗口q.
T=[tref,tref+TL]及此窗口内的最近邻距离mindist(t)={dist(t),T},存在一个线段方程集合L={l(t)=At+B},其中,l(t)为其上确界,即满足t∈[tref,tref+TL],l(t)≥dist(t).
特别地,我们定义查询q的搜索半径q.
SS如下:q.
SS=lmin(t)=At+B∈L,且l′(t)=A′t+B′∈L,.
d)(d)(∫∫++′+′mindist(q,t),即对象p不可能成为查询q的k近邻对象,因此不会对查询q产生影响.
定义9(查询相似度,QS).
给定两个CKNN查询q=(At+B,k,T),q′=(A′t+B′,k′,T′),这两个查询的相似度QS(q,q′)定义为廖巍等:可伸缩的增量连续k近邻查询处理271.
otherwise,0],[,d),,(),(1≠=′∩′=′∫essettttTTttttqqdistqqQSes定义10(相似查询,SQ).
给定CKNN查询q=(At+B,k,T)和查询集合Q,则查询集合Q中与CKNN查询q相似的查询SQ(q,Q)定义为QS(q,Q)=q′=(A′t+B′,k′,T′),其中,q″=(A″t+B″,k″,T″)∈Q,QS(q,q′)≥QS(q,q″).
相似查询的定义给出了查询集合Q中与查询q具有最相似语义的查询.
根据此定义,我们引入了SI-CNN动态扩充查询处理算法,其思想是:当客户端提交新的查询q时,服务端从查询集合Q中找到其相似查询SQ(q,Q),从而可以获得查询SQ(q,Q)的结果集,然后将结果集中的移动对象作为候选对象进行判断后放入到查询q的初始结果集中,根据候选对象计算出查询q的最近邻距离mindist(t)和搜索区域q.
SR,最后将查询q加入到查询集合Q中,并在查询更新时刻tupt通过搜索TPR树索引得到查询q的初始结果.
根据定理1可知,对每个CKNN查询q,若更新、插入或删除的移动对象在其查询窗口q.
T=[tref,tref+TL]范围内落在搜索区域q.
SR之外,则查询q的结果不需要更新.
由此我们引入了SI-CNN处理查询更新的算法,其思想如下:对于CKNN查询q,当数据库发生变化时,若移动对象p位置落在查询q的搜索区域q.
SR之外,则p不会对查询q结果造成影响,忽略此对象;否则,作进一步的精化处理,判断对象p是否对查询q结果产生影响.
另外,若落在查询q搜索区域之内的移动对象均为插入的新对象,则查询q结果更新不需要重新搜索TPR树索引,而仅仅利用查询q的最近邻距离mindist(t)进行精化判断即可得到查询q更新后的结果.
若有删除或更新的对象落在查询q的搜索区域q.
SR内,则利用最近邻距离mindist(t)对这些对象进行精化判断,若对查询q结果产生影响,那么在更新查询q以后,必须重新计算搜索区域q.
SR.
最后,必须对TPR树索引利用搜索区域q.
SR进行剪枝搜索,以得到正确的结果.
2.
2SI-CNN查询处理框架传统CKNN查询处理机制对每个查询更新独立地执行一次TPR树索引扫描,对于大量需要同时更新的CKNN查询来说,这种重复的磁盘扫描方式效率十分低下.
SI-CNN查询处理框架采用共享查询计划(sharequeryplan)的机制来支持大量并发的CKNN查询更新.
在查询更新时刻tupt,SI-CNN算法首先在基于内存的查询表(圆形的查询搜索区域)和对象缓冲区(点对象)之间做连接扫描以更新查询,然后在查询表与TPR树索引(点对象)之间做一次连接运算,只需要一遍TPR树索引扫描,便可获得所有的对查询可能造成影响的候选移动对象集,将这些候选对象进行分组,并发送给不同的查询进行精化判断,得到最终的查询更新结果.

图1所示为SI-CNN系统框架,具体包括以下几个部分:1)查询表(querytable),基于内存的序列表结构,用以存放用户提交的CKNN查询.
其记录形式为五元组QID,QLoc,k,T,SS.
其中,QID表示CKNN查询q的标识;QLoc表示参考时刻tref查询位置q.
Loc;k表示CKNN查询最邻近对象个数;T表示查询q的时间窗口范围;SS表示查询q的搜索半径.
在查询更新时刻tupt必须更新查询表中的所有记录,将QLoc更新为tupt时的查询位置,T起始时刻更新为tupt,若此记录对应查询q的结果被更新,则需要重新计算搜索半径SS.
2)查询结果表(queryresults),基于磁盘的顺序表结构,存放所有CKNN查询的结果.
其记录形式为二元组QID,Result.
其中,QID表示CKNN查询q的标识;Result表示查询q的结果集{R,T,D},对于Result的每个元组R,T,D,R,T,D分别表示查询q的k个最近邻对象、R的有效时间范围、T时间间隔内查询q的最近邻距离mindist(t).
3)对象缓冲区(objectbuffer),基于内存的线性队列,用于缓存更新、插入或删除的移动对象.
在更新时刻tupt,所有对象被写入到磁盘中(更新数据页面和TPR树索引),并清空对象缓冲区.
4)TPR树索引(TPR-tree),基于磁盘的移动对象索引结构,CKNN查询通过扫描TPR树索引来查找最近邻272JournalofSoftware软件学报Vol.
18,No.
2,February2007的k个移动对象.
5)增量结果表(incrementalresults),基于内存的线性链表结构,存放SI-CNN查询算法在进行查询更新时的候选移动对象(查询表分别与对象缓冲区、TPR树索引连接操作时产生的中间结果).
其元组形式为QID,p.
其中,QID表示记录对应的查询标识;p表示移动对象(包括参考时刻位置、速度矢量等信息).
增量结果表以查询标识QID进行排序,当链表中记录数目达到阈值时,将增量结果表中的记录更新到查询结果表中,同时清除缓存.
QuerytableIncrementalresultsQueryresultsObjectsbufferInmemoryJoinMemorydiskJoinQueryupdateStreamofmovingobjectsandmovingqueriesMemoryfullortimeoutInsertnewqueryresultsQueuefullResultsupdateResultsupdateTPR*-treeMemoryfullortimeoutDoneInsertnewquery.
.
.
SendincrementalresultstothequeriesMovingobjectsFig.
1SI-CNNsystemframework图1SI-CNN系统框架SI-CNN框架将CKNN查询组织在查询表中,表中记录存放了对应查询的相关信息和搜索区域.
由于每条查询记录所占用的空间非常小,所以整个查询表可以完全存放在内存中,同时便于SI-CNN算法在查询更新时进行查询搜索区域与移动点对象之间的连接操作和查询搜索区域的修改操作.
当新的查询提交时,SI-CNN算法生成新的查询记录并计算出其搜索区域,将此查询记录插入到查询表中.
若查询表中记录的查询窗口结束时刻小于当前查询更新时刻tupt,则从表中删除这一过时的查询记录.
CKNN查询结果集由于占用较大的空间而存放在基于磁盘的查询结果表中.
移动对象存放在物理磁盘上,并利用TPR树进行索引,在每个更新时刻tupt,必须对TPR树索引和数据页面进行更新.
客户端提交的插入、删除或更新移动对象缓冲在对象缓冲区中,并在每个更新时刻tupt与查询表进行连接判断后写入到磁盘索引及数据页面中.
为了能够快速地执行TPR树索引与查询表之间的连接运算,且减少查询结果更新时额外的磁盘I/O操作,我们引入了基于内存的增量结果表来保存SI-CNN算法产生的中间结果,并在增量结果表记录超过阈值时,将查询结果更新批量地写入到查询结果表中.