论文研究-ATPR-Tree:带有属性维的时空索引.pdf

所需积分/C币:5 2019-09-10 09:02:33 2.16MB .PDF

城市计算领域里所处理的移动对象往往带有除时间、空间信息外更多的信息,而目前的移动对象索引大多只有时间、空间这两个维度,不能有效地对附带更多信息的移动对象进行管理。基于这一问题,提出了一种带有属性维度的时空索引ATPR-tree,这种索引由TPR-tree改进而来。在TPR-tree节点CBR的基础之上新加入了属性值区间(RI)的概念;根据加入的RI属性维改变了TPR-tree的节点结构和代价目标函数;根据新的代价目标函数对插入、删除以及查询算法做出相应的改变。实验中所处理的移动对象是使用GSTD随机生成的,实验把附加属性作为索引一个维度的ATPR-tree和不作为索引的一个维度的TPR-tre
王永会,张恩瑞: ATPR-Tree:带有属性维的时空索引 2017,53(7)81 uree的代价目标函数改为了公式(1)所述的函数。 度值为3,而在2时刻进入了区域C,并且在此区域O V F(tdt (1)探测到的温度值为5,t3时刻离开区域C。有了属性值 F()指代代价函数所要优化的四个参数,它分别是的移动对象,在移动过程中不仅会不断更新速度的值与 方向,同时也会不断更新属性值的大小 MRR面积、MBR面积重叠、MBR形心战离以及MBR周 区域A 长的代价计算函数。如文献[4中所述,因为对平面积 区城C 分会得到一个三维的空间体,所以增加∫时间维度之后 区域B 对平面MBR的四个优化参数最小化的讨论变成了对立 休三维空间的MBR随时问延伸出的空间体的四种优化 参数最小化的讨论。节点的MRR形成的空间体越小则 ating 产生空白区域的可能性就越小,对应的奁询性能就越好 22其他版本的TPR-tree TPR-tre有很多的变种,其屮最具代表性的就是 图2带有温度值的移动对象在不同区域间的移动 TPR*-tre索引,TPR*-tre引入了扫描区域( sweeping 本文提出的 AtPR-tree是一种将属性值维度融合进 region)的概念。在TPR*re的基础上提出了ACA传统索引结构中的种新型索引,主要改变了TPR -tree 算法,使得 TPR-tree拥有了可以主动地调整节点CBR的节点结构、代价函数,以及相对应的索引维护时所有 的功能。除 TPR-tree之外,还有很多其他的TPR-e使用的算法 索引的变种41。 以往大多数TPR-tree变种多是针对代价函数的 这些由TPR-tre改造来的时空索引都可以提高优化或是更新方式的进,也有研究将TPRc附加属 TPR-tree的合洵询效率,优化IPke结构。但是很少有性值进行使用,但是这些研究都没有将属性值维度真正 种时空索引能考虑到城市计算的雷求,如前所述现在的融入到索引的内部结构中去,而是简单的附加于索引 的应用环境中移动对象往往携带更多的信息。因此本结构之上,不可随着IPR-te的插入或是删除操作而做 文基于 TPR-tree.的结构提出了一种带有属性维度的新出最佳的调整。这样的方法无异于是先检索出时空位 型时空索引:ATPR-tree时空索引。 置再根据属性值条件进行筛选,如此会加大检索出符合 某·条件的移动对象的代价。而 atPR-tree索引可以有 3问题定义 效地结合属性值维度,在索引更新变化时,属性值维度 3.1移动对象 也可以随之做出最好的调整进而在检索移动对象时可 移动对象是时空数据库所管理的基本元素,它具有以减少查询代价,提高上层应用运行效率 动态性,其位置会随着时间变化而变化,因而时空索引3.2属性值区间(RI) 也需要对移动的对象做出动态的改变。TPR-tree则可 处理的移动对象附加∫属性值,为了管理移动对象 以对移动对象当前以及未来一段时间内即将到达的位的这些属性值需要对传统的CBR进行扩展,进而在原 置进行预测性的查询。移动对象的运动可以用移动对来TPR- tree BJ CBR的基础上增加属性值区间( Rating 象在时的位置m(t)=(x,x),和对应的速度矢量 Interval,RI),所谓RI就是一个节点中所有分支所带有 -(,2)米计算,在[tns,l+hoom]区间内任何时间的属性值的取值范围。对于叶了节点而言,节点的某一 点的位置可以通过线性方程x(t)=x(t)+v(t-ta)计算条分支的R直接等于这条分支所指向的移动对象在其 得出,其中 horizon为 TPR-tree索引所使用到的一个参所处区域的属性值;而对于非叶子节点,它的每一个分 数,它确定L的取值范围。 支都有一个RI。如同MBR(VBR)样,分支的RI会紧 为了检索和使用的方便,希望移动对象能携带除密的包含这条分支的所有孩子节点的RⅠ,当前节点RI 位置和时间外更多的信息,比如当前对象所处区域的的下界和上界分别是当前节点所包含的每一个分支的 温度或移动对象一些自身信息的属性值,因此本义改RI下的最小值和上界的最大值 变了 TPR-tree中所处理的时空对象的数据结构,从原先 如图3(a)所示是一个三层的树形结构,它表示 的obec(id,<x,y>,V)变为了 objec(id,<x,y>,V, ATPR-tree在tm0时刻各个节点的RI的值以及每一层 ratine),其中 rating是此对象 object在其所处的区域内节点分支的RI相互包含的情况,例如,节点N3包含移 所具有的一个属性值。如图2所示,展示了一个带有温动对象a、b、c它们在某一区域内的属性值分别为7,3, 度属性的二维空间移动对象O在不同空间区域内移动4,最小值为3最大值为7所以N3的RI为<3,7>,而N1 时其属性值的变化情况,O在t时刻进入区域A,在该包含N<3,7和N<3,11>,所以N1的RI下界为其所 域内O的温度值为6,在t时刻进入区域B,此时的温有分支RI下界的最小值即为3,而上界为所有分支RI的 2017,53(7) Computer Engineering and Applications计算机工程与应用 最大值即为11l。 11>。假设此时给出一个杳询中含有一个属性值范围的 在索引更新的过程中每一个节点的RI会随着节点限定,即要查找属性值的大小等于[3,4]中的所有对象, 的插入、删除以及分裂而发生相应的变化。插入时如果则图屮c的结构满足这限定的节点有N3与N,需要 插入对象的属性值大于当前节点RI的上界或者小于下进行两次访问。而图中a的结构满足这一限定的节点 界,则需要对RI进行扩充,从而保证每一个节点的R都有N3、N4以及N需要进行三次访问。由此可见离散 能有效地对其所包含的分支或对象进行包含。如图3性的大小对查询的效率有直接的影响。 (b)所示,在tmel时插入了个新的移动对象N到节3.3代价目标函数 点N4中其属性值为13,并且节点N也在此时刻分裂 密度参数:为了后边讨论的方便,这里使用密度参 成了N与NN,因而节点RI情况也发生变化。新的数将R的离散性抽象成一个具体的值来考虑 移动对象N的属性值为13,大于11,所以N4的R的上 o=(RI-RI+eplison)xe 界就扩充为13,N包含N与N4,更后的N的上界公式(2)表示密度参数p的求值方法,RH是当前节点 依然大于N的R的上界所以N的R的上界也更新为R1的上界,R指当前节点R的下界,中on是一个 13N分裂后变为两个节点N与NN5,|也从原来不等零的最小的浮点数,这个浮点数的作用是避免密度 的<1,9>,变为分裂后的<1,5>与<8,9> 参数取值为零,如果在某一节点RI上下界的差值为零, 则在计算代价目标函数值M的时候,节点的M值也将 <3,13>|<1,17> 为零,进而造成对象随机的插入,使总的M的值无法再 保持最优,ε是一个止比例参数,用来调节密度参数,使 ,7><3,1|>|<1,9><6,17 其值稳定在一个区城,而不至于过大或过小。由公式可 见密度参数ρ越小,则表示节点R的离散性越小,反之 a b c de f h 越大则节点RI的离散性就越大。 (a)time时刻各节点的RI ATPR-tree在CBR的基础上加入了RI,作为一个索 引结构中新的维度,它自然会影响索引的插入与删除算 <3,13><1,17> 法所使用到的代价目标函数,R*tree有自己的代价目标 Ns NNsI N6 函数,而IPR-tre在R*-tree的基础上加入了时间维度, ,7><3,13x 代价函数的计算变为了对R*-tree的代价函数积分值的 回画。 计算,TPR-tree索引利川公式(1)分别的去计算节点 MBR边界矩形的面积、边长、重叠区城面积的积分。在 d e n t g h (b)time时刻各节点的R1 插入和删除时TPR-tree会保证公式(1)所给出的代价目 标函数得到的值尽量最小。而增加了属性值维度的 3,13><1,17 ATPR-tree采用公式(3)作为新的代价目标函数。 N M=0 F( (3) 7,11 1,9><6,17 其中P为当前节点的密度参数,后半部分就是公式(1), 即为TPR-uree的代价函数。简单的说,如果说R*-tree e b c d a f g h j 在插入删除时要尽量保证节点MBR的面积以及重叠面 (c)压缩后各节点的RI 积最小,那TPR-tre就是要保证节点的MBR随着时间 图3节点R的树形结构图 延伸后得到的空间体,即利川公式(2)计算得到的体积 RI的离散性RI的离散性指的是同样数目的点得到最小以及不同节点的空间体的重叠最小;而AIPR-tree 的R的上下界差值的大小。差值越大说明R内听包含在插入和删除时还需考虑到RI,需要保证RI有最小的 对象的属性值的波动越大,而此差值越小则说明RI内离散性,以保证查询时的效率。所以在公式(1)的基础 包含对象的属性值都比较相近。离散性也可以看成同上加入了密度参数,也就是在CBR形成的空间体中加 样一段长度的R所能包含分攴数目的能力,也就是说,入密度参数,所以公式(3)就可以看成节点MBR随着时 同样长度的段RI如果能包含的分支数越多则其离散间延仲后形成的空间体质量;而进行插入删除算法时 性就越低,能包含的分支数越少,就说明其离散性越高。各个分支的插入或是删除要保证公式(3)得到的值最 图3(c)是对R进行压缩后的结果,分支a与分支e小,即可以视为要保证这个节点的空间体的质量M 互换了位置,N3与N1的风分别变为<3,4>与<7,最小。 王永会,张恩瑞: ATPR-Tree:带有属性维的时空索引 2017,53(7)83 34索引结构 调用 NodeSplit函数得到N和NN; ∧TPR-tree索引采用了 TPR-tree I基本结构,是一 lOi(当前分裂的节点为根节点) 个高度平衡的多叉树,节点有叶子节点和非叶子节点 11.向上生成一个包含N与NN的新根节点; (即中间节点)之分 cIsc 叶子节点结构: Leaf MBR,VBR,RI, ObiPtr>,非叶 13.调用 Insert将分裂出的节点NN插入; 子节点结构:No-Leaf<MBR,VBR,RI, Nodeptr>,Leaf结 14.仿照2~13步对插入路径上每一个节点进行调整,其 构中,MBR用来包围一个移动对象的位置,VBR用来给 中 InsertEntry改为对相应节点信息的更新。 算法结束 出此移动对象的移动方向和速度,R是移动对象在当前 其所处区城的属性值, Objptr是指向这一移动对象的指 如算法1所述,在l1时刻插入一个新的分支e,算法 针。而在No-Ieaf的结构中,MBR、VBR、RI用来紧密包 首先以索引树的根节点作为第·个操作节点,调用 Choose Subtree函数,去找到一个适合插入e的叶子节点 含其孩子节点的MBR、VBR以及RI,而 Nodeptr是指向 如果N的分支没有满则将e插入到N中,并把N 此孩子节点的指针。 索引的结构如图4(a所示,图中所示的索引一共分的 MBR VBR和R作相应的扩充,R的扩充规则已在 三层,索引屮标明了多个移动对象(a,b,c,…),Leel=0 32节说明。如果N的分支已满则先去判断N是否调 时,节点分支的结构为Ieaf,1,eml/=1和mr!=2时用过 ReInsert,若没有则调用 ReInsert进行重插,否则调 点分支的结构为 No-Leaf图4(b)为对应的10个移动用 NodeSplit将节点N分裂成N和N。如果当前分 对象在m时刻的各个节点的MBR位置的分布以及相裂的节点为根节点,则向上生成一个节点作为新的根节 互包含的情况。 点,N、NN作为孩子节点插入其中,若不是根节点则 将由节点N分裂出的新节点NN作为新的分攴插入到 Root Ni Level=2 索引树中。插入函数中的 Choose Subtree、 Reinsert以及 Nodesplit p数都会使用到公式(3)所给出的代价目标 NaNN- 函数。 上[d- (1)ChooseSubtree 不同于传统的TPR-tre,ATPR-tr的Cl (a)AIPR-tree树形结构 uree将判断增量和重叠区域扩展量的计算方法如33 Root g 所述由V转为了M,用的代价函数计算公式由公式 (1)替换为公式(3)。如算法2所示,ATPR-tre的 Choose Subtree函数会先判断当前操作节点的分支是否 为叶子节点,若是则调用 indLeastoverlap找出使所有 分支重叠区域的M值的增长最小的分支。若当前节点 不是叶子节点则找出插入e之后此节点空间体M值的 增长量最小的分支 Choosen插入插入路径P。利用这种 (b)lte时刻各节点MBR分布 新的代价函数计算方法ATPR-tree的 Choose Subtree函 图4 ATPR-tree索引结构图 数会给出一个将属性值离散性程度大小考虑在内的插 入路径。 4算法 算法2 Choose Subtree 4.1插入与删除算法 输入:待插入的移动对象e,空的插入路径P 算法1Inse 输出:可以插入e的叶子节点N,插入路径P 输入:待插入的移动对象c lif(当前层数为0)找到查找的节点 输出:完成插入操作 2. return N 1.N=root-> Choose Subtree(e,P)/P是插入路径 3f(当前层数为1)当前节点的孩子节点为叶子节点 2if(N的分支未满) 4调用 FindLeastoverlap选出分支 Choosen 3. N- InsertEntry(e) 5.els 4. else 6计算N的所有分支在包含c之后M的增量 5.if(P不为空 7.选取M增量最小的分支作为 Choosen分支 6.if(在当前层没有发生过重插) Pinsert( Choosen) 调用 Reinsert进行重插的操作 9对N的 Choosen分支调用 Choose Subtree; 算法结束 84 2017,53(7) Computer Engineering and Applications计算机工程与应用 FindLeastoverlap函数负责找出包含所要插入的对节点。所以根据这一现象结合公式(3),本文提出了 象c之后与其他节点N的孩子分支的空间体重叠区域 ATPR-tree的 ReInsert方法。如算法2所示,函数开始会 的M的增长值最小的分支作为插入e的入口。如算法建立空数组Aray用来存储N的听有分支,然后将数组 3所述,一开始会将N的所有分攴根据其包含e所需的里的所有分支分别按照MBR,VBR的每一条边的起点 M值的增量进行排序,然后只取前条分支进行比较,终点先后顺序排序,计算每一个组合方式下Aray前k k由参数给定。计算节点N选定的k条分支在包含e个元素的△M,其中△M是重插后节点MBR的M值 之后与N的其他所有孩子分支的空间体重叠部分的质的变化量,△M=M1-Mm。选择△M最大的, 量的增量的和,选择使这一增量lnc值最小的分支即这些选定的重插的分支移除后能使节点 MBR VBR 为入口继续进行操作。其中M是分支N与分支大量减少的组合作为选定的排序维度和起点终点先后 N的空间体重叠部分的M值,通过公式(2)计算出两序排序方式。并将节点甲所含有的所有分按照此种 分支的空间体的重叠部分的v值然后用乘以分支k组合进行排序,然后移除前k个分支进行重插。因为叶 的密度参数p得到重叠部分的M值。M用相同子节点分支的MBR分布较为均匀,MBR的形状随时间 方法计算,△M是M2ter与Mbre的差值 的恶化情况较轻,所以原先的 Reinsert函数适用,因此只 算法3 FindLeastOverlap 需非叶了节点重插时调用新的 Reinsert函数即可。新的 输入:待插入的移动对象c,节点N ReInsert的算法时间复杂度由算法前半部分的排序决 输出:选中的分支 Choosen 定,假设在维度等于2时,对含有n个分支的节点N进 1.计算N的所有分支在包含e之后M的增量 2将所有分支按M的增量巾小到大排序 行重插,按MBR和VBR的边各排一次,其时间复杂度 3.取前k条增量最小的分支继续进行判断 为O(4 nlogn)。 4for这k条分支中的一个分支k 算法4 Reinsert 5.forN每个分 输入:当前调用重插算法的节点N 6计算包含e后N的分支k和i重叠部分的Mter 输出:无 7计算未包含e的分支k2和N重叠部分的 M 1声明一个空数组Aay 8.计算重叠区域M值的增量△M; 2将N所有分支存入到Aray中 9.Inc+=△M//计算M增量之和l 3.for每个空间维度t 10.如果k的Dc值更小则选择分支 Choosen=K 4分别将Aray中的所分支根据其在维度i上的MBR 1I. return Choosen 和VBR进行排序; 算法结束 5计算Aray中前k分支的空间体积; (2 )NodeSplit 6计算Aray屮前k分攴的密度参数; 与 Choose Subtree相似, NodeSplit函数也用公式(3) 7计算△M 作为选择分裂轴与分裂轴上的分裂点时所用的代价函 if△M<△ Mbest 数。选择节点的分裂轴时公式(3)中的F()代表MBR 9记录当前组合选定的维度和排序方式 的边长,O是对应其中一部分的密度参数。当在已有的 10.以选定的维度和排序去排序Aray 分裂轴之上选择分裂点时,代价函数中的F()表示分裂 11.将Aray中前k条分支从N中移除并重新插入,其他 后的两个节点的MBR重叠区域。若分裂后的两个节点 的分支保留在N中 的密度参数不同,则在计算这两个节点的MBR所形成 算法结束 的空间体的相交部分的质量时,相交的那一部分密度参 ATPR-tre删除算法继自TPR-tree的删除算法 数取这两个节点的密度参数的均值。 如果一个节点的分支数量少于参数给定的个数,则将此 (3)Reinsert 节点删除并将此节点内所有分支重插,另外分支的删除 TPR-tree Hg] ReInsert数通过计算每一分支的会使节点的R发生变化,所以分攴删除后要递归向上 MBR与其所属节点MBR的质心的距离作为对节点中调整每一层上节点的R,使父节点的RI能够有效的包 所有分支排序的标准,从此节点屮删除前k条与当前节 含其各个孩子节点。 点的MBR质心离最远的分支,并将其重新捕到索42查询算法 引树中去,以此来减少影响查询的节点空白区域的面 用户提出的一个查询语句一般山三个参数构成 积。但是山文献2的pWot部分所指出的,通过计Qm、Q1、Q,这里Qn表示用来限定所要查询的空 算分支MBR质心与分支所在节点MBR质心距离的远间区域的边界框,Q表示询时间段范围,由起始时间 近来判断是否重插此条分支并不能保证节点MBR空自与终止时间组成,Q2表示所要查询的属性值的区间 区域的缩减,且可能造成移除的分支再次插回到原先的段。查询完成后,索引会返回在Q时间段内的Q区域 王永会,张恩瑞: ATPR-Tree:带有属性维的时空索引 2017,53(7)85 中屈性值大小处于Q2之间的所有移动对象的id 用现在普遍使用的GSID随机生成器牛成,在一个100× 算法5首先建立一个用来存储节点的空栈 stack并100比例的区域内对移动对象进行生成,生成的移动对 将根节点压入栈中,由根节点向下搜索到叶子节点。在象生成消亡时间,移动速度快慢比率符合高斯分布。 向下搜索的过程中,如第7、8行所述,判断是否要进入 实验中各项参数的设定如表1所示,其中Qkl为查 此条分支时,除了要判断当前分支自身的MBR和查询询语句屮属性值参数所给出的区间长度,Q代表查 语句所给出的MBR在整个Q时间范闹里是否有重合询语句里给出的查询区域的矩形面积,Q代表查询语 部分外,还需判断查询语句中给出的Q与这·分支的句中的时间参数从参照时间开始向后延伸的长度。 RI是否有重叠,若以上两个条均符合才将此分支作为 表1实验参数设置表 个搜索的入口压入栈中。最后,直到算法结束会返回 组满足查询条件的移动对象的id 参数参数值 更新次数/1010,30,50.70,90,110,130,150 算法5 Query 对象个数10 10,20,40,60,80,100,120 输入: query<Q,Q,Q 查询次数/10 10,20,40,60,80,100 输出:符合条件的移动对象的i数组 result 1,4,8,12,16,20 1. vector<id-type >result; 0.01,0.02,0.04,0.08,0.16 2. stack push(root) 1,2,4,8,16 3. while (stack!=NULL) 对于测试的结果对比,前两组实验不仅比较了两种 4. N=stack top() 结构的索引节点的访问次数,同时也观察两种索引的所 5. SLack pop (): 6forN的每一条分支i 有节点由公式(3)得来的空间体质量M的和的变化情 7.if(N2与查询 query的Q重叠 况,以此来判断公式(3)是否能较为准确地预估查询时 8.∥N2的MBR在Q时间范围内与Qm1有重合且N节点的访问量的变化趋势。而对于剩卜儿组实验,则直 的R也与Q2重合 接考量节点访问量的变化来判断不同的索引结构的查 9.i(N)为叶子节点) 询效率。 Ⅴ /imitata(N)∥访问数据 52实验测试结果和分析 11. result. insert(N. id) 如图5(a)和5(b)所示是不同的更新次数对查询性能 12. else 的影响将数据集规模等其他参数固定。图中的横轴代表 13. stack push(N,); 不同的数量级的更新次数,而图5(a)的纵轴代表节点的访 14. rcturn result 问次数,图5b)的纵轴代表索引树中所有节点的M的值。 算法结東 实验 三3 本章用实验测试在不同的参数设置下带有属性值 怒 维度的索引是否可以有效地提升查询的效果:实验把 豆200 属性值作为一个维度的 ATPR-tree索引与没有把属性值 100→TPRr 作为一个维度的TPR-tre进行查询性能的比较,比较带 TPR-tree 有属性值维度的 ATPR-tree是否可以有效地减少杳询时 1030507090110130150 的节点访问的次数,根据查询时所访问的节点数量的多 更新次数/103 少来判断效果的好坏,查询时节点访问量与其查询所用 (a)不同更新次数下节点访问次数 的运行时间是成正比的。其中用来对比的 TPR-tree和 600 原本意义上的TPR-树有所不同,它使用原来的插入、删 除算法,没有把属性值作为一个索引的维度,仅仅是简 单附加于节点之上,其他部分未做任何改变,没有采用 新的代价函数。虽然这种TPR-tee结构上少做了改动但 { 是为了称呼方便,实验中也称其为TPR-树索引 ATPR-tree 5.1实验环境与参数设定 21100 TPR-tree 实验平台配置 Intel Core5@17GHz2.40GHz处 1030507090110130150 理器,3GB内存, Linux操作系统发行版本为 Centos6.0 更新次数/10 使用C++实现算法。实验中所处理的移动对象由于条 (b)不同更新次数下节点空间矩形的质量 件限制无法对真实的移动对象的运动进行捕捉,进而采 图5不同更新次数实验结果图 2017,53(7) Computer Engineering and Applications计算机工程与应用 由这两幅图可以看出随着更新次数的增多两种索杂度。但因为会使用新的 Reinsert函数的非叶子节点的 引的空闰矩形质量M都岀现了下降,对应査询所需的数量只占节点总数量的小部分,所以对时间复杂度的 节点访问量也下降了。在更新次数较少的时候 ATPR-tree影响不会太大,算法的时间复杂度基本和TPR*-tre持平。 的效果要更好,可以减少23%到27%的节点访问量。但 由图可以看出,随着移动对象数目的增多,AIPR 是随着更新次数的增多两种索引的差距会逐渐减少,当tee和TPR-tree的空间体M值直都在增长,但是 更新次数达到一定规模时, TPR-tree以及 ATPR-tree索 TPR-tree的涨幅更大。由图可知,在对象的数量级达到 引节点访问次数下降的速率趋于相同,两条直线趋于平20K左右时,AIPR-te较PR-ree的空间体M值的大 稳,AIPR-re的节点访问量的降低程度停留在%%左小和节点访问次数有了较为明显的改观,这是因为 右。也就是说随着更新次数的增多两种索引的差距诚^TpR-tre索引会將属性值的离散性进行优化,在使节 少了,这是因为随着更新次数增多, TPR-tree节点的空点MBR、VBR保持尽量小的基础上,去压缩属性值区 白区域减少,代价函数得到的值减少,当更新次数达到间,将尽可能多的相似的属性值存入到一个节点中去。 定数量时代价函数值趋十最优,不会再有改变。且因而不把属性作为一个维度的 TPR-tree则不具有这个功 为对R进行优化的原因 ATPR-tree的代价函数值M会能,随着数据量的加大,评分值的离散性也恶化的比较 始终优于TPR-tre,但优势不如更新次数少时明显。 快,进而引起比较大的M值,增大了查询时节点重复访 除了更新次数,移动对象数量的不同,也会造成杳问的概率,加大了查询时节点访问的次数。 询性能的差异。图6这一组图片是其他参数不变的情 图7是不同查询频率TPR-tree以及ATPR-tre所需 况下不同数量级的移动对象进行同样一组查询所需要要的节点访问数量横轴代表在100个时间单位内给出查 的节点访问次数的对比。图6(a)中的横轴代表移动点询的数量,纵轴表示每个查洵数量对应的节点访问次数。 的数量,纵轴代表所需的节点访问量;图6(b)中的横轴 300 指代移动点的数量,纵轴指代在当前移动点数量下,索 ATPR-tree 引的所有节点的空间体M的值。 TPR-tree 20 400 atPR-tree 150 300 TPR-trc l00 200 0 1020406080100 查询次数/103 图7不同查询次数实验结果图 120406080100120 移动点数量/103 本文提出的方法,在查询次数为20000次开始,节 (a)不同移动对象数量下节点访问次数 点的访问次数相对于原始的 TPR-tree有明显的缩减,随 600 着查询的次数增多,ATPR-tre查询所需的节点访问次 ATPR-tree 50 数较 TPR-tre了22%到27%的提升。 TPR-tree 由查询算法可知,在索引每一层选择查询的入口 时,会将一部分不与QR1重叠的分支剪掉,进而减少了 300 节点的访问次数,也就是说Q给出的范围越窄时,可 以剪掉的分攴数量就越多,节点访问次数就越少,而Q 给出的范围越大时,可以筛选掉的节点数量就越少,节 1020406080100120 点的访问次数就会变多。 更新次数/10 图8是不同的查询评分值区间长度Q所对应的 (b)不同移动对象数量下节点空间矩形质量图 节点的访问次数,横轴是查询给定的分值区间的长度而 图6不同移动点数量实验结果图 纵轴是访问节点的次数在。可以从图中看出,随着区间 当对索引树进行维护时,需要反复调用插入算法,插长度的增大,AIPR-re合询所要访问的节点有所增加 入算法的时间复杂度为( anlon),囚为算法主要是对代访问次数增加了约20%左右,这是因为随着评分值区间 价模型进行了修改所以没有增加循环的次数,这其中对的扩大,在査进行入口判断时可以剪枝掉的分支数量 时间复杂度影响最大的是 Reinsert算法,且因为 Reinsert减少,进而增大需要访问的节点个数。而TPR-tree索引 算法在对每一个分支进行处理时需要按照空间维度和的节点访问值并没有随着评分值区间的长度而变化,而 速度维度进行排序操作,进而一定程度的提高了时间复是一直稳定在一个值而上下浮动。这是因为未经过改 王永会,张恩瑞: ATPR-Tree:带有属性维的时空索引 2017,53(7)87 造的IPR-tree索引没有对评分值进行压缩,离散性高,索引结构: ATPR-tree,这种新的索引结构在IP-tree的 不管给出的查询评分值区间的范围如何都不会影响节节点上附加了属性值维度,并且改变了TPR-tree的插 点的访问次数 入、删除以及奁询算法。 ATPR-tree相比较以往的先检 索出时空位置,再对满足某一条件值的对象进行筛选的 250 方法,可以提高查询语句在带有除时空位置外更多条件 时查询的效率,城少这一过程中节点的访问次数。 还 参考文献 ATPR-tree []郑宇,城市计算与人数据[J中国计算机学会通,2013,9 TPR-tree (8):8-16. 4 121620 [2]王静远,李超,熊璋,等.以数据为中心的智慧城市研究综 区间长度Q 述[J计算机研究与发展,2014,51(2):239259 图8不同QR实验结果图 3] Saltenis S, Jensen C S, Leutenegger S T, et al. Indexing 图9显示了在对象数量、更新次数以及区间长度和 the positions of continuously moving objects[C/Proceedings 查询时间·定的条件下,不同的查询窗口宽度所对应的 of sigmod.2000:331-342 4 Xiong H, Wang L, Zhang D EEMC: An energy-efficient 节点访问次数。在任何情况下ATPR-tree都要比TPR mobile crowd sensing mechanism by reusing call/SMS ure更少的节点访问次数,节点访问次数的减少在 connections[C]Proceedings of NetMob, 2013: 323-329 112%到20%之间。图10显示了随着时间段查询里时s] Guttman AR-tre: dynamic index structure for spatial 间间隔的增加,相同的一组查询所需要的节点访问数 searching[c] /Proceedings of SIGMOD, 1984: 47-57 量,本文提出的索引结构依然可以保持比TPR-tree耗费[6 I Korotkov A. A new double sorting-bascd nodc splitting 更少的节点访问次数,从而提高查询效率,节点访问次 algorithm for R-trec[. Programming and Computcr Softwarc 数的减少稳定在19%左右 2012,38(3):109-118 [7 Emrich T, Kricgel H PIndexing unccrtain spatio-tcmporal 150 data[cl/proccedings of the ACM SIGMOD Conference on Management of Data, 2012 138-147 [8 Al-Badarnch A F, Yaseen Q, Hmeidi I A new enhancement to the r-tree node splitting[J] Information Science, 2010, 36 (1):3-18 [9 Xu Jianqiu, Guting R H, Zheng YThe TM-rtree: An index ATPR-tree on generic moving objectsfor range queries[J]. Geoinfor TPR-tre matica,2014,26(5):743-746 4 区间长度Qs/10 [10 Wang Longhao, Zheng Yu, Xie Xing, et al. A flexible spatio 图9不同Q实验结果图 temporal indexing scheme for large-scale GPS track retrieval[C]/Proceedings of IEEE 14th International Confer- ence on Mobile Data Management( MDM 2008), 2008: 1-8 [Il Beckmann N, Kriegel H, Schneider R, et al. The R'-tree 00 An efficientand robust access method for points and rectangles[J.ACM SIGMOD Record, 1990, 19: 322-331 [12] Tao Y, Papadias D, Sun J. The TPR-tree: An optimized spatio-temporal access method for predictive queries[C]! ATPR-tree Proceedings of VlDB, 2003: 790-801 TPR-tree [13 Kim S w, Jang M H, Lim S C Active adjustment: An 0 4 16 effective method for keeping the TPR -tree compact[J] 区间长度Q Journal of Informalion Science and Engineering, 2010 图10不同(实验结果图 26(5):1583-1600 6结束语 [14 NiLkiewicz B, Panlczyk M.TPR-lree: Running in main menory[D]. Aalborg University, 2006 在城市计算领域屮,往往希望移动用户能携带除时15 Liang ye a eflicient indexing maintenance Inethod for 间、空间外更多的信息。以往的索引结构大多只能按照 grouping moving objecTs with grid[J]. Procedia Environ 移动对象的时空位置进行检索,而本文提出了一种新的 mental Sciences. 2011.11: 486-492

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐