M-Quadtree索引：一種基于改進(jìn)四叉樹(shù)編碼方法的云存儲(chǔ)環(huán)境下空間索引方法

付仲良，胡玉龍，翁寶鳳，彭 瑞

1. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079； 2. 浙江省地理信息中心，浙江 杭州 310012

?

M-Quadtree索引：一種基于改進(jìn)四叉樹(shù)編碼方法的云存儲(chǔ)環(huán)境下空間索引方法

付仲良1，胡玉龍1，翁寶鳳1，彭 瑞2

1. 武漢大學(xué)遙感信息工程學(xué)院，湖北 武漢 430079； 2. 浙江省地理信息中心，浙江 杭州 310012

為了解決基于“鍵-值”模型的云存儲(chǔ)環(huán)境僅支持簡(jiǎn)單的關(guān)鍵字查詢，不支持多維空間查詢的問(wèn)題，提出了一種新的分布式空間索引方法——M-Quadtree索引。在索引構(gòu)建過(guò)程中，設(shè)計(jì)了一種基于改進(jìn)四叉樹(shù)的空間數(shù)據(jù)劃分方法，該方法規(guī)定了葉節(jié)點(diǎn)區(qū)域的最小數(shù)據(jù)量，通過(guò)四叉樹(shù)葉節(jié)點(diǎn)的再合并，解決了劃分后各子區(qū)域間存儲(chǔ)量不平衡的問(wèn)題，并且滿足了MapReduce并行化要求。給出了MapReduce框架下M-Quadtree索引的快速構(gòu)建、查詢與更新算法，并在搭建的Hadoop平臺(tái)進(jìn)行了關(guān)鍵參數(shù)對(duì)索引效率的影響以及不同規(guī)模數(shù)據(jù)下索引的創(chuàng)建、查詢和更新試驗(yàn)。與現(xiàn)有分布式空間索引的對(duì)比試驗(yàn)及分析結(jié)果表明，M-Quadtree索引在數(shù)據(jù)存儲(chǔ)量負(fù)載均衡、算法并行化和空間查詢效率等方面表現(xiàn)得更好。

云存儲(chǔ)；MapReduce；空間數(shù)據(jù)管理；空間索引；空間數(shù)據(jù)劃分

地理信息科學(xué)在21世紀(jì)遇到了數(shù)據(jù)密集、計(jì)算密集、并發(fā)訪問(wèn)密集和時(shí)空密集的挑戰(zhàn)[1]。近年來(lái)在IT領(lǐng)域飛速發(fā)展的云計(jì)算技術(shù)的超大規(guī)模、虛擬化、高性能、高可靠性等特點(diǎn)給大規(guī)?？臻g數(shù)據(jù)處理提供了機(jī)遇[2-6]。云存儲(chǔ)是在云計(jì)算環(huán)境下針對(duì)數(shù)據(jù)存儲(chǔ)發(fā)展出來(lái)的一個(gè)新概念，是指通過(guò)計(jì)算機(jī)集群的應(yīng)用、分布式文件系統(tǒng)或網(wǎng)格技術(shù)等，把網(wǎng)絡(luò)中各種類型的存儲(chǔ)設(shè)備在應(yīng)用軟件協(xié)助下集合起來(lái)，共同為用戶提供透明的數(shù)據(jù)存儲(chǔ)服務(wù)[7]。目前主流的云數(shù)據(jù)管理系統(tǒng)，如HBase、Cassandra和亞馬遜的Amazon Simple Storage，底層存儲(chǔ)系統(tǒng)都是基于BigTable管理系統(tǒng)發(fā)展而來(lái)，存儲(chǔ)系統(tǒng)采用的“鍵-值”存儲(chǔ)模型，具有很高的擴(kuò)展性、可用性和容錯(cuò)性。但是“鍵-值”模型是一種一維存儲(chǔ)結(jié)構(gòu)，僅支持基于主鍵的快速查詢，因缺乏索引機(jī)制，所以不能提供高效的多維查詢，這限制了云計(jì)算在地理信息科學(xué)中的應(yīng)用。利用云計(jì)算推進(jìn)地理信息科學(xué)的發(fā)展首先需要面對(duì)的就是空間數(shù)據(jù)的云存儲(chǔ)，而云存儲(chǔ)環(huán)境下的空間索引技術(shù)又是其中需要研究的首要問(wèn)題。目前分布式空間索引主要有兩個(gè)研究方向：一種是改進(jìn)傳統(tǒng)的用于單服務(wù)器的多維數(shù)據(jù)索引的擴(kuò)展性，使之支持多服務(wù)器分布式空間檢索，如SD-Rtree[8]、P2PR-Tree[9]、KR+-索引[10]、HQ-Tree[11]和DQuadtree[12]，它們大部分都是基于經(jīng)典的空間數(shù)據(jù)索引：R-樹(shù)或四叉樹(shù)，但是這種索引結(jié)構(gòu)會(huì)帶來(lái)空間冗余或數(shù)據(jù)量負(fù)載的不均衡，且這種自頂向下的多級(jí)索引結(jié)構(gòu)無(wú)法利用MapReduce并行構(gòu)建；另一種是利用線性化技術(shù)將多維的空間數(shù)據(jù)降為一維，在“鍵-值”模型上直接利用已有一維索引進(jìn)行空間操作[13-15]，這種方法支持高擴(kuò)展性，并行度高，但是僅能保持較寬松的位置鄰近，不適合空間范圍查詢，且更新數(shù)據(jù)后無(wú)法解決數(shù)據(jù)平衡問(wèn)題。

本文針對(duì)云存儲(chǔ)環(huán)境的特點(diǎn)，在吸取現(xiàn)有分布式空間索引優(yōu)點(diǎn)的基礎(chǔ)上，設(shè)計(jì)了一種適合云存儲(chǔ)環(huán)境的分布式空間索引：M-Quadtree索引，以解決現(xiàn)有分布式空間索引存在的數(shù)據(jù)存儲(chǔ)量負(fù)載不均衡、算法較難并行化或空間查詢效率低等問(wèn)題。該索引基于一種改進(jìn)的空間數(shù)據(jù)劃分策略，在MapReduce并行框架下完成空間數(shù)據(jù)的劃分和索引的構(gòu)建。本文同時(shí)給出了M-Quadtree索引在云環(huán)境中的并行構(gòu)建、查詢和更新算法，并和現(xiàn)有的分布式空間索引進(jìn)行了相應(yīng)的對(duì)比試驗(yàn)。

1 M-Quadtree索引方法

云存儲(chǔ)環(huán)境下的空間索引，要求數(shù)據(jù)具有較好的存儲(chǔ)位置鄰近性和負(fù)載平衡性，能滿足云存儲(chǔ)環(huán)境下大數(shù)據(jù)量和高擴(kuò)展性等要求，同時(shí)有較高的索引構(gòu)建效率。本文設(shè)計(jì)了兩級(jí)索引結(jié)構(gòu)——全局索引和塊內(nèi)索引。全局索引在數(shù)據(jù)并行劃分過(guò)程中構(gòu)造，負(fù)責(zé)索引數(shù)據(jù)塊；塊內(nèi)索引在各個(gè)數(shù)據(jù)節(jié)點(diǎn)內(nèi)并行構(gòu)造，負(fù)責(zé)索引數(shù)據(jù)塊內(nèi)的空間對(duì)象。

1.1 空間數(shù)據(jù)劃分

空間數(shù)據(jù)劃分是建立云環(huán)境下空間數(shù)據(jù)索引的基礎(chǔ)，采用不同的劃分方法直接影響索引的構(gòu)建效率和查詢效率。目前建立云環(huán)境下空間數(shù)據(jù)索引所采用的劃分策略主要分為3種：

(1) 基于k-means等空間聚類的劃分[16-17]，該劃分算法能較好地保持空間數(shù)據(jù)的位置鄰近性，得到較好的查詢效果，但是算法時(shí)間效率較低，無(wú)法滿足大數(shù)據(jù)量要求。

(2) 基于四叉樹(shù)的劃分，該劃分算法能保持空間數(shù)據(jù)的位置鄰近性，但是這種遞歸劃分方法會(huì)對(duì)讀取的空間數(shù)據(jù)重復(fù)計(jì)算，不能利用MapReduce并行化，在數(shù)據(jù)分布不均勻的情況下，會(huì)導(dǎo)致劃分后子區(qū)域間的數(shù)據(jù)存儲(chǔ)量不平衡，甚至產(chǎn)生空數(shù)據(jù)節(jié)點(diǎn)，導(dǎo)致查詢效率降低。

(3) 基于Hilbert或Z-Order等空間填充曲線的劃分[18-19]，該劃分算法適合并行化，時(shí)間效率高，但是單純的空間填充曲線方法在搜索的過(guò)程中會(huì)帶來(lái)一些額外的不必要的搜索空間(false-positive search)[20]，且該方法僅能保持較寬松的位置鄰近，查詢的上下界之間可能包含大量的無(wú)關(guān)子查詢區(qū)域，不適空間合范圍查詢。

本文基于MapReduce并行計(jì)算框架的特點(diǎn)和云環(huán)境對(duì)數(shù)據(jù)均衡存儲(chǔ)的要求，改進(jìn)現(xiàn)有四叉樹(shù)劃分方法，使之能滿足MapReduce并行化的要求，并解決劃分后可能出現(xiàn)空查詢區(qū)域的問(wèn)題。假設(shè)空間數(shù)據(jù)總量為D，劃分后每個(gè)數(shù)據(jù)塊容量上限為M，則最少會(huì)產(chǎn)生D/M個(gè)數(shù)據(jù)塊。先對(duì)整個(gè)空間區(qū)域利用四叉樹(shù)劃分方法進(jìn)行劃分，并建立索引四叉樹(shù)，樹(shù)的深度n取

(1)

由于空間數(shù)據(jù)分布的不均衡，落在該四叉樹(shù)某個(gè)葉子區(qū)域的數(shù)據(jù)量會(huì)出現(xiàn)大于或小于M，甚至出現(xiàn)為空的情況。若某葉子區(qū)域內(nèi)數(shù)據(jù)量大于M，對(duì)其繼續(xù)劃分；若葉子區(qū)域內(nèi)數(shù)據(jù)量小于M，并且和相鄰的子區(qū)域數(shù)據(jù)量之和也小于M，則將其與相鄰子區(qū)域合并為一個(gè)子區(qū)域，作為葉子節(jié)點(diǎn)。這時(shí)，四叉樹(shù)的葉子節(jié)點(diǎn)所對(duì)應(yīng)的各子區(qū)域不再是傳統(tǒng)四叉樹(shù)劃分后的4個(gè)面積均等的區(qū)域，而是如圖1所示的“□”型、“I”型和“L”型等3類12種形狀的區(qū)域。其中，“□”型區(qū)代表單獨(dú)某個(gè)象限組成的葉子節(jié)點(diǎn)，4種形狀如圖1(a)，編碼為0—3；“I”型區(qū)代表相鄰兩個(gè)象限合并后形成的葉子節(jié)點(diǎn)，4種形狀如圖1(b)，編碼為4—7；“L”型區(qū)代表相鄰3個(gè)象限合并形成的葉子節(jié)點(diǎn)，4種形狀如圖1(c)，編碼由A—D表示。傳統(tǒng)的四叉樹(shù)在葉子節(jié)點(diǎn)區(qū)域合并后，父節(jié)點(diǎn)所對(duì)應(yīng)的子節(jié)點(diǎn)由傳統(tǒng)的4個(gè)變?yōu)?2個(gè)。

圖1 M-Quadtree劃分編碼模型Fig.1 The coding model of M-Quadtree partition

數(shù)據(jù)塊的編碼類似四叉樹(shù)編碼，由從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的各層節(jié)點(diǎn)編碼組成。唯一與四叉樹(shù)不同的是葉節(jié)點(diǎn)，四叉樹(shù)葉節(jié)點(diǎn)的編碼只有0—3 4種，而本文介紹的編碼方法由于進(jìn)行了節(jié)點(diǎn)間的合并，葉節(jié)點(diǎn)的編碼有0—7和A—D等12種。為了表示與傳統(tǒng)四叉樹(shù)劃分方法的區(qū)別與聯(lián)系，本文稱這種劃分方式為M-Quadtree劃分(M：Modified)，相應(yīng)的編碼為M-Quadtree編碼，以此編碼為基礎(chǔ)構(gòu)建的索引為M-Quadtree索引。M-Quadtree劃分針對(duì)云環(huán)境的特點(diǎn)對(duì)傳統(tǒng)四叉樹(shù)劃分進(jìn)行了改進(jìn)，其優(yōu)勢(shì)有兩點(diǎn)：①M(fèi)-Quadtree劃分規(guī)定了子區(qū)域的最小數(shù)據(jù)量，消除了空區(qū)域，在保持子區(qū)域間數(shù)據(jù)量平衡方面可以表現(xiàn)得更好；②M-Quadtree劃分提高了空間數(shù)據(jù)加載和劃分的并行性，如果用傳統(tǒng)四叉樹(shù)方法并行劃分，其無(wú)法處理劃分后的那些空數(shù)據(jù)區(qū)域，而M-Quadtree并行劃分后可以將這些空數(shù)據(jù)區(qū)域合并。具體的并行劃分和索引構(gòu)建算法見(jiàn)下文。

1.2 空間數(shù)據(jù)塊內(nèi)索引

基于“鍵-值”存儲(chǔ)模型的云存儲(chǔ)系統(tǒng)提供了兩種基本的數(shù)據(jù)讀取方法：多鍵掃描(Scan)和單鍵讀取(Get)，其中Scan操作可以根據(jù)連續(xù)的鍵一次讀取多條記錄，Get操作只能根據(jù)一個(gè)鍵一次讀取一條記錄。文獻(xiàn)[10]已經(jīng)證明了在讀取同樣的數(shù)據(jù)量時(shí)，Scan操作有更高的讀取效率。

本文基于此特征設(shè)計(jì)空間數(shù)據(jù)塊內(nèi)索引，將在同一數(shù)據(jù)塊內(nèi)的空間對(duì)象按照Hilbert次序存儲(chǔ)，能較好地保證空間數(shù)據(jù)的存儲(chǔ)位置鄰近性，以空間對(duì)象的Hilbert碼作為鍵，可以盡可能以連續(xù)的鍵訪問(wèn)相鄰的空間對(duì)象，以提高Scan操作的使用率。相對(duì)于其他的空間填充曲線如Z-曲線、Graycode曲線等，Hilbert曲線已被證明是能夠獲得最佳聚類效果和最高空間查詢效率的空間填充曲線[21-22]，因此本文選用Hilbert曲線映射空間對(duì)象。

空間對(duì)象的Hcode(Hilbert碼)以其最小外包矩形中心點(diǎn)所在網(wǎng)格的Hilbert碼表示，其中點(diǎn)對(duì)象的Hcode以其坐標(biāo)所在網(wǎng)格的Hilbert碼表示。重組后的空間數(shù)據(jù)塊是一種具有特殊格式的數(shù)據(jù)文件，包含兩部分：局部索引部分和數(shù)據(jù)內(nèi)容部分。局部索引部分依次記錄數(shù)據(jù)塊的編碼(Dcode，劃分?jǐn)?shù)據(jù)塊時(shí)得到)、單元網(wǎng)格的行高和列高(ΔX、ΔY)、區(qū)域的數(shù)據(jù)量大小(lengthofregion)、第一個(gè)網(wǎng)格的中心點(diǎn)坐標(biāo)(X0，Y0)，然后依次是根據(jù)Hilbert次序從第一至最后一個(gè)空間對(duì)象的Hcode、空間對(duì)象所在數(shù)據(jù)塊文件內(nèi)的偏移量(offset)和長(zhǎng)度(length)。第i個(gè)空間對(duì)象偏移量由式(2)得出

offseti=P+Di-1

(2)

式中，P為數(shù)據(jù)塊內(nèi)索引所占存儲(chǔ)空間的大小，Di-1為前i-1個(gè)空間對(duì)象的數(shù)據(jù)量大小。根據(jù)經(jīng)典Hilbert碼生成算法[21]，已知對(duì)象的坐標(biāo)信息就可以計(jì)算其Hcode，再根據(jù)Hcode查出空間對(duì)象的塊內(nèi)偏移和長(zhǎng)度，即可得出空間對(duì)象。因?yàn)镠code是按照順序排列，可用折半查找，時(shí)間復(fù)雜度為o(log2n)。

2 M-Quadtree索引構(gòu)建算法

MapReduce框架的Reduce階段可使用用戶自定義的數(shù)據(jù)劃分算法，以提高負(fù)載均衡和計(jì)算效率，本文設(shè)計(jì)的M-Quadtree數(shù)據(jù)劃分方法適合在此階段采用。如圖2所示，算法通過(guò)兩個(gè)MR(MapReduce)階段來(lái)實(shí)現(xiàn)M-Quadtree索引的快速構(gòu)建。算法描述如下。

(1) 在加載數(shù)據(jù)以及構(gòu)建全局索引的MR過(guò)程中,依次進(jìn)行下述操作：

a. 為便于并行計(jì)算，先利用傳統(tǒng)四叉樹(shù)方法對(duì)整個(gè)空間區(qū)域進(jìn)行劃分，并建立索引四叉樹(shù)T，樹(shù)的深度由式(1)得出。

b.m1個(gè)mappers并行地讀取輸入的數(shù)據(jù)切片，對(duì)map函數(shù)讀取的每個(gè)對(duì)象o，根據(jù)其坐標(biāo)與T表計(jì)算其所屬子區(qū)域編碼，輸出〈keyCi,valueo〉鍵值對(duì)，其中，Ci為該對(duì)象所屬子區(qū)域i的四叉樹(shù)編碼。

c.r1個(gè)reducers接收所有劃分到該reducer的對(duì)象子集〈Ci,list(o)〉，每個(gè)reducer計(jì)算list(o)數(shù)據(jù)量大小，若大于上限M，則對(duì)該區(qū)域繼續(xù)四叉樹(shù)劃分，直到?jīng)]有子區(qū)域數(shù)據(jù)量大于M為止。計(jì)算后將數(shù)據(jù)塊〈Ck，list(o)〉分發(fā)到各數(shù)據(jù)節(jié)點(diǎn)，并將〈Ck,sizeOf(list(o))〉存入系統(tǒng)分布式緩存中，其中Ck為數(shù)據(jù)量小于M的子區(qū)域四叉樹(shù)編碼，sizeOf(list(o))為該子區(qū)域數(shù)據(jù)量。

d. 在分布式緩存中計(jì)算，若相鄰子區(qū)域數(shù)據(jù)量之和小于M，合并相鄰的區(qū)域編碼為Xk，并生成〈Ck,Xk〉通知各數(shù)據(jù)節(jié)點(diǎn)完成數(shù)據(jù)塊的合并。

e. 使用元數(shù)據(jù)服務(wù)器MDS收集數(shù)據(jù)塊的編碼，并建立全局索引表。

(2) 在局部索引構(gòu)建的MR過(guò)程中,依次進(jìn)行下述操作:

a.m2個(gè)mappers并行地讀取前一階段生成的數(shù)據(jù)塊〈Ck,list(o)〉，對(duì)map函數(shù)讀取的每個(gè)對(duì)象o，計(jì)算其Hcode，輸出〈keyCk,value 〈Hcode,o〉〉鍵值對(duì)。

b.r2個(gè)reducers接收所有劃分到該reducer的對(duì)象子集〈Ck,list(〈Hcode,o〉)〉，將對(duì)象子集中每個(gè)元組〈Hcode,o〉插入到列表L中，并對(duì)列表L按Hcode進(jìn)行排序。

c. 對(duì)排序后的對(duì)象建立局部索引，并序列化到HDFS文件中。

圖2 M-Quadtree索引構(gòu)建算法流程Fig.2 Flow chart of M-Quadtree index construction algorithm

在步驟(1)a建立索引四叉樹(shù)是為了步驟(1)b、(1)c中mappers、reducers可以并行執(zhí)行。數(shù)據(jù)遷移在第一個(gè)Reducers階段已經(jīng)完成。步驟(1)d合并數(shù)據(jù)塊的計(jì)算是在分布式緩存中完成，時(shí)間消耗可忽略不計(jì)。利用該算法建立的索引有以下優(yōu)勢(shì)：①采用M-Quadtree數(shù)據(jù)劃分算法，利用了四叉樹(shù)劃分不會(huì)有重疊空間的優(yōu)勢(shì)，又彌補(bǔ)了可能會(huì)導(dǎo)致數(shù)據(jù)不平衡的不足；②M-Quadtree編碼有一定的空間聚集性，有利于數(shù)據(jù)的快速讀?。虎廴炙饕跀?shù)據(jù)加載過(guò)程中即建立，并且是一種“扁平結(jié)構(gòu)”，沒(méi)有層層中間節(jié)點(diǎn)，利于數(shù)據(jù)塊的快速定位。④局部索引在各個(gè)節(jié)點(diǎn)內(nèi)部建立，充分利用MapReduce的并行優(yōu)勢(shì)。⑤由于采用了均衡的數(shù)據(jù)劃分方法。當(dāng)數(shù)據(jù)規(guī)模擴(kuò)大時(shí)，每個(gè)數(shù)據(jù)塊容量并沒(méi)有變化，只增大了數(shù)據(jù)塊數(shù)量，系統(tǒng)只需擴(kuò)大節(jié)點(diǎn)數(shù)量和mapper、reducer數(shù)量，索引具有擴(kuò)展性。

3 M-Quadtree索引查詢算法

以空間范圍查詢?yōu)槔?，查詢客戶端以窗口范圍W向元數(shù)據(jù)服務(wù)器MDS發(fā)送消息，查找與W相交的空間目標(biāo)。由于M-Quadtree劃分后會(huì)有“I”、“L”型葉子節(jié)點(diǎn)存在，為了精確查找，在MDS中保存一張對(duì)數(shù)據(jù)集空間范圍進(jìn)行邏輯四叉樹(shù)劃分的坐標(biāo)范圍映射表，先查出與W相交的四叉樹(shù)葉子節(jié)點(diǎn)編碼，再根據(jù)此編碼在MDS目錄(全局索引)中查找其對(duì)應(yīng)的數(shù)據(jù)塊，然后在各個(gè)數(shù)據(jù)塊中利用局部索引查找空間對(duì)象。查詢過(guò)程如圖3所示。

圖3 基于M-Quadtree索引的空間查詢Fig.3 The spatial query based on M-Quadtree index

圖3(a)為查詢區(qū)域在單數(shù)據(jù)塊內(nèi)的查詢，與查詢范圍W相交的邏輯四叉樹(shù)葉子節(jié)點(diǎn)編號(hào)為01，全局索引中匹配的Dcode為01，根據(jù)Dcode在全局索引中查出01數(shù)據(jù)塊所在的IOS節(jié)點(diǎn)，再在該IOS節(jié)點(diǎn)中根據(jù)W坐標(biāo)范圍和Hilbert碼生成算法算出Hcode范圍，根據(jù)Hcode范圍查找在此范圍的空間對(duì)象。圖3(b)為查詢區(qū)域跨數(shù)據(jù)塊查詢，與查詢范圍相交的邏輯四叉樹(shù)葉子節(jié)點(diǎn)編號(hào)為02和31，全局索引中匹配的Dcode為02和3C，此時(shí)將W分為W1和W2，分別在兩個(gè)數(shù)據(jù)塊中并行查找空間對(duì)象。具體查詢算法如下。

輸入：W(查詢范圍)

輸出：與W相交的空間對(duì)象實(shí)體集

(1) 查詢客戶端將W發(fā)給MDS，在MDS中查出與W相交的各數(shù)據(jù)塊Dcode。

(2) 根據(jù)全局索引查找匹配各Dcode的數(shù)據(jù)塊和IOS節(jié)點(diǎn)位置。

a. 在MDS索引表中查找與各Dcode匹配的數(shù)據(jù)塊。

b. 搜索各數(shù)據(jù)塊所在的IOS節(jié)點(diǎn)Si。

c. 由MDS將Dcode和W發(fā)給對(duì)應(yīng)的Si。

(3) 在Si中根據(jù)局部索引查找空間對(duì)象。

a. 根據(jù)W坐標(biāo)范圍和Hilbert碼生成算法，求得W的Hcode范圍。

b. 由Hcode在塊內(nèi)查找空間對(duì)象的塊內(nèi)偏移和長(zhǎng)度，進(jìn)而取出所有空間對(duì)象Oi。

(4) 將各個(gè)Si中取出的空間對(duì)象Oi發(fā)往客戶端，即組成了與W相交的空間對(duì)象實(shí)體集。

步驟(1)、(2)在MDS完成，僅含少量計(jì)算，并無(wú)大量數(shù)據(jù)輸入輸出，所需時(shí)間極少；步驟(3)、(4)在各個(gè)IOS節(jié)點(diǎn)并行完成，最終查詢時(shí)間由查詢時(shí)間最長(zhǎng)的IOS節(jié)點(diǎn)決定。

4 M-Quadtree索引更新算法

在數(shù)據(jù)的增刪過(guò)程中，會(huì)導(dǎo)致數(shù)據(jù)塊間的容量不平衡，進(jìn)而影響索引效率。因此，需要對(duì)數(shù)據(jù)塊分裂或合并。但是頻繁的分裂合并數(shù)據(jù)塊同樣會(huì)導(dǎo)致數(shù)據(jù)更新效率的降低，為避免這種情況，可設(shè)數(shù)據(jù)量上限M的P%大小為容量緩沖范圍，在此范圍內(nèi)的容量變化不進(jìn)行數(shù)據(jù)塊的分裂或合并，僅更新局部索引。

4.1 數(shù)據(jù)插入

數(shù)據(jù)插入可能會(huì)導(dǎo)致數(shù)據(jù)塊的分裂，對(duì)某數(shù)據(jù)塊進(jìn)行數(shù)據(jù)插入操作時(shí)，具體更新算法如下。

輸入：待插入的數(shù)據(jù)O

輸出：索引更新

(1) 利用索引查詢算法查找數(shù)據(jù)O所在的數(shù)據(jù)塊，O可能分布在多個(gè)數(shù)據(jù)塊內(nèi)。

(2) 向目標(biāo)數(shù)據(jù)塊D插入數(shù)據(jù)O。

(3) 如果數(shù)據(jù)塊大小size(D)≤(1+P%)·M，計(jì)算數(shù)據(jù)O的Hcode，在局部索引中插入數(shù)據(jù)記錄的Hcode、在數(shù)據(jù)塊文件內(nèi)的偏移量(offset)和長(zhǎng)度(length)。

(4) 如果size(D)>(1+P%)·M。

a. 分裂數(shù)據(jù)塊，并對(duì)數(shù)據(jù)量之和小于M的相鄰數(shù)據(jù)塊合并，產(chǎn)生若干新的數(shù)據(jù)塊編碼。

b. 將新數(shù)據(jù)塊編碼和原數(shù)據(jù)塊編碼發(fā)回的MDS，在MDS全局索引中刪除原編碼并記錄新生成的編碼。

4.2 數(shù)據(jù)刪除

數(shù)據(jù)刪除可能會(huì)導(dǎo)致數(shù)據(jù)塊的合并，對(duì)某數(shù)據(jù)塊進(jìn)行數(shù)據(jù)刪除操作時(shí)，具體更新算法如下。

輸入：待刪除的數(shù)據(jù)O

輸出：索引更新

(1) 利用索引查詢算法查找數(shù)據(jù)O所在的數(shù)據(jù)塊，數(shù)據(jù)O可能分布在多個(gè)數(shù)據(jù)塊內(nèi)。

(2) 刪除目標(biāo)數(shù)據(jù)塊D中的數(shù)據(jù)O。

(3) 如果數(shù)據(jù)塊大小size(D)≥(1-P%)·M，僅刪除數(shù)據(jù)塊內(nèi)數(shù)據(jù)O的局部索引記錄。

(4) 如果size(D)<1-P%)·M。

a. 根據(jù)該數(shù)據(jù)塊編碼，在MDS中查找與之空間相鄰的子區(qū)域。

b. 對(duì)數(shù)據(jù)量之和小于下限m的相鄰子區(qū)域合并生成新的數(shù)據(jù)塊。

c. 更新合并后數(shù)據(jù)塊局部索引。

d. 將新數(shù)據(jù)塊編碼和原數(shù)據(jù)塊編碼發(fā)回的MDS，在MDS全局索引中刪除原編碼并記錄新生成的編碼。

5 試驗(yàn)與結(jié)果分析

5.1 試驗(yàn)環(huán)境與數(shù)據(jù)

本文試驗(yàn)平臺(tái)由Hadoop-2.4.1集群組成，搭建在12個(gè)節(jié)點(diǎn)上，每?jī)蓚€(gè)節(jié)點(diǎn)部署在一臺(tái)物理機(jī)上。每臺(tái)物理機(jī)包含兩個(gè)虛擬系統(tǒng)、4GB內(nèi)存、500GB硬盤和64位Ubuntu14.04操作系統(tǒng)。兩個(gè)節(jié)點(diǎn)作為MDS(NameNode)，另外10個(gè)節(jié)點(diǎn)作為IOS(DataNode)。測(cè)試數(shù)據(jù)為北京市12 000輛出租車在2012年11月所產(chǎn)生的所有GPS數(shù)據(jù)。該數(shù)據(jù)完整全面地記錄了該市出租車的移動(dòng)軌跡。數(shù)據(jù)大小壓縮前為50GB。本文抽取80 000 000個(gè)數(shù)據(jù)點(diǎn)測(cè)試本文索引的可用性和效率，每個(gè)數(shù)據(jù)點(diǎn)包含空間坐標(biāo)等9個(gè)屬性。

5.2 M對(duì)索引效率的影響

HDFS默認(rèn)數(shù)據(jù)塊大小為64MB，這個(gè)數(shù)字是系統(tǒng)綜合考慮NameNode內(nèi)存消耗、MapReduce框架的效率等設(shè)定的默認(rèn)值[23]。本文中M作為數(shù)據(jù)塊容量的上限，也是M-Quadtree劃分和合并子區(qū)域的容量標(biāo)準(zhǔn)，不對(duì)其非空間數(shù)據(jù)應(yīng)用下的一般性作討論，僅討論其在空間數(shù)據(jù)環(huán)境下的一般性，即僅研究在存儲(chǔ)空間數(shù)據(jù)時(shí)，不同M對(duì)M-Quadtree索引效率造成的影響。圖4顯示了當(dāng)數(shù)據(jù)量為80 000 000個(gè)數(shù)據(jù)點(diǎn)(original)和40 000 000個(gè)數(shù)據(jù)點(diǎn)(half)，M分別為8MB、16MB、32MB、64MB和128MB時(shí)索引的構(gòu)造、查詢、更新所用的時(shí)間。

圖4(a)顯示了在不同數(shù)據(jù)規(guī)模、不同數(shù)據(jù)塊容量M下的索引構(gòu)建時(shí)間。相同數(shù)據(jù)規(guī)模下，當(dāng)M=32MB時(shí)，構(gòu)造索引所需時(shí)間最少。這是因?yàn)楫?dāng)M>32MB時(shí)，數(shù)據(jù)塊容量增大導(dǎo)致構(gòu)造塊內(nèi)索引所需時(shí)間延長(zhǎng)；當(dāng)M<32MB時(shí)，雖然減少了塊內(nèi)索引的構(gòu)造時(shí)間，但是數(shù)據(jù)塊數(shù)目增多，系統(tǒng)在并行劃分?jǐn)?shù)據(jù)塊時(shí)超過(guò)了所能提供的最大并行度。

圖4 參數(shù)M對(duì)索引效率的影響Fig.4 The effect of parameter M in the index

圖4(b)顯示了在不同數(shù)據(jù)規(guī)模、不同M下，查詢整體區(qū)域的0.5%范圍內(nèi)數(shù)據(jù)所需的響應(yīng)時(shí)間。相同數(shù)據(jù)規(guī)模下，M=16MB時(shí)數(shù)據(jù)查詢時(shí)間最少。這是因?yàn)楫?dāng)M>16MB時(shí)，跨塊查詢減少，并行查詢幾率降低，數(shù)據(jù)塊容量的增大也會(huì)導(dǎo)致塊內(nèi)查詢時(shí)間延長(zhǎng)，此時(shí)查詢時(shí)間主要由塊內(nèi)查詢時(shí)間決定；當(dāng)M<16MB時(shí)，跨塊查詢?cè)龆?，系統(tǒng)會(huì)花更多的時(shí)間查找數(shù)據(jù)塊。

圖4(c)顯示了在不同數(shù)據(jù)規(guī)模、不同M下，系統(tǒng)更新100MB數(shù)據(jù)時(shí)的響應(yīng)時(shí)間。相同數(shù)據(jù)規(guī)模下，當(dāng)M=32MB時(shí)索引更新時(shí)間最少。這是因?yàn)楫?dāng)M>32MB時(shí)，數(shù)據(jù)塊容量增大，增刪數(shù)據(jù)導(dǎo)致的塊分裂合并幾率降低，但是塊內(nèi)查詢所需時(shí)間增多同樣會(huì)影響索引更新效率；當(dāng)M<32MB，塊內(nèi)查詢時(shí)間減少，但是塊分裂合并幾率提高，會(huì)對(duì)索引更新效率產(chǎn)生影響。

由此試驗(yàn)可知，在存儲(chǔ)空間數(shù)據(jù)時(shí)，不同數(shù)據(jù)塊大小確實(shí)對(duì)M-Quadtree索引的效率有影響。對(duì)比不同數(shù)據(jù)規(guī)模下M在試驗(yàn)中的5組取值，當(dāng)M取32MB時(shí)，索引有最好的構(gòu)造和更新效率，雖然此時(shí)查詢效率不是最優(yōu)，但與取16MB時(shí)相差不到1s。故綜合考慮，一般情況下可取M=32MB。

5.3 空間數(shù)據(jù)劃分效率分析

空間數(shù)據(jù)劃分策略是并行空間索引結(jié)構(gòu)建立的基礎(chǔ)，它的優(yōu)劣直接影響了云計(jì)算環(huán)境下系統(tǒng)的處理效率。本節(jié)測(cè)試基于M-Quadtree劃分和兩種常用空間數(shù)據(jù)劃分的效率對(duì)比，包括劃分時(shí)間效率、數(shù)據(jù)量負(fù)載均衡度和選用不同劃分方法時(shí)的空間查詢效率。

表1對(duì)比了M-Quadtree劃分與3種現(xiàn)有的空間數(shù)據(jù)劃分方法所用的劃分時(shí)間，同時(shí)為了測(cè)試塊內(nèi)Hilbert編碼構(gòu)造帶來(lái)的額外時(shí)間開(kāi)銷，也與不采用Hilbert塊內(nèi)編碼的M-Quadtree劃分進(jìn)行對(duì)比。這幾種方法均在數(shù)據(jù)劃分過(guò)程中完成了索引的構(gòu)建，故可認(rèn)為此試驗(yàn)是索引的構(gòu)建效率對(duì)比。由試驗(yàn)可以看出，基于Hilbert的劃分方法時(shí)間效率最好，因?yàn)槠洳恍枰啻伪闅v空間對(duì)象，只需要加載數(shù)據(jù)時(shí)，一次性編碼獲取對(duì)象的空間排列即可。基于K-means的方法需要根據(jù)聚類中心的變化不斷迭代，所需時(shí)間遠(yuǎn)遠(yuǎn)大于其他方法。本文提出的M-Quadtree劃分在傳統(tǒng)四叉樹(shù)基礎(chǔ)上針對(duì)并行性進(jìn)行改進(jìn)，雖然在時(shí)間效率上稍遜于Hilbert，但與傳統(tǒng)的四叉樹(shù)劃分方法HQ-Tree相比，效率已經(jīng)有了很大提高。同時(shí)可以看出，采用Hilbert編碼索引塊內(nèi)數(shù)據(jù)確實(shí)增加了整個(gè)劃分的時(shí)間開(kāi)銷，但此開(kāi)銷跟整個(gè)劃分時(shí)間相比并不大，這是因?yàn)榫幋a時(shí)數(shù)據(jù)已經(jīng)加載完畢，并且塊內(nèi)索引的構(gòu)建是利用MapReduce框架在各個(gè)節(jié)點(diǎn)內(nèi)并行完成的。

表1 不同劃分方法的時(shí)間效率對(duì)比

Tab.1 Time efficiency comparison of different partitioning method s

本文用劃分后得到的數(shù)據(jù)塊數(shù)據(jù)量標(biāo)準(zhǔn)差衡量劃分后各數(shù)據(jù)塊的數(shù)據(jù)量負(fù)載均衡度，標(biāo)準(zhǔn)差越小表示劃分后各數(shù)據(jù)塊的數(shù)據(jù)量越均衡。由表2可以看出，使用Hilbert劃分后的數(shù)據(jù)量均衡度最好，使用傳統(tǒng)四叉樹(shù)方法劃分的均衡度最差，并且會(huì)產(chǎn)生更多的數(shù)據(jù)塊,M-Quadtree稍遜于Hilbert方法，但優(yōu)于K-means和傳統(tǒng)的四叉樹(shù)方法。

表2 不同劃分方法的數(shù)據(jù)量負(fù)載均衡度對(duì)比

Tab.2 Load balancing of the size of data of different partitioning method

劃分方法HilbertK?meansHQ?TreeM?Quadtree數(shù)據(jù)塊數(shù)量/個(gè)160176200170標(biāo)準(zhǔn)差/MB1．936．4112．023．43

分布式環(huán)境下的空間查詢效率是反映一個(gè)空間數(shù)據(jù)劃分方法優(yōu)劣的最重要指標(biāo)。圖5顯示了云環(huán)境下，采用不同劃分方法在不同查詢范圍下的空間查詢效率對(duì)比。在查詢范圍較小時(shí)(R<0.1%)，3種方法的查詢時(shí)間都很接近；但是當(dāng)查詢范圍增大，M-Quadtree顯示了最高的查詢效率。Hilbert的查詢效率最差，這是因?yàn)榫€性化只能較寬松地保持?jǐn)?shù)據(jù)存儲(chǔ)鄰近性，隨著查詢范圍的增大，查詢的線性上下界之間會(huì)包含大量的無(wú)關(guān)子查詢區(qū)域。M-Quadtree的查詢效率比基于傳統(tǒng)四叉樹(shù)劃分的HQ-Tree更好，這是因?yàn)楫?dāng)查詢范圍增大，HQ-Tree數(shù)據(jù)不均衡劃分的劣勢(shì)顯現(xiàn)出來(lái)，同樣的數(shù)據(jù)量會(huì)查到更多的數(shù)據(jù)塊，甚至?xí)a(chǎn)生不包含任何數(shù)據(jù)的“空數(shù)據(jù)塊”，并且數(shù)據(jù)塊內(nèi)部沒(méi)有采用索引，只能通過(guò)全局查詢來(lái)獲得具體的數(shù)據(jù)。而采用M-Quadtree劃分的數(shù)據(jù)塊大小相似(接近閾值M)，查詢的數(shù)據(jù)量越大，相對(duì)HQ-Tree查詢到的數(shù)據(jù)塊數(shù)量越少，而且數(shù)據(jù)塊內(nèi)部采用了基于Hilbert組織的索引結(jié)構(gòu)，可以充分利用系統(tǒng)內(nèi)置的Scan操作獲得需要查詢的空間數(shù)據(jù)，故所用的查詢時(shí)間相對(duì)越少。

圖5 不同劃分方法不同查詢范圍下查詢效率對(duì)比Fig.5 Efficiency comparison of spatial querying on different range and different partitioning method

本文設(shè)計(jì)的M-Quadtree劃分方法的各項(xiàng)性能都優(yōu)于傳統(tǒng)的四叉樹(shù)方法，雖然在構(gòu)建效率和數(shù)據(jù)量負(fù)載均衡度上稍遜于基于Hilbert的劃分方法，但在空間查詢效率上遠(yuǎn)遠(yuǎn)優(yōu)于后者。

5.4 并發(fā)環(huán)境下索引查詢效率分析

本節(jié)用兩組試驗(yàn)來(lái)測(cè)試并發(fā)環(huán)境下索引的查詢效率。一組測(cè)試不同索引方法下的并發(fā)查詢效率，另一組測(cè)試M-Quadtree索引下多機(jī)與單機(jī)環(huán)境下的查詢時(shí)間加速比。試驗(yàn)將壓力測(cè)試標(biāo)準(zhǔn)套件Loadrunner-9.10部署在云環(huán)境中用于評(píng)估系統(tǒng)性能。

圖6顯示了并發(fā)用戶數(shù)在50、100、150、200下查詢范圍為0.1%的3種索引方法的平均查詢響應(yīng)時(shí)間對(duì)比。從圖中結(jié)果可以看出，隨著并發(fā)用戶數(shù)的增多，M-Quadtree基本維持在一個(gè)恒定水平，而另外兩種索引方法的響應(yīng)時(shí)間均呈不同的增長(zhǎng)趨勢(shì)。主要原因是Hilbert采用的一級(jí)索引結(jié)構(gòu)，并發(fā)查詢的增多會(huì)給系統(tǒng)主節(jié)點(diǎn)MDS帶來(lái)更大的內(nèi)存壓力；HQ-Tree采用了不均衡的劃分方式，會(huì)查詢到更多的數(shù)據(jù)塊，高并發(fā)查詢帶來(lái)的影響更加明顯；M-Quadtree的負(fù)載更均衡，故其性能并沒(méi)有因?yàn)椴l(fā)查詢的增多而降低。

圖7顯示了不同問(wèn)題規(guī)模下，采用M-Quadtree索引的系統(tǒng)查詢時(shí)間加速比。原始規(guī)模指并發(fā)用戶數(shù)為100，查詢范圍為0.5%；一半規(guī)模指并發(fā)用戶數(shù)為50，查詢范圍為0.25%；雙倍規(guī)模指并發(fā)用戶數(shù)為200，查詢范圍為1%。從圖中可以看到，加速比不僅會(huì)隨著云環(huán)境中處理節(jié)點(diǎn)規(guī)模的擴(kuò)大而增大，同時(shí)也會(huì)隨著問(wèn)題規(guī)模的增大而增大。因此當(dāng)問(wèn)題規(guī)模越大，使用云系統(tǒng)處理空間數(shù)據(jù)作用越明顯。

圖6 并發(fā)查詢響應(yīng)時(shí)間對(duì)比Fig.6 Comparison of response time of concurrent queries

圖7 不同問(wèn)題規(guī)模下并行查詢的加速比Fig.7 Speedup of parallel query under different scale of the problem

5.5 索引更新效率分析

本節(jié)測(cè)試索引更新效率，同樣與Hilbert和HQ-Tree作對(duì)比。圖8顯示了3種索引在插入20 MB、50 MB、100 MB和200 MB數(shù)據(jù)所用的時(shí)間，數(shù)據(jù)刪除所用時(shí)間對(duì)比與此類似。當(dāng)插入數(shù)據(jù)較小時(shí)(P<50 MB)，三者更新數(shù)據(jù)所用時(shí)間相差不大；但是當(dāng)數(shù)據(jù)插入量變大時(shí)，Hilbert和HQ-Tree顯然耗費(fèi)了更多的時(shí)間。這是因?yàn)殡m然Hilbert在開(kāi)始劃分?jǐn)?shù)據(jù)時(shí)能保證數(shù)據(jù)量的負(fù)載均衡，但隨著數(shù)據(jù)插入量增大無(wú)法對(duì)其繼續(xù)保持，而HQ-Tree則會(huì)導(dǎo)致更多的數(shù)據(jù)塊分裂，并且Hilbert和HQ-Tree只有一層索引，任何數(shù)量的數(shù)據(jù)插入都會(huì)導(dǎo)致索引的整體更新；而M-Quadtree劃分使數(shù)據(jù)分布更平衡，并且大部分?jǐn)?shù)據(jù)塊的更新不會(huì)對(duì)全局索引造成影響，可在節(jié)點(diǎn)內(nèi)并行執(zhí)行。

6 結(jié) 論

本文根據(jù)云存儲(chǔ)環(huán)境的特點(diǎn)，改進(jìn)現(xiàn)有的空間數(shù)據(jù)劃分方法，設(shè)計(jì)了一種M-Quadtree劃分方法，該方法將四叉樹(shù)劃分的4種編碼拓展為12種，提高了算法的并行度和劃分效率，同時(shí)能滿足云環(huán)境下數(shù)據(jù)存儲(chǔ)量負(fù)載均衡的要求。基于此劃分方法，提出了一種適用于key-value數(shù)據(jù)模型的云存儲(chǔ)環(huán)境下的分布式空間索引——M-Quadtree索引。相比現(xiàn)有分布式環(huán)境中單純基于樹(shù)或線性化降維的兩種索引結(jié)構(gòu)，本文提出的索引在數(shù)據(jù)負(fù)載均衡、查詢更新效率和并發(fā)訪問(wèn)的應(yīng)對(duì)方面表現(xiàn)得更好。該索引在云環(huán)境中的各項(xiàng)性能均優(yōu)于現(xiàn)有的四叉樹(shù)索引結(jié)構(gòu)，并發(fā)環(huán)境下的空間查詢也優(yōu)于基于Hilbert空間填充曲線的索引，但是索引構(gòu)建效率和負(fù)載均衡度方面仍遜于基于線性化技術(shù)的索引。同時(shí)塊內(nèi)索引仍采用傳統(tǒng)的索引方法，當(dāng)數(shù)據(jù)塊容量變大，塊內(nèi)查詢會(huì)降低空間查詢的效率，故該索引結(jié)構(gòu)仍需進(jìn)一步優(yōu)化。

圖8 索引更新效率對(duì)比Fig.8 Efficiency comparison of index updating

[1] YANG Chaowei, GOODCHILD M, HUANG Qunying, et al. Spatial Cloud Computing: How Can the Geospatial Sciences Use and Help Shape Cloud Computing?[J]. International Journal of Digital Earth, 2011, 4(4): 305-329.

[2] 李德仁. 展望大數(shù)據(jù)時(shí)代的地球空間信息學(xué)[J]. 測(cè)繪學(xué)報(bào), 2016, 45(4): 379-384. DOI: 10.11947/j.AGCS.2016.20160057.

LI Deren. Towards Geo-Spatial Information Science in Big Data Era[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4): 379-384. DOI: 10.11947/j.AGCS.2016.20160057.

[3] VAQUERO L M, RODERO-MERINO L, CACERES J, et al. A Break in the Clouds: Towards a Cloud Definition[J]. ACM SIGCOMM Computer Communication Review, 2009, 39(1): 50-55.

[4] 李德仁, 張良培, 夏桂松. 遙感大數(shù)據(jù)自動(dòng)分析與數(shù)據(jù)挖掘[J]. 測(cè)繪學(xué)報(bào), 2014, 43(12): 1211-1216. DOI: 10.13485/j.cnki.11-2089.2014.0187.LI Deren, ZHANG Liangpei, XIA Guisong. Automatic Analysis and Mining of Remote Sensing Big Data[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12): 1211-1216. DOI: 10.13485/j.cnki.11-2089.2014.0187.

[5] CARY A, YESHA Y, ADJOUADI M, et al. Leveraging Cloud Computing in Geodatabase Management[C]∥Proceedings of the 2010 IEEE International Conference on Granular Computing. Washington, DC: IEEE Computer Society, 2010: 73-78.

[6] 郭仁忠, 劉江濤, 彭子鳳, 等. 開(kāi)放式空間基礎(chǔ)信息平臺(tái)的發(fā)展特征與技術(shù)內(nèi)涵[J]. 測(cè)繪學(xué)報(bào), 2012, 41(3): 323-326.

GUO Renzhong, LIU Jiangtao, PENG Zifeng, et al. Technologies Connotation and Developing Characteristics of Open Geospatial Information Platform[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(3): 323-326.

[7] ZENG Wenying, ZHAO Yuelong, OU Kairi, et al. Research on Cloud Storage Architecture and Key Technologies[C]∥Proceedings of the 2nd International Conference on Interaction Sciences: Information Technology, Culture and Human. New York: ACM, 2009: 1044-1048.

[8] MOUZA C D, LITWIN W, RIGAUX P. Large-Scale Indexing of Spatial Data in Distributed Repositories: the SD-Rtree[J]. The VLDB Journal, 2009, 18(4): 933-958.

[9] MONDAL A, YI Lifu, KITSUREGAWA M. P2PR-Tree: an R-Tree-Based Spatial Index for Peer-to-Peer Environments[M]∥LINDNER W, MESITI M, TüRKER C, et al. Current Trends in Database Technology-EDBT 2004 Workshops. Berlin Heidelberg: Springer, 2004: 516-525.

[10] WEI Lingyin, HSU Y T, PENG W C, et al. Indexing Spatial Data in Cloud Data Managements[J]. Pervasive and Mobile Computing, 2014, 15: 48-61.

[11] FENG Jun, TANG Zhixian, WEI Mi’an, et al. HQ-Tree: a Distributed Spatial Index Based on Hadoop[J]. China Communications, 2014, 11(7): 128-141.

[12] TANIN E, HARWOOD A, SAMET H. Using a Distributed Quadtree Index in Peer-To-Peer Networks[J]. The VLDB Journal, 2007, 16(2): 165-178.

[13] NISHIMURA S, DAS S, AGRAWAL D, et al.MD-HBase: Design and Implementation of an Elastic Data Infrastructure for Cloud-Scale Location Services[J]. Distributed and Parallel Databases, 2013, 31(2): 289-319.

[14] LAWDER J K, KING P J H. Querying Multi-Dimensional Data Indexed Using the Hilbert Space-Filling Curve[J]. ACM SIGMOD Record, 2001, 30(1): 19-24.

[15] CARY A, SUN Zhengguo, HRISTIDIS V, et al. Experiences on Processing Spatial Data with MapReduce[C]∥Proceedings of the 21st International Conference on Scientific and Statistical Database Management. Berlin, Heidelberg: Springer-Verlag, 2009.

[16] CARY A, YESHA Y, ADJOUADI M, et al. Leveraging Cloud Computing in Geodatabase Management[C]∥Proceedings of the 2010 IEEE International Conference on Granular Computing. Washington, DC: IEEE, 2010: 73-78.

[17] 吳明光. 一種空間分布模式驅(qū)動(dòng)的空間索引[J]. 測(cè)繪學(xué)報(bào), 2015, 44(1): 108-115. DOI: 10.11947/j.AGCS.2015.20130245.

WU Mingguang. A Spatial Distribution Pattern-driven Spatial Index[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(1): 108-115. DOI: 10.11947/j.AGCS.2015.20130245.

[18] 王永杰, 孟令奎, 趙春宇. 基于Hilbert空間排列碼的海量空間數(shù)據(jù)劃分算法研究[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2007, 32(7): 650-653.

WANG Yongjie, MENG Lingkui, ZHAO Chunyu. Spatial Partitioning of Massive Data Based on Hilbert Spatial Ordering Code[J]. Geomatics and Information Science of Wuhan University, 2007, 32(7): 650-653.

[19] LIU Yi, JING Ning, CHEN Luo, et al. Parallel Bulk-Loading of Spatial Data with MapReduce: an R-tree Case[J]. Wuhan University Journal of Natural Sciences, 2011, 16(6): 513-519. DOI: 10.1007/sl1859-011-0790-3.

[20] 馬友忠, 孟小峰. 云數(shù)據(jù)管理索引技術(shù)研究[J]. 軟件學(xué)報(bào), 2015, 26(1): 145-166.

MA Youzhong, MENG Xiaofeng. Research on Indexing for Cloud Data Management[J]. Journal of Software, 2015, 26(1): 145-166.

[21] MOON B, JAGADISH H V, FALOUTSOS C, et al. Analysis of the Clustering Properties of the Hilbert Space-Filling Curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 124-141.

[22] ABEL D J, MARK D M. A Comparative Analysis of Some Two-Dimensional Orderings[J]. International Journal of Geographical Information Systems, 1990, 4(1): 21-31.

[23] SHVACHKO K, KUANG H, RADIA S, et al. The Hadoop Distributed File System[C]∥Proceedings of the 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies. Washington, DC: IEEE Computer Society, 2010: 1-10.

(責(zé)任編輯：陳品馨)

M-Quadtree Index: A Spatial Index Method for Cloud Storage Environment Based on Modified Quadtree Coding Approach

FU Zhongliang1,HU Yulong1,WENG Baofeng1,PENG Rui2

1. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China; 2. Geomatics Center of Zhejiang, Hangzhou 310012, China

Currently, the cloud storage platform based on key-value model can only support simple keyword queries but cannot support multidimensional spatial queries. To solve the problem, this paper puts forward a new method of distributed spatial index—M-Quadtree index. In the process of index building, a space partitioning method based on improved quadtree was proposed. This partitioning method specifies the minimum amount of data in the leaf area. By recombining the quad leaves, it solves the problem of storage imbalance among sub regions, and meets the parallel requirements of the MapReduce. This paper describes some algorithms about M-Quadtree index building，querying and updating under the MapReduce framework. In the experiments, we implement the M-Quadtree index on Hadoop platform to test the effect of key parameter on the efficiency of index, and also test the efficiency of index building, querying and updating under different scale of data. Comparing with existing distributed spatial index, experiments show that the M-Quadtree index performs better on data load balancing, algorithm parallelism and the efficiency of spatial querying.

cloud storage; MapReduce; spatial data management; spatial index; spatial data partition

FU Zhongliang(1965—)，male,PhD,professor,PhD supervisor,majors in GIS,vector data matching.

YANG Yuanwei

付仲良，胡玉龍，翁寶鳳，等.M-Quadtree索引：一種基于改進(jìn)四叉樹(shù)編碼方法的云存儲(chǔ)環(huán)境下空間索引方法[J].測(cè)繪學(xué)報(bào)，2016,45(11)：1342-1351.

10.11947/j.AGCS.2016.20150408.

FU Zhongliang,HU Yulong,WENG Baofeng,et al.M-Quadtree Index: A Spatial Index Method for Cloud Storage Environment Based on Modified Quadtree Coding Approach[J]. Acta Geodaetica et Cartographica Sinica,2016,45(11):1342-1351. DOI:10.11947/j.AGCS.2016.20150408.

P208

A

1001-1595(2016)11-1342-10

2015-07-21

修回日期： 2016-09-10

付仲良(1965—),男，博士，教授，博士生導(dǎo)師，主要研究方向?yàn)镚IS、矢量數(shù)據(jù)匹配。

E-mail： fuzhl@263.net

楊元維

E-mail： yyw_08@whu.edu.com