Chap4-2 轨迹索引与检索

1、武汉大学测绘学院 李英冰YB Li, SGG, Wuhan University4.2 轨迹的索引与检索Trajectory Indexing and Retrieval3/25/2022武汉大学 李英冰1. 树2. 轨迹查询3. 轨迹数据检索目录2 (a) Query （t3）= p3 (b) Query （t3）=？武汉大学 李英冰31.树轨迹与轨迹存储Trajectory of moving objects. (a) Trajectory in the real world. (b) Trajectory stored in a database武汉大学 李英冰路网（轨迹）信息可以转换成

2、树进行存储4轨迹与树Structure of the NDTR-Tree. (a) Traffic network. (b) UT-Units submitted in router1.(c) The corresponding NDTR-Tree武汉大学 李英冰树(Tree)是n(n=0)个结点的有限集T q有且仅有一个特定根(Root)的结点；q其余结点可分为m个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。基本概念ACGBDEFKLHMIJ武汉大学 李英冰1层2层4层3层height= 4ACGBDE FK LHMIJ层次 根为第1层 最大层

3、数为树的深度（高度） 双亲 (直接前驱） 孩子（直接后继） 兄弟 堂兄弟 子孙 祖先森林-m(m=0)棵互不相交的树的集合。d=3d=0d=2K LFGMI JABCDEH基本常用术语度 一个结点的子树的个数称为该结点的度武汉大学 李英冰7树和森林的遍历先根次序遍历*访问根结点*依次先根遍历根的各子树 D T1 T2 T3BEF CG DH IJ先根次序遍历森林依次先根遍历各子树ABCDE FG HIKJACGBDEFHIJACGBDEFHIJK武汉大学 李英冰dataparent 0 1 2 3 4 5 6双亲表示树的存储结构A B C D E F G-1 0 0 0 1 1 3指向其双亲的

4、位置data parent特点：很快确定双亲结点ACGBDEF武汉大学 李英冰每个结点拥有孩子的个数不同，所以采用单链表链接孩子结点。9孩子双亲表示法ACGBDEF0123456data headptrABCDEFG123456data parent headprt-1000113typedef struct cnode int child; struct cnode *next;link;typedef struct datatype data; link *headptr;ctree;ctree Tmaxnode;武汉大学 李英冰LRLR？二叉树与度为2的树的区别度 2 =2 序 有序 无

5、序ABDEFGABCD FE二叉树 (Binary Tree)武汉大学 李英冰二叉树的性质性质1 在二叉树的第 i 层最多有 2i-1 个结点。(i 1)性质2 深度为 k 的二叉树至多有 2k-1个结点。(k 1)性质3 对任何一棵二叉树, 若其叶结点个数为 n0, 度为2的结点个数为 n2, 则有 n0n21武汉大学 李英冰深度为k且有2k-1个结点，所有分支结点的度为 2， n1=0 叶子结点都在最下一层。叶子结点都在最下两层，且最下一层集中在最左边。12 34 5 6 78 9 10 11 12 13 14 15 12 34 5 6 78 9 10 满二叉树和完全二叉树武汉大学 李英冰

6、12 34 5 6 78 9 10 二叉树的性质 武汉大学 李英冰由于（性质5）完全二叉树按层次编号后，可确定各结点与其双亲及孩子的关系，则完全二叉树按编号次序进行顺序表示。完全二叉树的顺序表示二叉树的存储结1 2 3 4 5 6 7 8 9 10结点5： 双亲是结点 2 左孩子是结点 10 没有右孩子武汉大学 李英冰一般二叉树顺序表示二叉树的存储结构JABCFEDGHI1 2 3 4 5 6 7 8 9 10 11 12 13 14将一般二叉树转换为完全二叉树（添加虚结点），然后按层次编号次序进行顺序表示。A B C D E F G H I J结点E（6）： 双亲是

7、结点C（3） 左孩子是结点 I（12） 没有右孩子（13为空）武汉大学 李英冰树的遍历：按某种次序访问树中的所有结点， 要求每个结点访问一次且仅访问一次。遍历二叉树三方面工作：q访问根结点记作 Dq遍历根的左子树记作 Lq遍历根的右子树记作 R可能的遍历次序有：q前序 DLR 镜像 DRLq中序 LDR 镜像 RDLq后序 LRD 镜像 RLD 二叉树的遍历武汉大学 李英冰n若二叉树非空，则u访问根结点 (D)u前序遍历左子树 (L)u前序遍历右子树 (R)前序遍历二叉树void preorder ( BTNode *t ) if ( t != NULL ) visite (t-data);

8、preorder ( t-lchild ); preorder ( t-rchild ); 前序遍历序列： D L R a b d ec f g武汉大学 李英冰n若二叉树非空，则u中序遍历左子树 (L)u访问根结点 (D)u中序遍历右子树 (R)中序遍历二叉树void inorder ( BTNode *t ) if ( t != NULL ) inorder ( t-lchild ); visite (t-data); inorder ( t-rchild ); 中序遍历序列： L D R ad b ec g f 武汉大学 李英冰n若二叉树非空，则u后序遍历左子树 (L)u后序遍历右子树 (

9、R)u访问根结点 (D)后序遍历二叉树后序遍历序列： L R D ad e bg f cvoid postorder ( BTNode *t ) if ( t != NULL ) postorder ( t-lchild ); postorder ( t-rchild ); visite (t-data); 武汉大学 李英冰前序遍历序列：- + a * b - c d / e f 中序遍历序列：a + b * c - d - e / f 后序遍历序列：a b c d - * + e f / - 应用二叉树遍历的事例表达式：a + b * ( c - d ) - e / f 武汉大学 李英冰基于

10、坐标查询q窗口查询（查询给定时间、区域的所有对象）q邻近查询 q近似查询 基于轨迹查询q拓扑查询（“pass by”, “leave”, “cross”）q导航查询 （移动速度，最高速度）主要方法：P-，R-, T-query212. 轨迹查询武汉大学 李英冰P-query (点与轨迹)22轨迹查询(P-query)bap2p1T cp3Where - Lp-norm (Euclidean space)- shortest network path distance (road network),(min),(spdistTpDTs),(spdist武汉大学 李英冰R-query (区域与轨迹

11、)23轨迹查询(R-query)baT1RbabaT2T3baT1babaT2T3查询在给定区域的轨迹查询给定时间重叠轨迹地区武汉大学 李英冰T-query (轨迹与轨迹)24轨迹查询(T-query)t1T1t2t3t4t5t6t7t8T2t1t2t3t4t1T1t2t3t4t5t6t7t8T2t1t2t3t4Closest pair distanceSum of pair distance武汉大学 李英冰增强R-tree多版本R-tree（分区时间维度） 基于网格索引（空间分区）252. 轨迹数据检索武汉大学 李英冰3D R-tree26增强R-treexTimey武汉大学 李英冰Augm

12、ented 3D R-tree27增强 3D R-treeTB-tree (Trajectory Bundle tree)STR-tree (Spatial-Temporal R-tree)Pfoster 2000 Dieter Pfoster, Christian S. Jensen, Yannis T., Novel approaches to the indexing of moving object trajectories. VLDB, 2000武汉大学 李英冰Multi-version R-tree 28多版本R-treeHR-tree Tao2001For each timest

13、amp, an R-tree is created. So, there are many R-trees. These R-trees are indexed. Query for trajectories in a given region and in a given time interval: 1. The R-tree at the timestamp is found first2. The trajectories in the specified region are retrieved from the R-tree. 武汉大学 李英冰Grid Based Index29基

14、于网格索引Prasad2003 V. Prasad Chakka Adam C. Everspaugh Jignesh M., Patel, Indexing Large Trajectory Data Sets With SETI, CIDR 2003The trajectory segments in each cell are indexed in temporal dimension . Spatial Filtering cells overlap with the query box are retrieved. Temporal Filtering the temporal . Refinement Step