Chap4-2 軌跡索引與檢索

1、武漢大學測繪學院 李英冰YB Li, SGG, Wuhan University4.2 軌跡的索引與檢索Trajectory Indexing and Retrieval3/25/2022武漢大學 李英冰1. 樹2. 軌跡查詢3. 軌跡數(shù)據(jù)檢索目錄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武漢大學 李英冰路網(wǎng)（軌跡）信息可以轉(zhuǎn)換成

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)?；靖拍預CGBDEFKLHMIJ武漢大學 李英冰1層2層4層3層height= 4ACGBDE FK LHMIJ層次 根為第1層 最大層

3、數(shù)為樹的深度（高度） 雙親 (直接前驅(qū)） 孩子（直接后繼） 兄弟 堂兄弟 子孫 祖先森林-m(m=0)棵互不相交的樹的集合。d=3d=0d=2K LFGMI JABCDEH基本常用術語度 一個結點的子樹的個數(shù)稱為該結點的度武漢大學 李英冰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武漢大學 李英冰每個結點擁有孩子的個數(shù)不同，所以采用單鏈表鏈接孩子結點。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的樹的區(qū)別度 2 =2 序 有序 無

5、序ABDEFGABCD FE二叉樹 (Binary Tree)武漢大學 李英冰二叉樹的性質(zhì)性質(zhì)1 在二叉樹的第 i 層最多有 2i-1 個結點。(i 1)性質(zhì)2 深度為 k 的二叉樹至多有 2k-1個結點。(k 1)性質(zhì)3 對任何一棵二叉樹, 若其葉結點個數(shù)為 n0, 度為2的結點個數(shù)為 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 二叉樹的性質(zhì) 武漢大學 李英冰由于（性質(zhì)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將一般二叉樹轉(zhuǎn)換為完全二叉樹（添加虛結點），然后按層次編號次序進行順序表示。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近似查詢 基于軌跡查詢q拓撲查詢（“pass by”, “l(fā)eave”, “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 (區(qū)域與軌跡

11、)23軌跡查詢(R-query)baT1RbabaT2T3baT1babaT2T3查詢在給定區(qū)域的軌跡查詢給定時間重疊軌跡地區(qū)武漢大學 李英冰T-query (軌跡與軌跡)24軌跡查詢(T-query)t1T1t2t3t4t5t6t7t8T2t1t2t3t4t1T1t2t3t4t5t6t7t8T2t1t2t3t4Closest pair distanceSum of pair distance武漢大學 李英冰增強R-tree多版本R-tree（分區(qū)時間維度） 基于網(wǎng)格索引（空間分區(qū)）252. 軌跡數(shù)據(jù)檢索武漢大學 李英冰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、于網(wǎng)格索引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