基于查询代价的两级轨迹数据划分算法

来源:用户上传      作者:刘梦男 许建秋

　　摘要：轨迹数据具有规模大、更新频繁的特点，对轨迹数据的查询具有较高的性能要求.为了提高轨迹数据的查询效率，提出了两级轨迹数据划分算法：在第一级划分中，使用基于优化最小边界矩形（Minimum Bounding Rectangle， MBR）的轨迹数据划分方法将轨迹数据划分为子轨迹，以提高轨迹数据的近似效果;在第二级划分中，按照时空范围，使用网格结构对子轨迹进行分组.基于划分算法提出了 R-tree 结点组织方法，将划分后的轨迹数据自底向上地构建 R-tree.通过实验展示了所提的划分算法对查询效率的提升.实验表明，与基于轨迹段平均个数和基于组合运动特征这两种轨迹数据划分算法相比，所提算法具有更好的查询性能，查询效率分别平均提升了43.0%和30.5%.
　　关键词：轨迹数据; 时空查询; 轨迹划分; 查询优化
　　中图分类号： TP392 文献标志码： A DOI：10.3969/j.issn.1000-5641.2022.05.015
　　Two-level trajectory data partition algorithm based on query cost
　　LIU Mengnan， XUJianqiu
　　（College of Computer Science and Technology， Nanjing University of Aeronautics and Astronautics，Nanjing 211106， China）
　　Abstract： Trajectory data are typically large in scale and require frequent updates; hence， there are high performance requirements for trajectory queries. In order to improve the query efficiency of trajectory data， a two-level trajectory partition algorithm is presented herein. In the first partition， trajectory data was divided into sub-trajectories based on optimized minimum bounding rectangle （MBR） to improve the approximate effect of trajectory data. In the second partition， the sub-trajectories were grouped by the grid structure according to spatio-temporal characteristics. A packing method of R-tree was proposed based on the partition algorithm， and the divided trajectory data was packed into the R-tree from bottom to top. Finally， compared with a method based on the average number or average size of trajectory segments， experimental results show that the proposed method offers better query performance than the two other methods based on the average number of trajectory segments and combined movement features; in fact， the query efficiency is improved by 43% and 30.5%，respectively.
　　Keywords： trajectory data; spatio-temporal query; trajectory partition; query optimization
　　0 引言
　　近年恚随着物联网和移动互联网的不断发展，产生和收集大量轨迹数据变得可行.轨迹数据在路径推荐、路况预测和城市规划智能决策等领域有着重要的应用.轨迹数据具有重要的社会和应用价值.因此，对轨迹数据的存储、查询、处理和分析变得越发重要.
　　轨迹数据从采集到应用的过程中，存在很多问题亟待解决，由此出现了很多处理轨迹数据的技术.原始轨迹数据存在很多噪声和冗余，需要使用数据清洗、轨迹压缩等技术进行预处理再转化为校准轨迹.校准轨迹需要通过移动对象数据库管理系统进行存储、索引和查询等处理.对处理后的数据进行数据挖掘、隐私保护等操作后获得有价值的信息.轨迹数据划分是一种轨迹数据处理的方法，应用十分广泛.轨迹数据划分不仅可以通过划分原始轨迹数据来提高数据的索引和查询效率，还可以用于轨迹数据信息的提取和挖掘.本文的研究重点：通过对轨迹数据进行划分使索引结构高效地支持查询.
　　在移动对象数据库中，轨迹数据通过单个三维最小边界矩形（Minimum Bounding Rectangle， MBR）来近似表示.这种近似方法会导致大量空白，造成查询效率的低下.在查询过程中，过多的空白会使查询窗口与 MBR 相交，但并不与轨迹数据相交.图1所示为轨迹数据划分对查询的影响，其中黑色圆点连线为轨迹.如图1（a）所示，查询窗口 q1和查询窗口 q2与轨迹数据的 MBR 相交但并不与轨迹相交，这样会造成多余的 I/O （Input/Output）操作，降低查询效率.轨迹数据划分可以将轨迹数据分割为独立的子轨迹，再通过 MBR 近似划分后的子轨迹.可以很直观地看出，轨迹数据划分后的 MBR 要小于轨迹未划分的 MBR.这样就可减少通过 MBR 近似轨迹数据带来的空白体积，减少不必要的相交来提高查询的效率.如图1（b）所示，轨迹数据划分为子轨迹后，q1和q2不与轨迹的 MBR 相交.

nlc202210091056

　　为了能有效地处理基于轨迹的查询，需要支持轨迹数据查询的索引结构[1-3]. R-tree[4]作为1种常见的时空索引结构，可通过比较查询窗口与结点的 MBR， 逐步找到与查询窗口相交的数据.通过轨迹数据划分将轨迹数据划分为子轨迹可以减少数据层面的磁盘 I/O， 提高查询的效率.但引入划分会使 R- tree 索引存储的 MBR 增多，索引的规模变大，在查询过程中，会增大索引目录层面的磁盘 I/O.因此，需要使用合适的 R-tree 构建方法，将时空范围接近的子轨迹组织到同一结点中，减少索引目录级别的磁盘 I/O.
　　基于此，本文提出了两级轨迹数据划分算法（Two-Level Trajectory Data Partition Algorithm， TLPA）：在第一级划分算法中，使用基于优化 MBR 的轨迹数据划分算法将轨迹数据划分为子轨迹，使用子轨迹的 MBR 来近似轨迹数据，进而减少 MBR 的空白体积，提高近似效果，减少数据层面的磁盘 I/O 来提高查询效率;在第二级划分算法中，使用基于网格的区域划分算法，将子轨迹按照时空范围划分到相应的网格中，并在此基础上提出 R-tree 构建方法，将时空范围接近的子轨迹组织到同一结点中，减少索引目录层面的磁盘 I/O.通过两级划分算法，减少了数据层面和索引目录层面的磁盘 I/O 数量，提高了查询效率.本文使用真实出租车 GPS 数据集进行实验，与基于轨迹段平均个数的轨迹数据划分算法（Based on Average Number of Partition Algorithm， BNPA）和基于组合运动特征的轨迹数据划分算法（Based on Combined Movement Features， BCMF）进行了比较.结果显示，本文的两级轨迹数据划分算法具有更好的查询性能，查询效率较 BNPA 平均提升了43.0%，较 BCMF 平均提升了30.5%.
　　本文后续结构：第1章简要介绍轨迹数据划分的相关工作;第2章定义轨迹数据划分和查询的相关问题;第3章介绍两级轨迹数据划分算法;第4章介绍基于划分算法的 R-tree 构建方法和查询处理;第5章将本文提出的算法与现有的轨迹数据划分方法进行分析和比较;第6章是总结和展望.
　　1 相关工作
　　轨迹数据划分算法主要分为3种：基于时间的轨迹数据划分算法、基于特征点的轨迹数据划分算法和基于^域的轨迹数据划分算法. Yue 等[5]采用基于时间的哈希策略来保证分区平衡和更少的分区时间，从而提高海量轨迹数据集的范围查询效率. Tang 等[6]根据速度变化提取变化点，根据停留时间提取停留点，将欧几里得垂直距离指标与运动方向相结合，将变化点和停留点、识别方向突变的点作为特征点，并使用这些特征点进行轨迹数据划分. Morteza等[7]提出了将由轨迹的最小边界矩形（MBR）定义的轨迹区域划分为包含运动对象 GOI （Geometry of Interest）的网格的方法，该方法基于提取的 GOI 和划分的轨迹区域，可以仅使用相交几何算子提取轨迹的访问地点的顺序（Sequence of Visited Locations， SVL）.
　　按照应用场景分类，轨迹数据划分算法主要分为3种：通过轨迹数据划分来进行数据分析，提取出轨迹数据中的离群点;通过区域划分策略来解决空间轨迹的聚类问题;通过对移动对象轨迹进行划分使索引结构高效地支持时空范围查询. Lee 等[8]提出了轨迹离群点的划分和检测框架，该框架将1条轨迹数据划分为1组线段，然后针对轨迹离群点检测外围线段，并基于这种划分检测框架，开发了轨迹异常值检测算法（TRAjectory Outlier Detection， TRAOD）. Masciari[9]提出了基于合适的区域划分策略和合适度量的高效聚类技术用于解决空间轨迹的聚类问题. Hadjieleftheriou等[10]首先提出通过引入人工分割来划分轨迹数据;由于使用 MBR 近似时空对象时会产生大量空白体积，这将导致传统的多维索引效率降低，然后提出了可以将时空对象分割成预定数量的轨迹段的轨迹数据划分算法，使划分后的轨迹的MBR体积最小，从而提高索引的查询效率. Rasetic等[11]提出的正式的代价模型，用于估计给定的查询大小和轨迹的任意分割来评估时空范围查询所需的 I/O 数量;此模型引入了动态规划算法来分割1组轨迹，这样使相对于平均查询大小的预期磁盘 I/O 数量达到了最小化.
　　2 问题描述
　　本章对本文所使用的术语进行了定义和解释，并给出了文中使用的符号及其释义.符号和释义详见表1.
　　定义1轨迹：轨迹通常是由时间和二维空间的函数进行建模.在数据库系统中，用时间单元序列来表示轨迹.假设轨迹由 T =?u1，u2，・・・，ut?来表示，其中ui是1个轨迹段，由?ti，ti+1， xi，yi，xi+1， yi+1?表示，ti和ti+1分别为1个时间间隔的开始时间和结束时间，（xi，yi ）和（xi+1， yi+1）分别为开始时间的空间位置和结束时间的空间位置.
　　定义2轨迹 MBR：轨迹 MBR 是指以三维坐标表示的轨迹数据的最大范围.
　　定义3轨迹数据划分：轨迹 T =?u1，u2，・・・，ut?可以通过多种可能的方式（从 T 中选择m 个分割点）， 沿其离散时间维度分割成m +1段，其中0< m < t .用 T [b， d]表示1条以ub开头、ud结尾的子轨迹.这样划分后的轨迹可以表示为 T （m）={T [1， i1]，T [i1，i2]，・・・，T [im，t]}，划分后的m 个子轨迹取并集仍能组合生成原始轨迹.
　　定义4时空范围查询：给定轨迹数据集 S，时间范围（ts，te ）（ts为开始时间，te为结束时间）， 空间范围（xl，yl，xu，yu ）（（xl，yl ）表示空间范围的左下坐标，（xu，yu ）表示空间范围的右上坐标）， 查询所有满足 t 在区间[ts，te ]、位置（x， y ）在空间范围（xl，yl，xu，yu ）中的时空对象.

nlc202210091056

　　3 算法描述
　　3.1 查询代价分析
　　给定1条划分后的轨迹T （m），假设轨迹段的 MBR 是独立存储的，查询窗口和每个轨迹段的 MBR 相交都要耗费1个独立的磁盘I/O.则轨迹与查询窗口（q）相交的磁盘 I/O 次数（D）的计算公式[12]为
　　为求解Intersect （T（m），q），下面以二维情况为例，给出推导过程.由于查询窗口的大小和位置是未知的，故不能准确求出空间对象 MBR 与查询窗口的相交次数，需要用相交的概率来估计相交次数.在二维空间中，假设查询窗口 q=（?x， ?y）等可能地出现在整个数据空间的各个位置，如图2所示，其中，q .?x 和 q .?y 分别表示查询窗口 x 维度的长度和查询窗口 y 维度的长度.图2中，查询窗口（q）与 MBR 相交当且仅当查询窗口的中心落入区域.由于查询窗口是等可能地出现在数据空间的各个位置，因此，相交的概率为区域的面积与总数据空间面积的比值，其中区域为 MBR 沿x，y维度拓展查询窗口大小的一半得到的区域.把这个区域命名为拓展 MBR.空间对象的拓展 MBR 越大，说明 MBR 的近似效果越差，导致空间对象与查询窗口相交概率增大，相交次数也相应增大.这样会造成更多的不必要的相交，降低查询效率.因此，轨迹数据的最优划分要保证划分后的轨迹数据的拓展 MBR 最小.
　　显然，对于轨迹数据来说，增加划分段数会减少划分后子轨迹的 MBR 总体积，但对于拓展 MBR 来说，情况并非如此.拓展 MBR 是将轨迹数据的 MBR 沿 x 方向左右、y 方向上下分别延伸 X/2、Y/2长度.当查询窗口较大时，增加划分段数会使轨迹数据通过拓展增大的体积大于划分导致的 MBR 减少的体积.因此，在划分前需要通过查询窗口和轨迹数据来定量分析得到最优的划分段数.
　　基于上述分析，给出下列引理及证明.
　　引理1给定二维空间对象 O ={o1，o2，・・・，om }，oi 为（xi ，yi ，xi+1，yi+1），其中，xi+1>xi，yi+1>yi，当划分段数确定时，划分后的空间对象 O 的拓展 MBR 面积（用 Sn 表示）与其 MBR 面积（用 SB O ，n 表示）满足
　　证明设查询窗口在x，y维度上的大小分别为X， Y .假定划分段数为 n （n<m?1）， 则有多种可能的方式将 O 划分 n 个子空间对象，表示为O =（O[1， k1]， O[k1，k2]， ・・・，O[kn―1，m]），其中O[1，k1]表示包含 o1，o2，・・・，ok 1的空间对象.将这些子空间对象近似为1组 MBR， 表示为 B O =（MBR（O[1， k1]）， MBR（O[k1，k2]）， ・・・，MBR（O[kn―1，m]）， O 的所有可能划分情况表示为Gather（O， n）={（B1，B2，・・・，Bn ）|3 k1，・・・，kn―1： B1= MBR（O[1， k1]）， B2= MBR（O[k1，k2]）， ・・・，Bn = MBR（O[kn―1，m]）}. O[1， k1]的拓展 MBR 大小S（O[1， k1]）为
　　将所有子空间对象的拓展 MBR 相加可以得到
　　其中，nXY +（ym+1?y1） X+（xm+1?x1） Y 为定值，SB O ，n 为划分后的空间对象 O 的 MBR 面积，B O ∈ Gather（O， n）.因此，当划分段数和查询窗口大小确定时，划分后的空间对象 O 的拓展 MBR 面积（Sn ）仅由其 MBR 面积（SB O ，n ）决定.
　　引理2给定二维空间对象O ={o1，o2，・・・，om }，oi 为（xi ，yi ，xi+1，yi+1），其中，xi+1>xi，yi+1>yi，O 的最优划分段数（使拓展 MBR 面积最小的划分段数）仅与查询窗口大小有关，且随着查询窗口的增大，最优划分段数从m 逐渐减少到0.
　　证明根据引理1可知，当划分段数为n 时，设 O 的最小拓展 MBR 面积为
　　其中Gather（O， n）为划分段数为n 时，O 的所有划分的集合.
　　当划分段数为n+1时 ，
　　则 Sn+1? Sn = XY + min SB O ，n+1? min SB O ，n .当 XY > min SB O ，n ?min SB O ，n+1时， Sn+1>Sn .划分段数为 n 时， O 的最小拓展 MBR 面积更小.因此，通过B O 2Gather（O，n+1）XY 与 min SB O ，n 的值，可以求出O 的最优划分段数.B O 2Gather（O，n）
　　显然，对于 min SB O ，n 来说，随着 n 的增加会使其减少，且随着 n 的增加 ，B O 2Gather（O，n）min SB O ，n ? min SB O ，n+1亦减少 .因此，当 XY < min SB O ，m ―2?min SB O ，m ―1时，最优划分段数为 m ?1;随着 XY 的增大，划分段数逐渐减少，直到B O 2Gather（O，1）

nlc202210091056

　　基于引理2可以发现，仅通过 oi 的值就可以求出 min SB O ，n 的值.因此，可以通过 XY 与B O 2Gather（O，n）min SB O ，n 的值获取m?1个分界点，将整个数据空间范围划分为连续的m 个区间，其中每个区间对应查询窗口大小 XY 的具体范围和该范围下的最优划分段数;再通过引理1就可以得出min SB O ，n 对应的划分方式，即为最优划分方式.B O 2Gather（O，n）
　　3.2 基于优化 MBR 的轨迹数据划分算法
　　在数据库中，时间维度和空间维度被同等对待.因此，上述分析对于作为三维时空对象的轨迹数据同样适用.给定1条轨迹 T， 查询窗口 q=（X，Y ，Z）， 其中X， Y， Z 分别为q 在x，y，t维度上的大小.使用ui的值则可求出最优划分段数对应的查询窗口大小区间和在该划分段数下的最优划分方式.
　　基于以上讨论，给出基于优化 MBR 的轨迹数据划分算法.具体见算法1.
　　算法1中： track 数组用于保存轨迹数据划分状态，初始化时插入0和T.size， 表示当前子轨迹只有1条，为原始轨迹，当经过1次循环找到1个划分点后，插入 track， 记录当前划分状态; result 数组用于保存划分方式及对应的查询窗口区间，在循环结束后，作为 partition（）函数的参数用于划分; partition（）函数通过使用给定的查询窗口大小和 result 数组得到最优划分方式.
　　通过算法1， 可以得出每条轨迹数据针对不同查询窗口大小的最优划分方式.对于整个轨迹数据集中的每个轨迹数据均采用算法1， 最后可以得到整个数据集上的最优划分.在实际应用中，查询窗口的大小不能预先确定，需要通过数学统计及分析预先得出查询窗口的平均大小.在平均大小不能很好地代表查询窗口的大小时，可以将查询窗口大小的范围与求出的区间进行比较，选出相交区域最多的区间进行划分.这样可以保证划分后的轨迹数据在尽可能大的查询窗口范围内其查询效率最优.在不能预先获取查询窗口大小的情况下，可以将整个查询窗口大小范围划分为多段，作为基准分别建立 R-tree;在查询过程中，通过具体查询的窗口大小选择对应的 R-tree.对于基于优化 MBR 的轨迹数据划分算法，可以得到每条轨迹数据的划分方式及对应的查询窗口区间.因此，建立不同查询窗口大小范围的多条 R-tree 的时间代价会低很多.
　　3.3 基于网格的区域划分算法
　　基于优化 MBR 的轨迹数据划分算法可以根据预期查询窗口大小将轨迹数据划分为多条子轨迹，并通过子轨迹的 MBR 近似轨迹数据，减少数据层面的磁盘访问次数.但 R-tree 索引是将多条轨迹组织到叶子结点中来回答查询，数据层面的优化不能保证构建索引后仍然是最优的.因此，本文提出了基于网格的区域划分算法：将通过基于优化 MBR 的轨迹数据划分算法划分后的子轨迹进行分组，把时空范围接近的子轨迹数据划分为1组;针对分组后的子轨迹设计 R-tree 构建算法，提高索引目录层面的查询效率.
　　基于网格的区域划分算法：首先，将时空范围划分为多个大小相等的不重叠的网格单元，每个单元仅存放完全包含在单元内的轨迹数据，如果轨迹数据穿过时空分割边界，则轨迹数据在边界处进行划分，并插入2个网格单元中（图3）;然后，将落入网格单元中的轨迹数据作为元组存储到数据文件中，每个数据页仅包含来自同一网格中的轨迹数据，网格单元存放这些数据页的信息以用于查找.
　　网格划分粒度是1个很重要的参数：一方面，如果网格单元的范围过大，会导致不同网格间的时空区分度低，增加 R-tree 构建的难度;另一方面，如果网格划分得非常精细，那么跨越网格边界的轨迹数就会增加，这反过来又会增加划分开销.选取原始轨迹数据的平均大小作为划分粒度既不会使网格空间范围过小，引入大量的划分，也不会使网格空间过大，降低时空区分度.
　　基于网格的区域划分算法使每个网格单元中的轨迹数据的时空范围相近，且每个网格单元数据量较少，便于 R-tree 结点的组织与构建.
　　4 R-tree 构建和查询处理
　　4.1 R-tree 构建
　　常规的 R-tree 的构建方法有2种，分别为自底向上[13-14]和自顶向下[15]的构建方法.自顶向下的构建方法采用插入的方式逐个将对象插入 R-tree 结点，这种构建方式存在一些缺点，如较高的构建时间、较低的结点利用率等.因此，本文的 R-tree 构建方法采用自底向上的 R-tree 建方法，将划分后的子轨迹按照一定的规则构建 R-tree.
　　在使用基于网格的划分算法将子轨迹分组后，每个网格中的子轨迹时空范围相近.因此，R- tree 的每个叶子结点仅存储来自同一网格中的子轨迹，不仅提高了构建效率，而且使时空范围相近的子轨迹存放到同一叶子结点中，还提高了索引的查询性能.
　　基于网格划分的构建方法的示意图如图4所示.
　　R-tree 结点组织方法的基本思想：首先，选取网格中时间维度最小的子轨迹，将其作为只有1个条目的叶子结点，通过计算，将网格中其余子轨迹插入叶子结点后叶子结点 MBR 增量，选取f ?1个增量最小的子轨迹构建叶子结点;然后，从剩余子轨迹中继续选取时间维度最小的子轨迹，重复上述过程，直到网格中所有子轨迹均插入叶子结点，再进入下个网格，生成所有叶子结点;最后，将叶子结点看作新的条目，按照上述过程递归生成中间结点，直到生成根结点.
　　4.2 查询处理
　　R-tree 的叶子结点存储的条目为是轨迹的唯一标识符TupleID和 MBR.在查询过程中，通过比较结点 MBR 与查询窗口是否相交来逐步获取轨迹 MBR 与查询窗口相交的条目，生成候选轨迹列表.由于 R-tree 存储的是划分后的子轨迹，因此，候选轨迹列表中可能会出现属于同一轨迹的多条子轨迹.所以在生成候选轨迹列表后，要对列表进行去重操作;去重后，使用TupleID获取具体的轨迹信息，然后再进行相交判断，获取与查询窗口相交的轨迹.

nlc202210091056

　　基于优化 MBR 的轨迹数据划分方法是通过与查询窗口相交的次数的分析得到的，它适用于时空范围查询.对于轨迹 k-近邻查询、轨迹相似性查询等查询方式，同样可以使用合适的查询窗口得到结果.出于篇幅考虑，本文不做进一步的讨论.
　　5 实验评估
　　5.1 前期准备
　　实验数据集使用北京市2008年3月2日至3月8日的10357条出租车 GPS 轨迹数据.轨迹数据的采样点为1083560个.实验在 Ubuntu14.04环境下进行，采用 C++语言编写，利用可拓展的移动对象数据库系统 Secondo[16]框架进行实验评估. CPU 为 Intel Xeon（R）1.90 GHz ×6， GPU NVIDA Corporation GM107GL [Quadro K2200]， 32 GB 内存.
　　5.2 实验及结果
　　实验首先采用第3章提出的轨迹数据划分算法分别对数据集中的轨迹数据进行逐条划分，查询窗口大小分别设置为1%、5%、10%数据空间大小;然后将划分后的轨迹数据用第4章提出的 R-tree 构建算法构建 R-tree;最后用中央处理器运行时间（CPUtime）来衡量查询效率.本文将使用基于组合运动特征的轨迹数据划分算法（BCMF）和基于轨迹段平均个数的轨迹数据划分算法（BNPA）与本文提出的两级轨迹数据划分算法（TLPA）进行了对比实验，并对使用 Secondo 中的Bulkload构建方法和基于网格划分的构建方法进行了对比实验. BNPA 是基于平均度量的轨迹数据划分算法，它分别使用轨迹数据的平均轨迹段个数进行划分，划分后的子轨迹的轨迹段个数不超过平均轨迹段个数.
　　图5、图6、图7分别给出了本文的轨迹数据划分算法（TLPA）与基于轨迹段平均个数的轨迹数据划分算法（BNPA）和基于组合运动特征的轨迹数据划分算法（BCMF）， 在不同查询窗口大小下的轨迹范围查询效率的结果.图5、图6、图7中，横轴为查询窗口大小，纵轴为查询所需的 CPUtime，TLPA1%、TLPA5%、TLPA10%分别表示 TLPA 的查询窗口大小设置为1%、5%、10%数据空间大小.从图5、图6、图7中可以看到，TLPA在查询窗口大小为整个数据空间的1%、5%、10%时查询效率都优于 BCMF 和 BNPA 这2种算法.其中，TLPA 在查询窗口大小为整个数据空间的1%时（图5）， 相比 BCMF 查询所需的CPUtime减少了11.7%，相比 BNPA 减少了55%; TLPA 在查询窗口大小为整个数据空间的5%时（图6）， 相比 BCMF 查询所需的CPUtime减少了30%，相比 BNPA 减少了62%; TLPA 在查询窗口大小为整个数据空间的10%时（图7）， 相比 BCMF 查询所需的CPUtime减少了50%，相比 BNPA 减少了12%.在给定查询窗口大小的情况下，与 BCMF 和 BNPA 相比，TLPA 具有更好的查询性能，查询效率较 BCMF 平均提升了30.5%，较 BNPA 平均提升了43%. BCMF 在查询窗口较小时查询性能较好，原因是 BCMF 的划分粒度很细，会将轨迹数据划分为较多的子轨迹，相当于针对较小查询窗口的最优划分. BNPA 的划分粒度较粗，会将轨迹数据划分为较少的子轨迹，相当于针对较大查询窗口的最优划分，在较大查询窗口时的查询效果更好.
　　图8给出了Bulkload和基于网格划分的构建方法在构建 R-tree 时的效果对比. TLPA5%算法划分后的轨迹数据分别使用了Bulkload和基于网格划分的构建方法构建 R-tree， 并比较了在各个查询窗口大小下的磁盘访问（I/O）次数.从图8中可以看到，使用基于网格划分的构建方法磁盘访问次数相比Bulkload少了约20%，构建 R-tree 效果更好.
　　6 总结与展望
　　本文提出的两级轨迹数据划分算法，对轨迹数据进行划分使之可以高效地支持时空范围查询.基于两级轨迹数据划分算法，本文提出了 R-tree 构建方法，对划分后的轨迹数据进行组织构建.使用此方法构建的 R-tree 比使用 Secondo 中Bulkload构建得到的 R-tree 回答范围查询的查询效率更高.本文主要介绍的是轨迹数据划分算法对范围查询的优化，但对于 k-近邻查询和轨迹相似性查询等查询方式同样可以使用查询框来近似得到查询结果，未来可以对此做进一步的研究.
　　[参考文献 ]
　　[1]张林， 汤大权， 张.时空索引的演变与发展[J].计算机科学， 2010， 37（4）：15-20，26.
　　[2]赵馨逸， 黄向东， 乔嘉林， 等.基于不均匀空间划分和 R 树的时空索引[J].计算机研究与发展， 2019， 56（3）：666-676.
　　[3] CHAKKA P V， EVERSPAUGH A C， PATEL J M. Indexing large trajectory data sets with SETI [C/OL]// First BiennialConference on Innovative Data Systems Research， CIDR 2003.（2003-01-05）[2022-06-09]. https：//www.cidrdb.org/.
　　[4] GUTTMAN A. R-trees： A dynamic index structure for spatial searching [G]// Readings in Database Systems. San Francisco： MorganKaufmann Publishers Inc.， 1994：125-135.

nlc202210091056

　　[5] YUE Z W， ZHANG J W， ZHANG H B， et al. Time-based trajectory data partitioning for efficient range query [C]// InternationalConference on Database Systems for Advanced Applications. Cham： Springer， 2018：24-35.
　　[6] TANG J， LIU L F， WU J G. A trajectory partition method based on combined movement features [J]. Wireless Communications andMobile Computing， 2019， 2019：7803293. DOI：10.1155/2019/7803293.
　　[7] MOUASVI S M， HARWOOD A， KARUNASEKERA S， et al. Geometry of interest （GOI）： Spatio-temporal destination extraction andpartitioning in GPS trajectory data [J]. Journal of Ambient Intelligence and Humanized Computing， 2017， 8（3）：419-434.
　　[8] LEE J G， HAN J， WHANG K Y. Trajectory clustering： a partition-and-group framework [C]// Proceedings of the 2007 ACMSIGMOD International Conference on Management of Data. ACM， 2007：593-604.
　　[9] MASCIARI E. Trajectory clustering via effective partitioning [C]// International Conference on Flexible Query Answering Systems.Berlin： Springer， 2009：358-370.
　　[10] HADJIELEFTHERIOU M， KOLLIOS G， TSOTRAS V J， et al. Efficient indexing of spatiotemporal objects [C]// InternationalConference on Extending Database Technology. Berlin： Springer， 2002：251-268.
　　[11] RASETIC S， SANDER J， ELDING J， et al. A trajectory splitting model for efficient spatio-temporal indexing [C]// VLDB’05：Proceedings of the 31st International Conference on Very Large Data Bases. VLDB Endowment， 2005：934-945.
　　[12] THEODORIDIS Y， SELLIS T. A model for the prediction of R-tree performance [C]// Proceedings of the 15th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM， 1996：161-171.
　　[13]李松， 崔h宇， 张丽平， 等.基于CURE聚类算法的静态R树构建方法[J].计算机科学， 2015， 42（10）：193-197.
　　[14] LEUTENEGGER S T，LOPEZ M A， EDGINGTON J. STR： A simple and efficient algorithm for R-tree packing [C]// Proceedings13th International Conference on Data Engineering. IEEE， 1997：497-506. DOI：10.1109/ICDE.1997.582015.
　　[15] BECKMANN N， KRIEGEL H P， SCHNEIDER R， et al. The R*-tree： An efficient and robust access method for points and rectangles[C]// SIGMOD Conference. ACM， 1990：322-331.
　　[16] G?TING R H， BEHR T， D?NTGEN C. SECONDO： A platform for moving objects database research and for publishing andintegrating research implementations [G]// Bulletin of the IEEE Computer Society Technical Committee on Data Engineering. IEEE，2010：56-63.
　　（责任编辑：李艺）

nlc202210091056

转载注明来源:https://www.xzbu.com/1/view-15440632.htm