基于分區(qū)技術(shù)的靜態(tài) R 樹索引并行計(jì)算技術(shù)

R 樹索引性能優(yōu)良，被廣泛用于原型研究和商用空間數(shù)據(jù)庫(kù)系統(tǒng)，它是目前最流行、最成功的多維索引結(jié)構(gòu)之一[1]。但在海量空間數(shù)據(jù)的管理過(guò)程中，存在 R 樹構(gòu)建時(shí)耗過(guò)大、數(shù)據(jù)更新效率低、全局索引維護(hù)困難等問(wèn)題。因此，本文針對(duì)靜態(tài) R 樹加載過(guò)程良好的可并行性，采用并行計(jì)算技術(shù)并行化 R 樹的構(gòu)建過(guò)程，以提高索引構(gòu)建效率。利用大型商用數(shù)據(jù)庫(kù)分區(qū)技術(shù)管理海量空間數(shù)據(jù)，在邏輯上保證數(shù)據(jù)的無(wú)縫存儲(chǔ)，確保查詢效率并從物理層次上提高海量空間數(shù)據(jù)及其索引的可管理性、可用性和性能。

1 分區(qū)技術(shù)在空間數(shù)據(jù)庫(kù)引擎中的應(yīng)用

1.1 分區(qū)技術(shù)

數(shù)據(jù)庫(kù)提供的分區(qū)功能可以提高許多應(yīng)用程序的可管理性、性能和可用性。在 GIS 領(lǐng)域，將商用關(guān)系數(shù)據(jù)庫(kù)作為空間數(shù)據(jù)的容器，采用分區(qū)技術(shù)提高空間數(shù)據(jù)訪問(wèn)的性能需要合理確定分區(qū)字段。在分區(qū)的基礎(chǔ)上建立高效、易于管理維護(hù)的空間索引是成功應(yīng)用分區(qū)技術(shù)的關(guān)鍵。

1.2 海量空間數(shù)據(jù)的高效存儲(chǔ)

1.2.1 分區(qū)方案選擇

常見的分區(qū)方法包括范圍分區(qū)、Hash 分區(qū)、列表分區(qū)和組合分區(qū)?？臻g數(shù)據(jù)的特殊性在于其空間特性，根據(jù) GIS 應(yīng)用的特點(diǎn)，范圍分區(qū)和列表分區(qū)較適合海量空間數(shù)據(jù)的大表分區(qū)存儲(chǔ)。本文采用范圍分區(qū)方法，通過(guò)預(yù)先設(shè)定圖幅范圍避免范圍分區(qū)帶來(lái)的各分區(qū)數(shù)據(jù)不均勻問(wèn)題。

1.2.2 數(shù)據(jù)裝載

為保證分區(qū)內(nèi)空間對(duì)象地理范圍的連續(xù)性，先根據(jù)數(shù)據(jù)的空間分布特征劃分圖幅范圍，各圖幅應(yīng)該是整個(gè)數(shù)據(jù)范圍的一個(gè)劃分。如圖 1 所示，根據(jù)數(shù)據(jù)的空間分布情況，將數(shù)據(jù)分為 4 個(gè)區(qū)，盡量保證各區(qū)數(shù)據(jù)量均衡。存儲(chǔ)在數(shù)據(jù)庫(kù)中4 個(gè)不同的表空間內(nèi)，跨圖幅的數(shù)據(jù)單獨(dú)存放在分區(qū) 4 中。

1.2.3 數(shù)據(jù)維護(hù)

基于分區(qū)技術(shù)的空間數(shù)據(jù)存儲(chǔ)使空間數(shù)據(jù)能以分區(qū)為單位被維護(hù)并管理，如數(shù)據(jù)更新、索引維護(hù)等工作可以在單個(gè)分區(qū)內(nèi)進(jìn)行，而不影響其他分區(qū)中的數(shù)據(jù)，提高了海量數(shù)據(jù)的可管理性和可維護(hù)性。

2 靜態(tài) R 樹的并行構(gòu)建

2.1 存在的問(wèn)題

空間數(shù)據(jù)的 R 樹構(gòu)建[2]是 CPU 密集型計(jì)算，且涉及大量I/O 操作，其時(shí)耗很大。已有很多方法可以加速 R 樹的構(gòu)建，如 Packed R 樹、Hilbert Packed R 樹、Bercken’s Buffer R 樹、 Arge’s Buffered R 樹等靜態(tài) R 樹，但針對(duì)海量數(shù)據(jù)的 R 樹構(gòu)建時(shí)間仍然不能滿足實(shí)際應(yīng)用的要求。且全局空間索引維護(hù)困難，海量空間數(shù)據(jù)的 R 樹索引會(huì)導(dǎo)致樹深度增加，查詢效率下降。存在小部分?jǐn)?shù)據(jù)“臟區(qū)”時(shí)，必須對(duì)全局?jǐn)?shù)據(jù)重建空間索引。

針對(duì)以上問(wèn)題，在空間數(shù)據(jù)分區(qū)存儲(chǔ)的基礎(chǔ)上對(duì)分區(qū)數(shù)據(jù)并行計(jì)算空間索引，減少索引創(chuàng)建時(shí)間。在保證查詢效率的同時(shí)，提高全局索引的可維護(hù)性。

2.2 基于 TGS 算法的 R 樹并行構(gòu)建

2.2.1 TGS 算法

Garcia 等人于 1998 提出自上而下的貪婪分裂(Top-down Greedy-Split, TGS)算法，其特點(diǎn)是自上而下地遞歸構(gòu)建 R 樹。

在 R 樹的遞歸分裂過(guò)程中，通常采用掃描線分割空間中N 個(gè)對(duì)象的 MBR 面積作為 TGS 的自定義代價(jià)函數(shù)選擇掃描線，即

f(r1, r2)=SArea(r1)+SArea(r2)

其中，SArea(ri)為被掃描線分割的第 i 個(gè)部分的面積。

每次遞歸過(guò)程中選擇分割當(dāng)前子集中 N 個(gè)對(duì)象的 MBR面積最小的掃描線，即

S=min(fi(r1, r2))

其中，i=1,2,…,n，n 為掃描線總數(shù);S 為選取的掃描線;fi(r1, r2)表示第 i 條掃描線。

2.2.2 R 樹的并行構(gòu)建

如圖 2 所示，并行計(jì)算 R 樹索引的基本思想如下：采用并行 GIS 處理常用的典型策略[3]，即 DCSO(Decomposition, Conquer, Stitch, Output)策略，本文數(shù)據(jù)分區(qū)存儲(chǔ)實(shí)現(xiàn)了數(shù)據(jù)的自然分解，即問(wèn)題分解;指定處理節(jié)點(diǎn)分別處理各分區(qū)數(shù)據(jù)，生成 R 樹的子樹;將各子樹作為根節(jié)點(diǎn)的分支節(jié)點(diǎn)插入，完成整體索引創(chuàng)建，得到最終結(jié)果。

更多內(nèi)容請(qǐng)查看pdf