一種采用Hilbert空間排列碼的場(chǎng)景數(shù)據(jù)調(diào)度策略

孫立偉，袁昱緯，周俊芳

(1.中國(guó)人民解放軍91977部隊(duì)，北京 102249；2.中國(guó)人民解放軍92999部隊(duì)，北京 102400)

0 引言

場(chǎng)景數(shù)據(jù)的調(diào)度策略是實(shí)現(xiàn)大規(guī)模場(chǎng)景數(shù)據(jù)的存儲(chǔ)管理[1]、處理[2]、瀏覽顯示[3]和分發(fā)[4]應(yīng)用[5]的基礎(chǔ)，對(duì)于數(shù)字地球等[6]應(yīng)用性能也起著決定性的作用。隨著場(chǎng)景數(shù)據(jù)量以幾何級(jí)數(shù)增長(zhǎng)，數(shù)據(jù)規(guī)模越來(lái)越大，給場(chǎng)景數(shù)據(jù)的組織調(diào)度效率帶來(lái)了極大的考驗(yàn)[7]。目前，許多學(xué)者對(duì)數(shù)據(jù)調(diào)度算法進(jìn)行了研究?；粑√岢隽艘环N基于層次金字塔結(jié)構(gòu)和四叉樹(shù)索引結(jié)構(gòu)相結(jié)合的數(shù)據(jù)組織調(diào)度方法，僅僅在內(nèi)存中存儲(chǔ)了索引結(jié)構(gòu)，提高了檢索效率，但是數(shù)據(jù)冗余嚴(yán)重[8]。劉恒飛則設(shè)計(jì)了一種基于四叉樹(shù)索引結(jié)構(gòu)與網(wǎng)格劃分的數(shù)據(jù)調(diào)度方法，減少了數(shù)據(jù)重復(fù)存儲(chǔ)，提高檢索效率[9]。吳穎等人則利用四叉樹(shù)分割的思想，實(shí)現(xiàn)對(duì)大規(guī)模場(chǎng)景數(shù)據(jù)的裁剪，提升場(chǎng)景的繪制效率，減少了內(nèi)存占有率[10]。通過(guò)對(duì)傳統(tǒng)四叉樹(shù)索引技術(shù)[11]應(yīng)用到海量場(chǎng)景數(shù)據(jù)調(diào)度進(jìn)行研究，可知數(shù)據(jù)調(diào)度的研究主要集中在數(shù)據(jù)存儲(chǔ)、層次劃分以及空間索引等方面，因此本文研究并提出了一種采用Hilbert空間排列碼的大規(guī)模場(chǎng)景數(shù)據(jù)調(diào)度策略，利用空間排序碼的空間聚集特性，將海量高維數(shù)據(jù)向低維空間靠近，同時(shí)通過(guò)最近鄰算法提高相鄰空間數(shù)據(jù)連續(xù)存儲(chǔ)的概率，優(yōu)化場(chǎng)景數(shù)據(jù)存儲(chǔ)管理，提高數(shù)據(jù)調(diào)度效率。

1 Hilbert空間排列碼

Hilbert曲線(xiàn)[12]于1891年提出，源自Peano曲線(xiàn)簇。采用Hilbert曲線(xiàn)可以建立二維甚至多維空間向一維線(xiàn)性空間的一一映射關(guān)系，這個(gè)一維線(xiàn)性空間的映射序列稱(chēng)為Hilbert空間排列碼。Hilbert空間排列碼具有優(yōu)良的空間聚集性能[13-14]，可以使二維或多維空間中相鄰的元素在轉(zhuǎn)換的一維線(xiàn)性序列中盡量相鄰。

吳明光等[15]將Hilbert曲線(xiàn)引入數(shù)據(jù)集劃分問(wèn)題，提高數(shù)據(jù)空間分布的均衡性，吳晨等[16]等將Hilbert曲線(xiàn)引入HBase遙感影像檢索中，提高了影像數(shù)據(jù)的檢索效率。楊明遠(yuǎn)[17]等將Hilbert曲線(xiàn)引入數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)優(yōu)化中，較大幅度地增強(qiáng)了算法的空間范圍查詢(xún)效率。

本文考慮在對(duì)三維場(chǎng)景數(shù)據(jù)集的管理中，對(duì)于瓦片狀分布的空間實(shí)體[18-19]，引入Hilbert曲線(xiàn)及Hilbert空間排列碼，利用其空間聚集性能，優(yōu)化場(chǎng)景數(shù)據(jù)管理策略，增加空間中相鄰的場(chǎng)景數(shù)據(jù)在存儲(chǔ)時(shí)同樣連續(xù)的概率，使場(chǎng)景數(shù)據(jù)處理時(shí)磁盤(pán)盡量連續(xù)讀取，提高數(shù)據(jù)調(diào)度的效率。

2 基于Hilbert空間排列碼的數(shù)據(jù)調(diào)度策略

本文采用一種高效的Hilbert空間排列碼最近鄰查詢(xún)方法，有效地規(guī)避Hilbert在臨域查詢(xún)時(shí)計(jì)算復(fù)雜的弊端，同時(shí)利用Hilbert空間排列碼良好的空間聚集性能，提高數(shù)據(jù)管理時(shí)的搜索和調(diào)度效率，具體算法描述如下：

(1)三維場(chǎng)景數(shù)據(jù)集的預(yù)處理

遍歷三維場(chǎng)景所有區(qū)域，將場(chǎng)景劃分為N×N個(gè)地形分塊，并構(gòu)建金字塔模型的層次結(jié)構(gòu)；在邏輯層面上，一般采用四叉樹(shù)對(duì)金字塔模型的層次結(jié)構(gòu)進(jìn)行組織和管理。

(2)專(zhuān)用數(shù)據(jù)集的Hilbert排列

該金字塔模型的每個(gè)層級(jí)中，每個(gè)地形分塊采用Hilbert空間排列碼的順序編碼，并按照該編碼順序進(jìn)行存儲(chǔ)和管理。

由地形分塊的格網(wǎng)編碼轉(zhuǎn)化為Hilbert空間排列碼的方法如下：

① 將索引地形分塊格網(wǎng)的行列數(shù)采用二進(jìn)制位交叉方法轉(zhuǎn)化為對(duì)應(yīng)的Morton碼；

② 將Morton碼轉(zhuǎn)化為二進(jìn)制，以?xún)晌粸橐粋€(gè)單位，由高位開(kāi)始，對(duì)生成的Morton碼中的10和11互換；

③ 由高位開(kāi)始，設(shè)為ti，對(duì)后續(xù)各位中的10和00進(jìn)行互換；

④ 將結(jié)果按順序排列，即為Hilbert空間排列碼。按照Hilbert空間排列碼的順序練成曲線(xiàn)如圖1所示，高階的Hilbert空間排列碼可由圖1遞歸產(chǎn)生。

圖1 Hilbert空間排列碼示意

(3)計(jì)算視場(chǎng)區(qū)域格網(wǎng)坐標(biāo)范圍

首先將視點(diǎn)F處的經(jīng)緯度換算為格網(wǎng)坐標(biāo)。然后為減少浮點(diǎn)運(yùn)算，提高數(shù)據(jù)讀取效率，視場(chǎng)區(qū)域內(nèi)的其他格網(wǎng)坐標(biāo)，不再采用經(jīng)緯度進(jìn)行換算，而采用格網(wǎng)坐標(biāo)累加的方法得到，直至遇到邊緣的角點(diǎn)，如圖2所示。

假設(shè)視點(diǎn)F處的格網(wǎng)坐標(biāo)為(x，y)，圖2中的深灰區(qū)域?yàn)橐朁c(diǎn)F處可見(jiàn)的視野范圍，并為其進(jìn)行分塊，每個(gè)分塊大小的邊長(zhǎng)為a。視野范圍中右側(cè)矩形區(qū)域左上角格網(wǎng)坐標(biāo)為(x+[V/a]，y+[w/2/a])，右下角格網(wǎng)坐標(biāo)為(w+{V+L}/a，y-{w/2/a})，(其中，[]表示向上取整，{ }表示向下取整)，視野范圍中左側(cè)三角形所在的格網(wǎng)坐標(biāo)則由矩形區(qū)域左上角、左下角和視點(diǎn)區(qū)域坐標(biāo)推出。

圖2 視野區(qū)域格網(wǎng)坐標(biāo)范圍示意

(4)采取基于視點(diǎn)擴(kuò)散的讀取思路，提取視場(chǎng)范圍內(nèi)的地形分塊數(shù)據(jù)

得到視野區(qū)域所需地形分塊的格網(wǎng)坐標(biāo)后，按照(2)中的方法計(jì)算視點(diǎn)F的Hilbert編碼；然后以F點(diǎn)的Hilbert為起點(diǎn)，按照視點(diǎn)方向，進(jìn)行臨域搜索，搜索范圍限定在(3)得到的格網(wǎng)范圍內(nèi)，將該范圍完全遍歷。

(5)按照Hilbert空間排列碼順序讀取和處理

在上一步的臨域搜索和遍歷的同時(shí)，對(duì)于每搜索一個(gè)分塊格網(wǎng)將其讀取，供處理和顯示使用。讀取時(shí)，按照首地址+偏移地址的方式進(jìn)行，偏移地址=(本影像塊編碼-首影像塊編碼)×每個(gè)影像塊所占用的磁盤(pán)空間。

采用本算法對(duì)空間數(shù)據(jù)進(jìn)行管理和調(diào)度，使后續(xù)進(jìn)行的空間數(shù)據(jù)調(diào)度效率得到了很大的提高。例如，按照空間范圍進(jìn)行查詢(xún)時(shí)，通過(guò)查詢(xún)區(qū)域內(nèi)的格網(wǎng)范圍，得到對(duì)應(yīng)的Hilbert空間排列碼，以此計(jì)算偏移地址進(jìn)行提取，可以較大地減少重新計(jì)算地址的計(jì)算量，減少空間索引量，提高數(shù)據(jù)調(diào)度的性能。此外，由于Hilbert空間排列碼優(yōu)秀的線(xiàn)性映射特性，空間數(shù)據(jù)按照該順序存儲(chǔ)后，空間中相鄰的地形分塊在線(xiàn)性存儲(chǔ)上也是盡量相鄰存儲(chǔ)的，從而減少了磁盤(pán)的訪(fǎng)問(wèn)時(shí)間，提高了數(shù)據(jù)處理效率。

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)采用的硬件環(huán)境為Intel Xeon? CPU E3-1271 V3 3.60 GHz，8 GB內(nèi)存，NVIDIA Quadro K2200顯卡，軟件環(huán)境為Windows7，VS2010。實(shí)驗(yàn)素材選取了6組場(chǎng)景數(shù)據(jù)，其大小分別為6.65，20.63，72.10，257.93，889.28，5 602.91 MB，分塊數(shù)量分別為128，512，2 048，8 192，32 768，131 072。

3.1 基于Hilbert空間排列碼的三維場(chǎng)景數(shù)據(jù)集構(gòu)建測(cè)試

對(duì)6組場(chǎng)景數(shù)據(jù)分別采用將經(jīng)典四叉樹(shù)編碼索引算法和本文提出算法構(gòu)建數(shù)據(jù)集，并對(duì)比2種方法在構(gòu)建時(shí)的耗時(shí)。實(shí)驗(yàn)分別記錄經(jīng)典四叉樹(shù)編碼索引算法和本文提出算法構(gòu)建數(shù)據(jù)集的時(shí)間開(kāi)銷(xiāo)，每組場(chǎng)景數(shù)據(jù)各測(cè)試5次，并計(jì)算平均值。經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果如表1所示。

表1 構(gòu)建結(jié)構(gòu)耗時(shí)的測(cè)試結(jié)果

數(shù)據(jù)量大小/MB分塊數(shù)量傳統(tǒng)方法構(gòu)建耗時(shí)/s本文方法構(gòu)建耗時(shí)/s6.6471280.466 90.468 820.6315122.120 62.294 972.7032 0489.620 910.032 4256.9568 19287.97591.741 9879.38232 768434.125482.0875 620.119131 0722 942.4813 140.316

從實(shí)驗(yàn)結(jié)果可以看出，本文方法與傳統(tǒng)方法在進(jìn)行三維場(chǎng)景數(shù)據(jù)集構(gòu)建的耗時(shí)相當(dāng)。由于四叉樹(shù)構(gòu)建的時(shí)間復(fù)雜度一般為O(nlogn)，與本文算法的時(shí)間復(fù)雜度相當(dāng)，其中，n為層次結(jié)構(gòu)中最底層分塊數(shù)量。本文方法略多的耗時(shí)主要發(fā)生在Hilbert排列碼的計(jì)算上。

3.2 場(chǎng)景數(shù)據(jù)隨機(jī)讀取測(cè)試

將6組實(shí)驗(yàn)場(chǎng)景數(shù)據(jù)在金字塔模型的層次結(jié)構(gòu)中進(jìn)行分級(jí)、分塊后，得到層級(jí)數(shù)分別為5～10層，實(shí)驗(yàn)時(shí)分別采用本文提出方法(Hilbert空間排列碼順序)和四叉樹(shù)結(jié)構(gòu)(在各層級(jí)中按照先行后列、從左到右的順序)方式進(jìn)行測(cè)試。實(shí)驗(yàn)時(shí)，隨機(jī)指定行列號(hào)，讀取并顯示以該位置為中心的10×10個(gè)地形分塊，記錄使用上述方法在索引和讀取上的時(shí)間開(kāi)銷(xiāo)。每組實(shí)驗(yàn)場(chǎng)景分別進(jìn)行5次測(cè)試，并計(jì)算平均值，如表2所示。

表2 場(chǎng)景數(shù)據(jù)隨機(jī)讀取耗時(shí)的測(cè)試結(jié)果

層級(jí)數(shù)四叉樹(shù)qrst編碼索引檢索耗時(shí)/msHilbert空間排列碼順序及檢索耗時(shí)/ms5830.27425.376991.30561.7471 297.70569.3881 620.76559.5291 893.53610.24102 219.80665.37

由表2中的實(shí)驗(yàn)數(shù)據(jù)可知，本文提出的方法(Hilbert空間排列碼順序)與傳統(tǒng)方法的四叉樹(shù)結(jié)構(gòu)(先行后列、從左到右的順序)相比，隨機(jī)讀取效率明顯提高。本文算法在數(shù)據(jù)讀取時(shí)的時(shí)間復(fù)雜度為O(nlogn)，比經(jīng)典四叉樹(shù)算法的O(n)略多，其中n為層級(jí)數(shù)；但由于本文方法利用了Hilbert空間排列碼的特性，瀏覽三維場(chǎng)景時(shí)讀取的場(chǎng)景分塊一般為連續(xù)的，Hilbert空間排列碼在組織數(shù)據(jù)時(shí)，空間上相鄰的分塊在磁盤(pán)存儲(chǔ)時(shí)相鄰的概率較經(jīng)典四叉樹(shù)方法大很多，大部分的讀取能夠連續(xù)進(jìn)行，減少了磁盤(pán)尋址時(shí)的開(kāi)銷(xiāo)，縮短影像塊的讀取時(shí)間。

4 結(jié)束語(yǔ)

針對(duì)三維場(chǎng)景實(shí)時(shí)性瀏覽中的數(shù)據(jù)調(diào)度問(wèn)題，本文研究了一種采用Hilbert空間排列碼的三維場(chǎng)景數(shù)據(jù)調(diào)度策略，通過(guò)Hilbert空間排列碼生成方法構(gòu)建數(shù)據(jù)集，以提高數(shù)據(jù)管理時(shí)的搜索和讀取效率。試驗(yàn)表明，與基于傳統(tǒng)四叉樹(shù)的調(diào)度策略相比，在構(gòu)建時(shí)間相當(dāng)?shù)幕A(chǔ)上，本文方法的隨機(jī)讀取時(shí)間明顯減少，具有更高的場(chǎng)景數(shù)據(jù)調(diào)度效率。