Chap42軌跡索引與檢索分析

1、武漢大學(xué)測繪學(xué)院 李英冰YB Li, SGG, Wuhan University4.2 軌跡的索引與檢索Trajectory Indexing and Retrieval3/16/2022武漢大學(xué) 李英冰1. 樹2. 軌跡查詢3. 軌跡數(shù)據(jù)檢索目錄2 (a) Query （t3）= p3 (b) Query （t3）=？武漢大學(xué) 李英冰31.樹軌跡與軌跡存儲(chǔ)Trajectory of moving objects. (a) Trajectory in the real world. (b) Trajectory stored in a database武漢大學(xué) 李英冰路網(wǎng)（軌跡）信息可以轉(zhuǎn)換成

2、樹進(jìn)行存儲(chǔ)4軌跡與樹Structure of the NDTR-Tree. (a) Traffic network. (b) UT-Units submitted in router1.(c) The corresponding NDTR-Tree武漢大學(xué) 李英冰樹(Tree)是n(n=0)個(gè)結(jié)點(diǎn)的有限集T q有且僅有一個(gè)特定根(Root)的結(jié)點(diǎn)；q其余結(jié)點(diǎn)可分為m個(gè)互不相交的子集T1,T2,T3Tm，其中每個(gè)子集又是一棵樹，并稱其為子樹(Subtree)?；靖拍預(yù)CGBDEFKLHMIJ武漢大學(xué) 李英冰1層2層4層3層height= 4ACGBDE FK LHMIJ層次 根為第1層 最大層

3、數(shù)為樹的深度（高度） 雙親 (直接前驅(qū)） 孩子（直接后繼） 兄弟 堂兄弟 子孫 祖先森林-m(m=0)棵互不相交的樹的集合。d=3d=0d=2K LFGMI JABCDEH基本常用術(shù)語度 一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度武漢大學(xué) 李英冰7樹和森林的遍歷先根次序遍歷*訪問根結(jié)點(diǎn)*依次先根遍歷根的各子樹 D T1 T2 T3BEF CG DH IJ先根次序遍歷森林依次先根遍歷各子樹ABCDE FG HIKJACGBDEFHIJACGBDEFHIJK武漢大學(xué) 李英冰dataparent 0 1 2 3 4 5 6雙親表示樹的存儲(chǔ)結(jié)構(gòu)A B C D E F G-1 0 0 0 1 1 3指向其雙親的

4、位置data parent特點(diǎn)：很快確定雙親結(jié)點(diǎn)ACGBDEF武漢大學(xué) 李英冰每個(gè)結(jié)點(diǎn)擁有孩子的個(gè)數(shù)不同，所以采用單鏈表鏈接孩子結(jié)點(diǎn)。9孩子雙親表示法ACGBDEF0123456data headptrABCDEFG123456data parent headprt-1000113typedef struct cnode int child; struct cnode *next;link;typedef struct datatype data; link *headptr;ctree;ctree Tmaxnode;武漢大學(xué) 李英冰LRLR？二叉樹與度為2的樹的區(qū)別度 2 =2 序 有序 無

5、序ABDEFGABCD FE二叉樹 (Binary Tree)武漢大學(xué) 李英冰二叉樹的性質(zhì)性質(zhì)1 在二叉樹的第 i 層最多有 2i-1 個(gè)結(jié)點(diǎn)。(i 1)性質(zhì)2 深度為 k 的二叉樹至多有 2k-1個(gè)結(jié)點(diǎn)。(k 1)性質(zhì)3 對任何一棵二叉樹, 若其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的結(jié)點(diǎn)個(gè)數(shù)為 n2, 則有 n0n21武漢大學(xué) 李英冰深度為k且有2k-1個(gè)結(jié)點(diǎn)，所有分支結(jié)點(diǎn)的度為 2， n1=0 葉子結(jié)點(diǎn)都在最下一層。葉子結(jié)點(diǎn)都在最下兩層，且最下一層集中在最左邊。12 34 5 6 78 9 10 11 12 13 14 15 12 34 5 6 78 9 10 滿二叉樹和完全二叉樹武漢大學(xué) 李英冰

6、12 34 5 6 78 9 10 二叉樹的性質(zhì) 武漢大學(xué) 李英冰由于（性質(zhì)5）完全二叉樹按層次編號后，可確定各結(jié)點(diǎn)與其雙親及孩子的關(guān)系，則完全二叉樹按編號次序進(jìn)行順序表示。完全二叉樹的順序表示二叉樹的存儲(chǔ)結(jié)1 2 3 4 5 6 7 8 9 10結(jié)點(diǎn)5： 雙親是結(jié)點(diǎn) 2 左孩子是結(jié)點(diǎn) 10 沒有右孩子武漢大學(xué) 李英冰一般二叉樹順序表示二叉樹的存儲(chǔ)結(jié)構(gòu)JABCFEDGHI1 2 3 4 5 6 7 8 9 10 11 12 13 14將一般二叉樹轉(zhuǎn)換為完全二叉樹（添加虛結(jié)點(diǎn)），然后按層次編號次序進(jìn)行順序表示。A B C D E F G H I J結(jié)點(diǎn)E（6）： 雙親是

7、結(jié)點(diǎn)C（3） 左孩子是結(jié)點(diǎn) I（12） 沒有右孩子（13為空）武漢大學(xué) 李英冰樹的遍歷：按某種次序訪問樹中的所有結(jié)點(diǎn)， 要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。遍歷二叉樹三方面工作：q訪問根結(jié)點(diǎn)記作 Dq遍歷根的左子樹記作 Lq遍歷根的右子樹記作 R可能的遍歷次序有：q前序 DLR 鏡像 DRLq中序 LDR 鏡像 RDLq后序 LRD 鏡像 RLD 二叉樹的遍歷武漢大學(xué) 李英冰n若二叉樹非空，則u訪問根結(jié)點(diǎn) (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武漢大學(xué) 李英冰n若二叉樹非空，則u中序遍歷左子樹 (L)u訪問根結(jié)點(diǎn) (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 武漢大學(xué) 李英冰n若二叉樹非空，則u后序遍歷左子樹 (L)u后序遍歷右子樹 (

9、R)u訪問根結(jié)點(diǎn) (D)后序遍歷二叉樹后序遍歷序列： L R D ad e bg f cvoid postorder ( BTNode *t ) if ( t != NULL ) postorder ( t-lchild ); postorder ( t-rchild ); visite (t-data); 武漢大學(xué) 李英冰前序遍歷序列：- + a * b - c d / e f 中序遍歷序列：a + b * c - d - e / f 后序遍歷序列：a b c d - * + e f / - 應(yīng)用二叉樹遍歷的事例表達(dá)式：a + b * ( c - d ) - e / f 武漢大學(xué) 李英冰基于

10、坐標(biāo)查詢q窗口查詢（查詢給定時(shí)間、區(qū)域的所有對象）q鄰近查詢 q近似查詢 基于軌跡查詢q拓?fù)洳樵儯ā皃ass by”, “l(fā)eave”, “cross”）q導(dǎo)航查詢 （移動(dòng)速度，最高速度）主要方法：P-，R-, T-query212. 軌跡查詢武漢大學(xué) 李英冰P-query (點(diǎn)與軌跡)22軌跡查詢(P-query)bap2p1T cp3Where - Lp-norm (Euclidean space)- shortest network path distance (road network),(min),(spdistTpDTs),(spdist武漢大學(xué) 李英冰R-query (區(qū)域與軌跡

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

12、ented 3D R-tree27增強(qiáng) 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武漢大學(xué) 李英冰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. 武漢大學(xué) 李英冰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