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

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

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

【部分圖文】：

矢量瓦片金字塔模型

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

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

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

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



本文編號(hào)：2965414