明 梓，劉 偉，李 旸，崔俊杰，劉 剛，李佳惠，雷夢婷

（1.湖北工業(yè)大學(xué) 經(jīng)濟與管理學(xué)院，湖北 武漢 430068；2.長江信達(dá)軟件技術(shù)（武漢）有限責(zé)任公司，湖北 武漢 430014；3.中國地質(zhì)大學(xué)（武漢）地理與信息工程學(xué)院；4.中國地質(zhì)大學(xué)（武漢）計算機學(xué)院，湖北 武漢 430078；5.湖北工業(yè)大學(xué) 計算機學(xué)院，湖北 武漢 430068）

0 引言

城市化進程的加快帶來了交通擁堵、空間環(huán)境惡劣等問題，給我國智慧城市的建設(shè)帶來了挑戰(zhàn)［1-4］。合理開發(fā)與利用城市地理空間大數(shù)據(jù)，借助物聯(lián)網(wǎng)和人工智能等技術(shù)對城市地理空間資源進行智能管控與高效調(diào)度是解決上述問題的有效途徑。在面向城市地理空間大數(shù)據(jù)的地理信息系統(tǒng)（Geographic Information System，GIS）建設(shè)中，高效的空間查詢技術(shù)是關(guān)鍵基礎(chǔ)［5-9］。其中，區(qū)域查詢方法是應(yīng)用最廣泛的一類查詢方法，可以快速檢索到指定區(qū)域內(nèi)包含的全部地理空間對象（例如建筑、植被、公共設(shè)施、車輛等），幫助城市管理者了解城市地物的分布情況，從而為其提供決策支持。

基于空間邊界約束的查詢通常被稱為空間區(qū)域查詢，即從該數(shù)據(jù)庫中檢索出一個指定區(qū)域內(nèi)的所有數(shù)據(jù)對象，這個目標(biāo)區(qū)域可以是任何形狀的封閉幾何圖形。目前主流區(qū)域查詢算法均基于R-tree 提出，但由于R-tree 在面對大規(guī)模、非均勻分布的城市空間大數(shù)據(jù)時會出現(xiàn)節(jié)點重疊、結(jié)構(gòu)失衡等一系列問題，以R-tree 索引為基礎(chǔ)的區(qū)域查詢算法很難有理想表現(xiàn)。因此，MVD（Multi-layer Voronoi Diagrams）索引被提出，其通過多層Voronoi 網(wǎng)絡(luò)結(jié)構(gòu)替代傳統(tǒng)樹形結(jié)構(gòu)，有效規(guī)避了上述問題［5］。以MVD 為基礎(chǔ)的區(qū)域查詢算法在面對城市空間大數(shù)據(jù)時展現(xiàn)出更高的查詢效率（即查詢算法的響應(yīng)速度），但其無法直接對非點型數(shù)據(jù)進行索引，因此基于MVD 的區(qū)域查詢方法不支持非點型空間數(shù)據(jù)。

針對上述問題，本文基于MVD 索引提出一種針對非點型空間對象的區(qū)域查詢技術(shù)框架：首先通過最小外包圓（Minimum Bounding Circle，MBC）對空間對象進行擬合，實現(xiàn)MVD 索引對非點型空間對象的存儲管理；然后根據(jù)空間對象最小外包圓的半徑上界對查詢區(qū)域進行邊界拓展，實現(xiàn)MVD 索引對非點型空間對象的區(qū)域查詢，進而提出MVD-Polygon 算法。為進一步優(yōu)化MVD-Polygon 算法的查詢效率，采用空間對象尺度對數(shù)據(jù)進行分級管理，從而加速查詢過程，并將優(yōu)化后的MVD-Polygon 命名為MVDPolygon-Grade。為驗證該方案的有效性，將MVD-Polygon、MVD-Polygon-Grade 與基于R-tree 的主流區(qū)域查詢算法Multi-step 進行性能比較，結(jié)果表明MVD-Polygon 算法擁有更高的查詢效率。

1 相關(guān)研究

空間區(qū)域查詢最早由Willard［10］提出，并提供了一種以O(shè)(nlog64)復(fù)雜度求解的方案，其中n為數(shù)據(jù)庫中的數(shù)據(jù)總量；而后，Paterson 等［11］基于B-tree 提出一種計算復(fù)雜度為O(k·logn+s)的求解方案，其中k為多邊形邊的數(shù)量，s為結(jié)果集大小。自R-tree 索引被提出后，絕大多數(shù)區(qū)域查詢方法都開始采用該索引作為基礎(chǔ)來實現(xiàn)。為減少PIP（Point in Polygon）驗證次數(shù)，Kriegel 等［12］基于R-tree 索引提出一種通過兩級過濾策略實現(xiàn)的空間區(qū)域查詢算法Multi-step，該算法通過查詢區(qū)域的外包近似形從R-tree 中檢索出一個候選集，然后對候選集中的對象逐一過濾，篩選出最終結(jié)果集。R-tree 內(nèi)部的基本單元都是空間正交矩形，而正交矩形之間的空間關(guān)系運算非常簡單快速，因此一般情況下都是利用正交的最小外包矩形（Minimum Bounding Rectangle，MBR）來構(gòu)建查詢區(qū)域的近似形。在Oracle Spatial 組建中，區(qū)域查詢也是基于R-tree 實現(xiàn)的，但其不需要利用空間近似形進行初次過濾，而是直接利用查詢范圍進行檢索［13］。在這種區(qū)域查詢算法的執(zhí)行過程中，雖然部分節(jié)點與查詢區(qū)域之間的空間拓?fù)潢P(guān)系運算成本會有所增加，但總體I/O 成本有效降低。

城市地理空間數(shù)據(jù)的多中心非均勻分布會加劇Rtree 索引的節(jié)點重疊，因此在面向城市地理空間大數(shù)據(jù)的GIS 系統(tǒng)中，基于R-tree 實現(xiàn)的區(qū)域查詢算法需要訪問大量索引中間層節(jié)點，并產(chǎn)生大量冗余空間關(guān)系驗證，進而導(dǎo)致基于R-tree 的Multi-step 區(qū)域查詢算法在面對海量對象、空間關(guān)系復(fù)雜的場景中存在查詢效率較低的問題。為進一步提升復(fù)雜場景下的算法查詢效率，Li等［14］基于復(fù)合型索引VoR-tree 提出一種利用Voronoi 圖實現(xiàn)的區(qū)域查詢方法Voronoi-Region，并將該方遷移至高性能的多層網(wǎng)絡(luò)結(jié)構(gòu)索引MVD 中［5］。借助MVD 的非樹形結(jié)構(gòu)，該算法在避免訪問大量中間節(jié)點的同時削減了絕大部分冗余數(shù)據(jù)點的訪問和驗證，有效提升了海量對象以及復(fù)雜空間關(guān)系場景中針對點型數(shù)據(jù)的區(qū)域查詢效率。然而，Voronoi圖的構(gòu)建需要以一個離散點集合為基礎(chǔ)，以Voronoi 圖為基礎(chǔ)部件的MVD 索引僅支持點型數(shù)據(jù)管理，即相對應(yīng)的區(qū)域查詢方法無法適用于非點型數(shù)據(jù)檢索。

為此，本文基于MVD 索引提出針對非點型數(shù)據(jù)的管理方式和相應(yīng)的區(qū)域查詢算法，以解決MVD 索引不支持非點型數(shù)據(jù)管理以及其對應(yīng)的區(qū)域查詢算法無法對非點型數(shù)據(jù)進行區(qū)域查詢的問題，進而改進目前主流算法在海量對象與復(fù)雜空間關(guān)系場景下對非點型數(shù)據(jù)進行區(qū)域查詢時效率不足的問題。

2 基于邊界擴展的MVD區(qū)域查詢技術(shù)

2.1 總體技術(shù)框架設(shè)計

基于MVD 索引實現(xiàn)針對非點型空間數(shù)據(jù)的高性能區(qū)域查詢方法需要解決兩個重點問題：第一是如何實現(xiàn)MVD 索引對非點型空間對象的存儲管理？本文基于MVD索引的點對象與非點型空間對象之間的關(guān)系構(gòu)建起兩種映射關(guān)系，完成對非點型空間對象的管理；第二是如何基于MVD 索引設(shè)計針對非點型空間對象的區(qū)域查詢方法？本文采用引入緩沖區(qū)的方法構(gòu)建候選集，并對候選集中的對象進行空間關(guān)系驗證，得到最終結(jié)果集。同時基于初始查詢邊界拓展查詢邊界，實現(xiàn)MVD 索引對非點型空間對象的查詢，并基于空間對象尺度的數(shù)據(jù)分級方法加速查詢過程?？傮w技術(shù)框架見圖1（彩圖掃OSID 碼可見，下同）。

Fig.1 Overall technical framework圖1 總體技術(shù)框架

2.2 非點型空間對象存儲管理方法

針對非點型空間對象的管理方式需注意兩個方面：①MVD 索引結(jié)構(gòu)是以點對象為基礎(chǔ)構(gòu)建的，非點型空間對象需基于MVD 索引結(jié)構(gòu)進行管理；②MVD 索引結(jié)構(gòu)管理非點型空間對象時需完整地存儲非點型對象數(shù)據(jù)。

針對第一個方面，MVD 索引結(jié)構(gòu)以點對象為基礎(chǔ)構(gòu)建，需要選擇某個點來代替非點型空間對象構(gòu)建索引結(jié)構(gòu)。本文選擇非點型空間對象的質(zhì)心代替整個對象構(gòu)建MVD 索引結(jié)構(gòu)，構(gòu)建質(zhì)心與整個對象一對一的映射關(guān)系。非點型空間對象與質(zhì)點映射關(guān)系如圖2所示。

Fig.2 Mapping relationship between non-point spatial object and centroid圖2 非點型空間對象與質(zhì)心映射關(guān)系

針對第二個方面，非點型空間對象包含眾多數(shù)據(jù)，如對象的邊界線數(shù)據(jù)、尺度數(shù)據(jù)、屬性數(shù)據(jù)等。在完成這些數(shù)據(jù)的存儲后，本文根據(jù)質(zhì)心與這些數(shù)據(jù)的關(guān)聯(lián)關(guān)系構(gòu)建一對多的映射關(guān)系。

以上兩種映射關(guān)系可以通過非點型空間對象的質(zhì)心ID 進行關(guān)聯(lián)。其中，第一種映射關(guān)系通過非點型空間對象的質(zhì)心構(gòu)建MVD 索引，然后通過針對點對象的空間查詢方法進行區(qū)域查詢，可以得到非點型空間對象的質(zhì)心構(gòu)成的點集；第二種映射關(guān)系根據(jù)點集中的點對象ID 與其對應(yīng)的非點型空間對象ID 的映射關(guān)系即可查詢到整個非點型空間對象的全部數(shù)據(jù)。

2.3 基于邊界擴展技術(shù)的MVD索引區(qū)域查詢方法

基于邊界擴展技術(shù)的區(qū)域查詢方法總體流程如圖3所示。該方法主要包含兩個核心技術(shù)，分別為基于MBC半徑的查詢區(qū)域邊界擴展方法和基于擴展邊界的候選集驗證方法?；贛BC 半徑的查詢區(qū)域邊界擴展方法的主要思路為通過引入緩沖區(qū)來增大區(qū)域查詢范圍，使候選集包含所有查詢結(jié)果；基于擴展邊界的候選集驗證方法的主要思路為通過對候選集中的對象進行空間關(guān)系驗證來篩選出最終結(jié)果集。

Fig.3 Overall process of region query method based on boundary extension technology圖3 基于邊界擴展技術(shù)的區(qū)域查詢方法總體流程

2.3.1 基于MBC半徑的查詢區(qū)域邊界擴展方法

選擇非點型空間對象的質(zhì)心構(gòu)建MVD 索引后，如果僅直接按照將質(zhì)點視為整個非點型空間對象的思路進行區(qū)域查詢，則會造成質(zhì)點在查詢區(qū)域外，但其實際對應(yīng)的非點型空間對象在查詢區(qū)域內(nèi)的情況，本文將其稱為漏檢問題。針對該問題，本文在原有區(qū)域查詢邊界的基礎(chǔ)上引入緩沖區(qū)來構(gòu)建候選集。為表述方便，定義以下概念：①空間對象尺度，指空間對象最小外包圓的半徑值，用R 表示，點對象的尺度為零；②緩沖區(qū)尺度，指構(gòu)建緩沖區(qū)過程中在查詢邊界外側(cè)所作的平行線與查詢邊界的垂直距離，用L表示；③數(shù)據(jù)集尺度，數(shù)據(jù)集中全體空間對象尺度的最大值代表該數(shù)據(jù)集的尺度，即Rmax=Max{R1，R2，R3，…，Rn}，用Rmax表示。

以緩沖區(qū)邊界為基礎(chǔ)執(zhí)行對點對象的區(qū)域查詢方法，得到由質(zhì)心構(gòu)成的點集，點集中的質(zhì)心所對應(yīng)的非點型空間對象構(gòu)建成了候選集。只要緩沖區(qū)邊界可以包含所有結(jié)果，便可以避免漏檢現(xiàn)象。因此，在初始區(qū)域查詢邊界的基礎(chǔ)上引入何種尺度的緩沖區(qū)是關(guān)鍵問題［15-17］，基于極限思想，當(dāng)緩沖區(qū)尺度大于或等于數(shù)據(jù)集中最大尺度的非點型空間對象時，緩沖區(qū)邊界恰好包含所有結(jié)果。以圖4為例，尺度最大的非點型空間對象為4 號，其質(zhì)心為p點，尺度為Rmɑx，如果僅看區(qū)域查詢邊界，p點在區(qū)域查詢邊界之外，當(dāng)緩沖區(qū)尺度L等于Rmɑx時，緩沖區(qū)邊界可以包含所有區(qū)域查詢的結(jié)果（p點在緩沖區(qū)邊界內(nèi)），這些結(jié)果構(gòu)成了針對非點型空間對象的區(qū)域查詢算法的候選集。

Fig.4 Schematic diagram of maximum value of buffer scale圖4 緩沖區(qū)尺度極大值示意圖

綜上可知，基于初始查詢邊界引入合適尺度的緩沖區(qū)便可使所有結(jié)果包含在緩沖區(qū)范圍內(nèi)。對于區(qū)域查詢邊界，分別在其外側(cè)作距邊界線一定距離的平行線可生成緩沖區(qū)邊界［18］。根據(jù)查詢區(qū)域原始邊界的頂點坐標(biāo)和緩沖區(qū)尺度可以求得每個原始頂點到其在緩沖區(qū)邊界上對應(yīng)頂點間的向量d，從而得到緩沖區(qū)邊界上所有頂點的坐標(biāo)。每個頂點對應(yīng)的向量d的計算步驟如下：

（1）構(gòu)建單位向量。如圖5 所示，對于當(dāng)前區(qū)域查詢邊界上的點p來說，其與左右相鄰點n、m構(gòu)成兩個向量，設(shè)向量為n，向量為m，其單位向量分別為a和b。

Fig.5 Schematic diagram of buffer intersectionc圖5 緩沖區(qū)交點示意圖

（2）計算擴大后的向量。計算出單位向量后，由于兩個方向的向量大小模長均為1，將a和b向量相加并取反得到外擴方向上的單位向量c。

（3）計算緩沖區(qū)邊界上的交點。緩沖區(qū)尺度為L，取向量c的反向向量-c與m的角度，進而計算向量-c與向量m的距離dis。計算dis與L的比值，根據(jù)比值計算向量c方向上的目標(biāo)向量d，計算方法見式（1）。最后根據(jù)兩個向量求出目標(biāo)點q。

基于數(shù)據(jù)集尺度引入對應(yīng)尺度的緩沖區(qū)，然后利用緩沖區(qū)邊界對空間對象集對應(yīng)的質(zhì)心點集執(zhí)行范圍查詢，即可得到充分包含所有結(jié)果集對象的候選集。具體步驟為：①獲取區(qū)域查詢范圍邊界；②基于原始區(qū)域查詢邊界引入數(shù)據(jù)集對應(yīng)的緩沖區(qū)，得到緩沖區(qū)邊界；③基于緩沖區(qū)邊界進行針對點數(shù)據(jù)的區(qū)域查詢，得到質(zhì)心集合；④基于“2.2”節(jié)中的第一種映射關(guān)系即可通過質(zhì)心集合中的質(zhì)心ID 查詢到質(zhì)心對應(yīng)的非點型空間對象，這些非點型空間對象構(gòu)成了候選集。

2.3.2 基于擴展邊界的候選集驗證方法

當(dāng)候選集構(gòu)建完成后，需要對其中的對象進行過濾，以得到最終結(jié)果集，其中過濾主要是驗證結(jié)果集中非點型空間對象與區(qū)域查詢邊界之間空間關(guān)系的過程。候選集中的非點型空間對象可分為兩類：第一類是質(zhì)心在區(qū)域查詢邊界內(nèi)的對象，第二類是質(zhì)心在區(qū)域查詢邊界與緩沖區(qū)邊界之間的對象。如圖6 所示，1、2、3 號對象為第一類對象；紅點處為第二類對象。

Fig.6 Schematic diagram of two types of non-point spatial objects圖6 兩種非點型空間對象示意圖

針對第一類對象進行空間關(guān)系驗證，如果某個空間對象的質(zhì)心在區(qū)域查詢邊界內(nèi)，說明這個對象一定與查詢邊界存在相交或包含關(guān)系，屬于區(qū)域查詢的結(jié)果集，只需要進行一次針對點對象的區(qū)域查詢即可得到由質(zhì)心構(gòu)成的點集，點集中的點所對應(yīng)的非點型空間對象即為構(gòu)成結(jié)果集的對象。

針對第二類對象進行空間關(guān)系驗證，只需要判斷是否至少滿足以下兩個條件之一：①該空間對象至少存在一個邊界頂點在查詢區(qū)域內(nèi)部（避免邊的重合）；②該空間對象的邊界與查詢區(qū)域邊界相交。本文采用引射線法判斷二者是否相交［19-20］，如果存在相交關(guān)系，則將其納入結(jié)果集中。

2.3.3 算法步驟

基于MVD 索引的針對非點型空間對象的區(qū)域查詢算法步驟為：

2.4 基于空間對象尺度分級的索引構(gòu)建策略

由上文可知，基于初始查詢邊界引入合適尺度的緩沖區(qū)便可將所有結(jié)果包含在緩沖區(qū)范圍內(nèi)。如果數(shù)據(jù)集中的非點型空間對象尺度相近，引入緩沖區(qū)進行區(qū)域查詢后候選集中只包含少量冗余對象。然而在城市空間查詢場景中，數(shù)據(jù)集中的非點型空間對象尺度不一定相近，例如一個城市的人工湖、大型商場、一個電話亭的尺度完全不在一個數(shù)量級，根據(jù)城市內(nèi)最大尺度對象的尺度引入緩沖區(qū)后，區(qū)域查詢的候選集中會包含大量冗余對象。如果根據(jù)尺度對數(shù)據(jù)集中的對象進行分類，手動將尺度相近的對象分在同一個數(shù)據(jù)集中，例如將電話亭、汽車等尺度在米級別的對象分到一個數(shù)據(jù)集中，將商場、學(xué)校等百米級別的對象分到另一個數(shù)據(jù)集中，以此構(gòu)成若干個子數(shù)據(jù)集，并分別引入對應(yīng)尺度的緩沖區(qū)進行查詢，則可有效減少候選集中的冗余對象。

如圖7 所示，以澳門市建筑輪廓的一部分為研究對象構(gòu)建各尺度子數(shù)據(jù)集的候選集，建筑對象構(gòu)成了數(shù)據(jù)集，將數(shù)據(jù)集內(nèi)的對象手動分為大、中、小尺寸的3 個子數(shù)據(jù)集，并分別引入相應(yīng)尺度的緩沖區(qū)。其中，圖7（a）為數(shù)據(jù)集未進行尺度劃分的情況，引入整個數(shù)據(jù)集中尺度最大的空間對象的尺度（圖中5 號對象的尺度）作為緩沖區(qū)邊界，質(zhì)心在緩沖區(qū)內(nèi)的所有非點型空間對象均被納入到候選集中，共包含20 個對象，其中1、2、3、4 號對象為區(qū)域查詢的最終結(jié)果。圖7（b）、（c）、（d）為3 個不同尺度的子數(shù)據(jù)集引入對應(yīng)尺度緩沖區(qū)后的結(jié)果。子候選集中的對象個數(shù)分別為6、2、0，對子候選集取并集構(gòu)成最終候選集，共包含8 個對象，且1、2、3、4 號對象均包含其中?？梢钥闯?，對數(shù)據(jù)集進行分級預(yù)處理可有效減少候選集中的冗余對象。

Fig.7 Schematic diagram of candidate subset construction of sub data sets of all scales圖7 各尺度子數(shù)據(jù)集候選集構(gòu)建示意圖

3 實驗方法與結(jié)果分析

為驗證本文提出的針對非點型空間對象的區(qū)域查詢算法MVD-Polygon-Grade（以下簡稱MPG 算法）的性能，以及基于空間對象尺度的數(shù)據(jù)分級管理方案的查詢效率，以基于R-tree 的Multi-step 算法（以下簡稱MS 算法）和MVD-Polygon（以下簡稱MP 算法）算法為對照進行評估實驗。本實驗旨在比較3 種算法的時間效率，即算法完成一次查詢所需要的時間，所需時間越少，算法效率越高。為減少誤差，實驗結(jié)果經(jīng)過50次運行后取算數(shù)平均值得到。

3.1 實驗環(huán)境配置

實驗環(huán)境主要包括軟件和硬件兩個方面，詳細(xì)配置如表1所示。

3.2 數(shù)據(jù)集

基于尺度相近的對象放到同一個子數(shù)據(jù)集的原則，本研究根據(jù)澳門市12 482 個建筑輪廓的面數(shù)據(jù)將城市建筑分為5類，構(gòu)建5個子數(shù)據(jù)集。具體信息見表2。

Table 2 Information of sub datasets at different scales表2 不同尺度子數(shù)據(jù)集信息

3.3 結(jié)果分析

如圖8 所示，澳門市建筑輪廓數(shù)據(jù)集包含12 482 個建筑輪廓的面數(shù)據(jù)，這些面數(shù)據(jù)共由225 807 個邊界點構(gòu)成，平均每個面數(shù)據(jù)由18 個點表示，符合非點型空間對象的特征。

Fig.8 Outline of buildings in Macao圖8 澳門市建筑輪廓

為研究區(qū)域查詢邊界的規(guī)則程度對算法效率的影響，分別構(gòu)建頂點為4～6 個和20～30 個的多邊形作為區(qū)域查詢邊界，兩組多邊形分別構(gòu)建50 個。為減少查詢面積對實驗結(jié)果的影響，本組實驗保證查詢區(qū)域邊界的最小外包圓面積相同，查詢面積依次為3 km2、5 km2、8 km2、12 km2、16 km2。由圖9 可以看出，無論區(qū)域查詢邊界是否規(guī)則，在相同查詢面積下，MPG 算法比MS算法和MP 算法具有更高的效率，但MPG 算法比MS 算法更易受到區(qū)域查詢邊界規(guī)則程度的影響，區(qū)域查詢邊界越復(fù)雜，MPG 算法效率下降得越快。這是由于在MPG 算法的結(jié)果集構(gòu)建過程中，第一類空間對象是基于高效MVD 針對點數(shù)據(jù)的區(qū)域查詢算法而來，本身就屬于結(jié)果集，只需要很低的時間成本即可完成第一類空間對象的確定；而判斷第二類空間對象是否屬于結(jié)果集需要依次對其進行空間關(guān)系驗證，相對耗時，且區(qū)域查詢邊界越復(fù)雜，空間關(guān)系驗證所需時間成本越高；區(qū)域查詢面積越小，第二類空間對象占整個候選集的比例越大。基于以上原因，MPG 算法基于空間對象尺度對數(shù)據(jù)進行分級管理，以確保第二類空間對象很少。MP 算法沒有基于空間對象尺度對數(shù)據(jù)進行分級管理，導(dǎo)致有大量第二類空間對象需要進行空間關(guān)系驗證，因此與MS 算法相比，MP 算法在區(qū)域查詢面積較小時并未體現(xiàn)出明顯優(yōu)勢。隨著區(qū)域查詢面積的增大，第二類空間對象占候選集對象的比例逐漸降低，MP 算法效率逐漸接近MPG 算法。

Fig.9 The influence of the rule degree of region query boundary on the efficiency of region query圖9 區(qū)域查詢邊界規(guī)則程度對區(qū)域查詢效率的影響

為驗證查詢區(qū)域面積對算法效率的影響，本組實驗的區(qū)域查詢邊界形狀設(shè)置為正交矩形，查詢位置隨機，查詢區(qū)域面積分別為3 km2、5 km2、8 km2、12 km2、16 km2，分別占整個數(shù)據(jù)分布區(qū)域的6.2%、10.4%、16.7%、25%、33.3%，每種面積下的查詢次數(shù)均為50 次，取算數(shù)平均值作為最終結(jié)果。由圖10 可以看出，無論何種查詢面積，MPG 算法均比MS 算法和MP 算法有更高的查詢效率。在區(qū)域查詢面積較小的情況下，MP 算法和MS 算法的效率并未表現(xiàn)出顯著差異；在區(qū)域查詢面積較大的情況下，MP 算法的效率接近于MPG 算法，強于MS算法。

Fig.10 The influence of query area on the efficiency of region query圖10 查詢區(qū)域面積對區(qū)域查詢效率的影響

4 結(jié)語

為合理開發(fā)與利用城市地理空間大數(shù)據(jù)，本文針對MVD 索引只能管理點型數(shù)據(jù)而無法直接針對非點型數(shù)據(jù)進行區(qū)域查詢的問題，設(shè)計提出了一種基于邊界擴展技術(shù)的區(qū)域查詢算法實現(xiàn)框架。該框架通過最小外包圓對空間對象進行擬合，基于MVD 索引實現(xiàn)非點型空間對象的區(qū)域查詢，并基于空間對象尺度對數(shù)據(jù)進行分級管理以提高查詢效率。利用澳門市城市建筑輪廓數(shù)據(jù)進行驗證實驗，結(jié)果表明，在相同查詢面積、查詢邊界復(fù)雜程度條件下，本文提出的MVD-Polygon-Grade 算法比Multistep 算法和MVD-Polygon 算法查詢效率更高，且數(shù)據(jù)規(guī)模越大、查詢面積越大，數(shù)據(jù)尺度分級層次越明顯，MVDPolygon-Grade 算法的區(qū)域查詢效率越高。本研究提出了從點對象拓展到非點型空間對象的通用數(shù)據(jù)管理思路和區(qū)域查詢方法，為進一步挖掘現(xiàn)有索引結(jié)構(gòu)的數(shù)據(jù)管理潛力提供了支撐。然而該方法仍存在改進空間：①MVDPolygon-Grade 算法的分級方法為前期數(shù)據(jù)處理過程中的手動粗糙分級，未來將設(shè)計針對數(shù)據(jù)集的最優(yōu)分級方法，以保證各個子數(shù)據(jù)集內(nèi)的數(shù)據(jù)方差最小，數(shù)據(jù)集間方差最大，使候選集驗證過程中產(chǎn)生最少冗余，進一步提升算法效率；②主要驗證了查詢面積、查詢邊界復(fù)雜程度對MVD-Polygon-Grade 算法的影響，未來將研究更多因素（如空間對象的密集程度）對該算法的影響，以拓展其應(yīng)用場景。