7期 周做英等：基于位置的服务：架构与进展 1159 3DR-tree1町把时间维当作一个额外的空间维， 的目录删除后再插入，或者是将该节点的MBR进 不区分空间维和时间维，用一个3DR-tree统一对 行扩展以包含该对象的新位置，为了应对移动对象 在这个三维空间内的轨迹进行索引，使得空间查询、 频繁的更新操作，RUM-tree2]利用保存在内存的 时间查询、时空查询在3DR-tree上统一实现.MR- 特定信息，在更新时能避免访问磁盘来实现删除旧 tree)和HR-tree2o]对每一个时刻的移动对象的位 条目.而过期的旧条目将以批处理方式移除，从而提 置建立一个R-tree.为了节省索引的空间，对连续时 高了更新操作的效率. 刻内位置未发生改变的移动对象不再进行保存，而 3.3将来位置索引技术 是通过指针指向前一个节点.MV3R-tree2)同时维 为了索引未来时刻的移动对象位置，通常情况 护两棵树：MVR-tree和3DR-tree,其中MVR-tree 下需要根据移动对象的速度V对移动对象的未来 用于处理时间参数为时刻的时空查询，3DR-tree用 位置建模，即locationnew=locationo十VX(tnew一 于处理时间参数为时间间隔的时空查询.为了处理 t).对移动对象将来位置的索引技术分为两类：基 针对轨迹的查询，TB-tree2利用类似R-tree的结 于R-tree的索引结构和基于B+-tree的索引结构. 构，但是它要求每个节点只保存来自于同一移动对 TPR-tree2]和TPR'-tree[so]使用时间参数的MBR 象轨迹的时空数据.这样，在时空上临近但不属于一 来组织移动对象，在组织节点时不仅考虑移动对象 个移动对象轨迹的数据将被分别保存在不同的节 当前的位置，也考虑移动对象的速度，因而MBR能 点内 随时间的变化而扩展.当移动对象的位置更新时，则 基于Hash的索引结构通常将空间维和时间维 重新计算包含该对象的MBR.由于这类索引结构保 分开处理.SET2]把空间维和时间维区分开：使用 存了速度信息，因而能预测移动对象的将来位置 静态、无重叠的网格划分空间维度（如图3所示）：使 REr-tree)是TPR-tree的一种扩展，它针对部分 用一维R-tree索引各空间网格内的时间维度.Song 移动对象长时间不更新位置信息导致MBR不断扩 在其相关研究中也是先按照空间维度使用静态的网 大的缺点，设定一个失效时间以删除失效的移动对 格划分[2)，而对每个空间网格内的对象的时间属性 象或重新计算.VCIR--tree]额外保持每个R-tree 进行转化，用SEB-tree2进行素引. 节点的所有对象的最大速度，在查询处理时，根据查 询时间和最大速度对MBR或查询本身进行扩展， 如图4所示. 扩展的MBR MBR.V 图3SETI中基于空间的网格划分[2] 3.2当前位置索引技术 Query 移动对象的位置随时间不停变化，这就要求索 引结构能够应对大量更新操作.2十3R-tree[ze)是一 种既能索引历史轨迹，又能索引当前位置的方法，它 MBR2,V 扩展的Query 维护了两个R-tree,一个2DR-tree用于索引移动对 R △XVm 象当前位置，另一个3DR-tree用于索引移动对象 R 的历史轨迹.当移动对象的位置改变时，一条新的轨 Query: 迹线段被构造出来并插入至3DR-tree中，与此同 时，新位置插人到2DR-tree中，且旧位置从2D R-tree中移除.LUR-treel2)通过R-tree索引移动对 象的当前位置，以满足移动对象频繁的位置更新操 图4VCIR-tree处理范围查询时的MBR扩展和查询扩展[町 作.一旦移动对象的位置改变，新的位置将及时更新 利用B+-tree对移动对象建立索引也是一种重 到R-tree中.如果新位置仍然在其原先节点的 要的方法.B-tree]是第一个基于B+-tree索引移 MBR内，只需更改该目录的位置；如果新的位置超 动对象的方法.整个空间被划分为若干个单元格，借 出其节点的MBR,则根据不同策略选择是将该对象 助于空间填充曲线(space filling curve),每个单元３ＤＲｔｒｅｅ［１８］把时间维当作一个额外的空间维， 不区分空间维和时间维，用一个３ＤＲｔｒｅｅ统一对 在这个三维空间内的轨迹进行索引，使得空间查询、 时间查询、时空查询在３ＤＲｔｒｅｅ上统一实现．ＭＲ ｔｒｅｅ［１９］和ＨＲｔｒｅｅ［２０］对每一个时刻的移动对象的位 置建立一个Ｒｔｒｅｅ．为了节省索引的空间，对连续时 刻内位置未发生改变的移动对象不再进行保存，而 是通过指针指向前一个节点．ＭＶ３Ｒｔｒｅｅ［２１］同时维 护两棵树：ＭＶＲｔｒｅｅ和３ＤＲｔｒｅｅ，其中ＭＶＲｔｒｅｅ 用于处理时间参数为时刻的时空查询，３ＤＲｔｒｅｅ用 于处理时间参数为时间间隔的时空查询．为了处理 针对轨迹的查询，ＴＢｔｒｅｅ［２２］利用类似Ｒｔｒｅｅ的结 构，但是它要求每个节点只保存来自于同一移动对 象轨迹的时空数据．这样，在时空上临近但不属于一 个移动对象轨迹的数据将被分别保存在不同的节 点内．基于Ｈａｓｈ的索引结构通常将空间维和时间维 分开处理．ＳＥＴＩ［２３］把空间维和时间维区分开：使用 静态、无重叠的网格划分空间维度（如图３所示）；使 用一维Ｒｔｒｅｅ索引各空间网格内的时间维度．Ｓｏｎｇ 在其相关研究中也是先按照空间维度使用静态的网 格划分［２４］，而对每个空间网格内的对象的时间属性 进行转化，用ＳＥＢｔｒｅｅ［２５］进行索引． 图３ＳＥＴＩ中基于空间的网格划分［２３］ ３２当前位置索引技术 移动对象的位置随时间不停变化，这就要求索 引结构能够应对大量更新操作．２＋３Ｒｔｒｅｅ［２６］是一 种既能索引历史轨迹，又能索引当前位置的方法，它 维护了两个Ｒｔｒｅｅ，一个２ＤＲｔｒｅｅ用于索引移动对 象当前位置，另一个３ＤＲｔｒｅｅ用于索引移动对象 的历史轨迹．当移动对象的位置改变时，一条新的轨 迹线段被构造出来并插入至３ＤＲｔｒｅｅ中，与此同 时，新位置插入到２ＤＲｔｒｅｅ中，且旧位置从２Ｄ Ｒｔｒｅｅ中移除．ＬＵＲｔｒｅｅ［２７］通过Ｒｔｒｅｅ索引移动对 象的当前位置，以满足移动对象频繁的位置更新操 作．一旦移动对象的位置改变，新的位置将及时更新 到Ｒｔｒｅｅ中．如果新位置仍然在其原先节点的 ＭＢＲ内，只需更改该目录的位置；如果新的位置超 出其节点的ＭＢＲ，则根据不同策略选择是将该对象 的目录删除后再插入，或者是将该节点的ＭＢＲ进 行扩展以包含该对象的新位置．为了应对移动对象 频繁的更新操作，ＲＵＭｔｒｅｅ［２８］利用保存在内存的 特定信息，在更新时能避免访问磁盘来实现删除旧 条目．而过期的旧条目将以批处理方式移除，从而提 高了更新操作的效率． ３３将来位置索引技术 为了索引未来时刻的移动对象位置，通常情况 下需要根据移动对象的速度犞对移动对象的未来 位置建模，即犾狅犮犪狋犻狅狀ｎｅｗ＝犾狅犮犪狋犻狅狀ｏｌｄ＋犞×（狋ｎｅｗ－ 狋ｏｌｄ）．对移动对象将来位置的索引技术分为两类：基 于Ｒｔｒｅｅ的索引结构和基于Ｂ＋ｔｒｅｅ的索引结构． ＴＰＲｔｒｅｅ［２９］和ＴＰＲｔｒｅｅ［３０］使用时间参数的ＭＢＲ 来组织移动对象，在组织节点时不仅考虑移动对象 当前的位置，也考虑移动对象的速度，因而ＭＢＲ能 随时间的变化而扩展．当移动对象的位置更新时，则 重新计算包含该对象的ＭＢＲ．由于这类索引结构保 存了速度信息，因而能预测移动对象的将来位置． ＲＥＸＰｔｒｅｅ［３１］是ＴＰＲｔｒｅｅ的一种扩展，它针对部分 移动对象长时间不更新位置信息导致ＭＢＲ不断扩 大的缺点，设定一个失效时间以删除失效的移动对 象或重新计算．ＶＣＩＲｔｒｅｅ［３２］额外保持每个Ｒｔｒｅｅ 节点的所有对象的最大速度，在查询处理时，根据查 询时间和最大速度对ＭＢＲ或查询本身进行扩展， 如图４所示． 图４ＶＣＩＲｔｒｅｅ处理范围查询时的ＭＢＲ扩展和查询扩展［３２］ 利用Ｂ＋ｔｒｅｅ对移动对象建立索引也是一种重 要的方法．Ｂｘｔｒｅｅ［３３］是第一个基于Ｂ＋ｔｒｅｅ索引移 动对象的方法．整个空间被划分为若干个单元格，借 助于空间填充曲线（ｓｐａｃｅｆｉｌｌｉｎｇｃｕｒｖｅ），每个单元 ７期 周傲英等：基于位置的服务：架构与进展 １１５９