針對矢量瓦片在構(gòu)建過程中對原始矢量數(shù)據(jù)源檢索性能的不足,提出了一種基于改進網(wǎng)格與遞歸網(wǎng)格排序（sort-tile-recursive,STR）R-樹的混合索引結(jié)構(gòu),用于提升對數(shù)據(jù)源的空間查詢效率。該混合索引通過瓦片金字塔上下文信息改進了一級網(wǎng)格索引的查詢方式,減少了查詢過程中的空間比較。同時,使用STR R-樹作為二級索引,有效減輕了因矢量數(shù)據(jù)空間分布不均衡所帶來的影響,實現(xiàn)了二級查詢優(yōu)化。實驗表明,對比數(shù)據(jù)庫常用空間索引（如網(wǎng)格索引、四叉樹索引、R-樹/R*樹索引）,該混合索引對不同空間分布的矢量數(shù)據(jù)適應(yīng)良好,能顯著提高對矢量數(shù)據(jù)源的查詢性能,加速瓦片的構(gòu)建。 

【文章來源】：武漢大學(xué)學(xué)報(信息科學(xué)版). 2020,45(10)北大核心

【文章頁數(shù)】：9 頁

【部分圖文】：

矢量瓦片金字塔模型

對于線、多邊形等數(shù)據(jù)，需基于幾何體最小外包矩形的左上角與右下角點利用式（4）計算兩點對應(yīng)的網(wǎng)格坐標，分別為T1(tx1,ty1)和T2(tx2,ty2)，取所有與外包矩形重疊的網(wǎng)格T (tx,ty):tx1≤tx≤tx2且ty1≤ty≤ty2且tx,ty∈Z，并冗余存儲該空間對象。對網(wǎng)格索引的范圍查詢與非單點數(shù)據(jù)的存儲過程相似，可根據(jù)上述規(guī)則實現(xiàn)快速定位。然而，由于普通網(wǎng)格索引的劃分規(guī)則與金字塔劃分規(guī)則不同，如圖2所示，在瓦片范圍查詢時，查詢矩形無法與網(wǎng)格索引相適應(yīng)，易產(chǎn)生多路查詢。此外，由于矢量數(shù)據(jù)空間分布不均衡，網(wǎng)格索引中各存儲單元的負載亦會發(fā)生嚴重傾斜。若以細粒度劃分網(wǎng)格以解決傾斜問題，將會導(dǎo)致數(shù)據(jù)的過度冗余，增加內(nèi)存壓力[18]。綜上所述，為減少多路查詢和二級過濾時的數(shù)據(jù)量，依據(jù)金字塔劃分方式對網(wǎng)格索引進行劃分，以適應(yīng)矢量瓦片的范圍查詢。同時，為顧及矢量數(shù)據(jù)多樣的空間分布特征，以二級索引優(yōu)化網(wǎng)格結(jié)構(gòu)，加速二級檢索。

其中，網(wǎng)格索引的劃分將依據(jù)預(yù)先設(shè)定的冗余度值與矢量瓦片金字塔上下文唯一確定。由于矢量瓦片金字塔中每一層級劃分粒度的不同，對于同一份矢量數(shù)據(jù)，依據(jù)金字塔每一層級構(gòu)建的網(wǎng)格索引冗余度也不盡相同。確定適宜冗余度大小的網(wǎng)格索引劃分是改進網(wǎng)格索引構(gòu)建的關(guān)鍵。如圖1所示，假設(shè)以金字塔第二層級作為基準層級構(gòu)建網(wǎng)格索引，以該層級表示的空間范圍作為網(wǎng)格索引的四至范圍，以瓦片表示的實際尺寸作為網(wǎng)格單元的大小。基準層級的確定可通過二分法實現(xiàn)，首先依據(jù)矢量數(shù)據(jù)的空間形態(tài)初步確定初始層級，再依據(jù)冗余度判定，最終確定最接近預(yù)設(shè)經(jīng)驗冗余度值的層級為基準層級。如圖4所示，混合索引的二級結(jié)構(gòu)以單鏈表或STR R-樹實現(xiàn)。單鏈表是以單向指針相連的常用數(shù)據(jù)結(jié)構(gòu)，擁有較高的空間利用率，但在范圍搜索時需通過線性搜索遍歷所有對象。STR R-樹是對R-樹打包方式的改進，其通過對靜態(tài)有界的多維數(shù)據(jù)進行良好的空間劃分形成高度平衡的R-樹，從而增強空間范圍查詢的性能[21]。通常情況下，STR R-樹在檢索時的時間復(fù)雜度為對數(shù)時間，但由于節(jié)點間的區(qū)域重疊，其真正的時間復(fù)雜度將介于對數(shù)時間與線性時間之間。基于對數(shù)時間復(fù)雜度與線性時間復(fù)雜度的變化特點，當索引的數(shù)據(jù)量較小時，STR R-樹無法發(fā)揮其優(yōu)勢，故在二級組織結(jié)構(gòu)選擇時將以網(wǎng)格單元中存儲的數(shù)據(jù)量進行評估，若數(shù)據(jù)量大于預(yù)設(shè)的經(jīng)驗閾值，則構(gòu)建二級STR R-樹索引，否則仍以鏈表結(jié)構(gòu)存儲。如圖3(b）所示，設(shè)定閾值為10，那么網(wǎng)格索引結(jié)構(gòu)中G1、G4網(wǎng)格將構(gòu)建STR R-樹二級索引，而網(wǎng)格G2、G3則不進行構(gòu)建。

【參考文獻】：
期刊論文
[1]顧及要素空間分布特征的稠疏矢量瓦片構(gòu)建方法研究[J]. 朱笑笑,張豐,杜震洪,劉仁義,余華芬.  浙江大學(xué)學(xué)報(理學(xué)版). 2017(05)
[2]網(wǎng)絡(luò)環(huán)境下矢量數(shù)據(jù)高效并行可視化方法[J]. 郭明強,黃穎,吳亮,謝忠.  武漢大學(xué)學(xué)報(信息科學(xué)版). 2014(11)
[3]基于Hilbert曲線的STR索引改進算法[J]. 戴晶,吳明光,鄭培蓓,王蕾,崔登吉,陳泰生.  武漢大學(xué)學(xué)報(信息科學(xué)版). 2014(07)
[4]一種面向服務(wù)器制圖可視化的矢量數(shù)據(jù)多尺度組織方法[J]. 孫璐,陳犖,劉露,蘇德國.  計算機工程與科學(xué). 2014(02)
[5]矢量數(shù)據(jù)多尺度空間索引方法的研究[J]. 程昌秀.  武漢大學(xué)學(xué)報(信息科學(xué)版). 2009(05)
[6]對空間數(shù)據(jù)多尺度表達有關(guān)問題的思考[J]. 艾廷華,成建國.  武漢大學(xué)學(xué)報(信息科學(xué)版). 2005(05)
[7]從數(shù)字地圖到空間信息網(wǎng)格——空間信息多級網(wǎng)格理論思考[J]. 李德仁,朱欣焰,龔健雅.  武漢大學(xué)學(xué)報(信息科學(xué)版). 2003(06)
[8]矢量和柵格一體化的數(shù)據(jù)模型[J]. 楊樹強,陳火旺,王峰.  軟件學(xué)報. 1998(02)

碩士論文
[1]分布式矢量瓦片生產(chǎn)與訪問系統(tǒng)的設(shè)計與實現(xiàn)[D]. 王梅欣.西安電子科技大學(xué) 2016



本文編號：2965414