第十章基于空間目標(biāo)排序的索引方法

1、物聯(lián)網(wǎng)1302基于空間目標(biāo)的排 序 方 法主 講 人封華封華策劃徐云筱徐云筱 閆冬閆冬 蘭天翔蘭天翔目錄C o n t e n t2.Z-排序3.Hilbert曲線4.位置鍵1.緒論5.總結(jié)與展望關(guān)鍵問題關(guān)鍵問題緒論基本思想基本思想PART ONE第一部分幾種可能填充方法幾種可能填充方法Main idea and key problem 基本思想：基本思想：索引空間?多維空間目標(biāo)?關(guān)鍵問題：關(guān)鍵問題：保持目標(biāo)間臨近關(guān)系?某種策略若干網(wǎng)格分配編號轉(zhuǎn)換數(shù)字映射一維空間目標(biāo)Row-wise or Snake-curve?橫向填充 蛇形曲線缺點缺點跨度太大跨度太大空間填充曲線：一條連續(xù)曲線遍歷空間所有

2、網(wǎng)格空間填充曲線：一條連續(xù)曲線遍歷空間所有網(wǎng)格Z-排序值Z-排序與四叉樹Z-Z-排序排序基本思想PART TWO第二部分z-ordering基本思想：基本思想：基于空間填充曲線，將數(shù)據(jù)空間循環(huán)分解到更小子空間。?排序示例排序示例?order-1 order-2 . order (n+1) Z-valueZ-ordering and Linear quad trees?如何將Z-排序與四叉樹對應(yīng)起來？?, 1, 2, 3 011), 01, 10, (00 W,E,N,S West,East,North,South:0101W E N SZ-ordering and Linear quad tr

3、ees. and repeat recursivelyzgray-cell =WN;WN= (0101)25=0101W E N S0011Z排序的缺點？排序的缺點？實現(xiàn)方法實現(xiàn)方法與與Z-Z-排序比較排序比較HilbertHilbert曲線曲線基本思想基本思想PART THREE第三部分Hilbert Curve?與Z-排序類似，也是一種空間填充曲線 1st order 2st order 3st order enum UP, LEFT, DOWN, RIGHT,;void hilbert(int level,int direction=UP) if (level=1) switch (di

4、rection) case LEFT: move(RIGHT); /* move() could draw a line in. */ move(DOWN); /* .the indicated direction */ move(LEFT); break; case RIGHT: move(LEFT); move(UP); move(RIGHT); break; case UP: move(DOWN); move(RIGHT); move(UP); break; case DOWN: move(UP); move(LEFT); move(DOWN); break; /* switch */

5、else switch (direction) . case DOWN: hilbert(level-1,RIGHT); move(UP); hilbert(level-1,DOWN); move(LEFT); hilbert(level-1,DOWN); move(DOWN); hilbert(level-1,LEFT); break; /* switch */ /* if */z-ordering&Hilbert - analysis 如何衡量空間填充曲線的優(yōu)劣？分配策略分配策略位置鍵位置鍵基本思想基本思想PART FOUR第四部分優(yōu)缺點優(yōu)缺點使用四叉樹將數(shù)據(jù)空間遞歸分解為四個大小

6、相等子空間（SW，NW，SE，NE）?某一子空間位置鍵k可由上級子空間k得到，公式如下：?每一個子空間與一個唯一五進制數(shù)值關(guān)聯(lián)，稱為位置鍵?Main ideam:空間分解最大層次數(shù)h:當(dāng)前層次數(shù)z-ordering?m:空間分解最大層次數(shù)h:當(dāng)前層次數(shù)Advantages&Disadvantages?優(yōu)點：利于空間目標(biāo)屬性信息與幾何空間信息緊密結(jié)合 缺點：表示象限往往大于目標(biāo)包圍矩形，精確度差 目標(biāo)標(biāo)識重復(fù)存儲，需額外開銷 查詢區(qū)域與各級子空間相交，查詢效率低 拓展到多維索引困難且效率低 展望展望總結(jié)與展望總結(jié)與展望結(jié)論結(jié)論PART FIVE第五部分主要結(jié)論與展望主要結(jié)論與展望 基于空間目標(biāo)排序的索引方法將多維空間目標(biāo)映射為一維空間目標(biāo)。 如今一維索引技術(shù)已比較成熟，可實現(xiàn)快速存取和索引，但是經(jīng)過映射后，空間目標(biāo)的空間關(guān)系往往會丟棄，導(dǎo)致高維空間接近的對象在一維排序序列未必相互接近，從而影響空間查詢的效率與準(zhǔn)確性。In thefuture目前的空間索引研究較多的局限于二維、三維空間對象,而對高維空間索引技術(shù)研究比較少。隨