Chap4-2 轨迹索引与检索

1、武汉大学测绘学院 李英冰 YB Li, SGG, Wuhan University 4.2 轨迹的索引与检索 Trajectory Indexing and Retrieval 7/13/2021 武汉大学 李英冰 1. 树 2. 轨迹查询 3. 轨迹数据检索 目录 2 (a) Query （t3）= p3 (b) Query （t3）=？ 武汉大学 李英冰3 1.树 轨迹与轨迹存储 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)。 基本概念 A C G BD EF KL H M IJ 武汉大学 李英冰 1层 2层 4层

3、3层 height = 4 A C G BD E F K L H M IJ 层次 根为第1层 最大层数为树的深度（高度） 双亲 (直接前驱） 孩子（直接后继） 兄弟 堂兄弟 子孙 祖先 森林-m(m=0)棵互不相交的树的集合。 d=3 d=0 d=2 K L FG M I J A BCD EH 基本常用术语 度 一个结点的子树的个数称为该结点的度 武汉大学 李英冰7 树和森林的遍历 先根次序遍历 *访问根结点 *依次先根遍历根的各子树 D T1 T2 T3 BEF CG DH IJ 先根次序遍历森林 依次先根遍历各子树 ABCDE FG HIKJ A C G BD EFHIJ A CGBD E

4、 FH IJ K 武汉大学 李英冰 data parent 0 1 2 3 4 5 6 双亲表示 树的存储结构 A B C D E F G -1 0 0 0 1 1 3 指向其双亲的位置 data parent 特点：很快确定双亲结点 A C G B D EF 武汉大学 李英冰 每个结点拥有孩子的个数不同， 所以采用单链表链接孩子结点。 9 孩子双亲表示法 A C G B D EF 0 1 2 3 4 5 6 data headptr A B C D E F G 123 45 6 data parent headprt -1 0 0 0 1 1 3 typedef struct cnode i

5、nt child; struct cnode *next; link; typedef struct datatype data; link *headptr; ctree; ctree Tmaxnode; 武汉大学 李英冰 LRLR ？二叉树与度为2的树的区别 度 2 =2 序 有序 无序 A BD EFG A B CD F E 二叉树 (Binary Tree) 武汉大学 李英冰 二叉树的性质 性质1 在二叉树的第 i 层最多有 2i-1 个结点。(i 1) 性质2 深度为 k 的二叉树至多有 2k-1个结点。(k 1) 性质3 对任何一棵二叉树, 若其叶结点个数为 n0, 度为2的结点个

6、数为 n2, 则有 n0n21 武汉大学 李英冰 深度为k且有2k-1个结点， 所有分支结点的度为 2， n1=0 叶子结点都在最下一层。 叶子结点都在最下两层， 且最下一层集中在最左边。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 满二叉树和完全二叉树 武汉大学 李英冰 1 2 3 4 5 6 7 8 9 10 二叉树的性质 武汉大学 李英冰 由于（性质5）完全二叉树按层 次编号后，可确定各结点与其双 亲及孩子的关系，则完全二叉树 按编号次序进行顺序表示。 完全二叉树的顺序表示 二叉树的存储结构 1 89 4 5 6 23

7、 7 10 1 2 3 4 5 6 7 8 9 10 结点5： 双亲是结点 2 左孩子是结点 10 没有右孩子 武汉大学 李英冰 一般二叉树顺序表示 二叉树的存储结构 J A BC FED GHI 1 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）： 双亲是结点C（3） 左孩子是结点 I（12） 没有右孩子（13为空） 武汉大学 李英冰 树的遍历：按某种次序访问树中的所有结点， 要求每个 结点访问一次且仅访问一次。 遍历二叉树三方面工作： q访问

8、根结点记作 D q遍历根的左子树记作 L q遍历根的右子树记作 R 可能的遍历次序有： q前序 DLR 镜像 DRL q中序 LDR 镜像 RDL q后序 LRD 镜像 RLD 二叉树的遍历 武汉大学 李英冰 n若二叉树非空，则 u访问根结点 (D) u前序遍历左子树 (L) u前序遍历右子树 (R) 前序遍历二叉树 void preorder ( BTNode *t ) if ( t != NULL ) visite (t-data); preorder ( t-lchild ); preorder ( t-rchild ); 前序遍历序列： D L R a b d ec f g 武汉大学

9、李英冰 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后序遍历右子树 (R) u访问根结点 (D) 后序遍历二叉树 后序遍历序列： L R D a d e b g f c void postorder ( B

10、TNode *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 武汉大学 李英冰 基于坐标查询 q窗口查询（查询给定时间、区域的所有对象） q邻近查询 q近似查询 基于轨迹查询 q拓扑查询（“pass b

11、y”, “leave”, “cross”） q导航查询 （移动速度，最高速度） 主要方法：P-，R-, T-query 21 2. 轨迹查询 武汉大学 李英冰 P-query (点与轨迹) 22 轨迹查询(P-query) b a p2 p1 T c p3 Where - Lp-norm (Euclidean space) - shortest network path distance (road network) ),(min),(spdistTpD Ts ),(spdist 武汉大学 李英冰 R-query (区域与轨迹) 23 轨迹查询(R-query) b aT1 R b a b a

12、 T2 T3 b aT1 b a b a T2 T3 查询在给定区域的轨迹 查询给定时间重叠轨迹地区 武汉大学 李英冰 T-query (轨迹与轨迹) 24 轨迹查询(T-query) t1 T1 t2 t3 t4 t5t6 t7 t8 T2 t1 t2 t3 t4 t1 T1 t2 t3 t4 t5t6 t7 t8 T2 t1 t2 t3 t4 Closest pair distance Sum of pair distance 武汉大学 李英冰 增强R-tree 多版本R-tree（分区时间维度） 基于网格索引（空间分区） 25 2. 轨迹数据检索 武汉大学 李英冰 3D R-tree 2

13、6 增强R-tree x Time y 武汉大学 李英冰 Augmented 3D R-tree 27 增强 3D R-tree TB-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

14、 多版本R-tree HR-tree Tao2001 For each timestamp, 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 first 2. The trajectories in the specified region are retrieved f

15、rom the R-tree. 武汉大学 李英冰 Grid Based Index 29 基于网格索引 Prasad2003 V. Prasad Chakka Adam C. Everspaugh Jignesh M., Patel, Indexing Large Trajectory Data Sets With SETI, CIDR 2003 The 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 . Duplicate Elimin