馮 鈞，任 鋒，唐志賢

（河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京211100）

0 引 言

隨著信息技術(shù)的迅猛發(fā)展，各種高新技術(shù)應(yīng)用會(huì)周期性地生成海量的空間數(shù)據(jù)[1]。因而組織和使用這些數(shù)據(jù)顯得愈發(fā)的重要?？臻g數(shù)據(jù)通常形式多樣、規(guī)模巨大、計(jì)算復(fù)雜。這些特性使得如何深度地利用空間數(shù)據(jù)成為一項(xiàng)具有挑戰(zhàn)性的工作。高效的數(shù)據(jù)訪問是深度利用海量數(shù)據(jù)的前提，如何高效地對空間離散數(shù)據(jù)進(jìn)行索引以滿足日益增長數(shù)據(jù)應(yīng)用的的實(shí)時(shí)性需求以成為數(shù)據(jù)庫領(lǐng)域的一個(gè)研究熱點(diǎn)[2－4]。

最基本的空間離散數(shù)據(jù)索引方法是通過將整個(gè)空間區(qū)域劃分成不同的部分，再在各個(gè)區(qū)域中按照一定的順序查找數(shù)據(jù)。典型的primary index有B樹、K－D樹、K－D－B樹、四叉樹、R樹及其變體[5，6]等等。在海量空間數(shù)據(jù)的情況下，往往導(dǎo)致樹的深度過深，上述結(jié)構(gòu)的檢索效率明顯較低。secondary index作為一種混合式索引結(jié)構(gòu)，常見的有QR樹[7]、PMR樹[8]、Hilbert R樹[9]等等，通過兩級級索引的方式能夠有效降低樹的深度，提高檢索效率，但是由于結(jié)構(gòu)復(fù)雜，在處理海量數(shù)據(jù)時(shí)會(huì)帶來龐大的計(jì)算量。面對海量空間數(shù)據(jù)處理與查詢的復(fù)雜性，傳統(tǒng)的集中式處理方式已經(jīng)變成制約處理和查詢效率的 “瓶頸”。隨著 “云計(jì)算”的興起，其所具有擴(kuò)展性好、容錯(cuò)性強(qiáng)同時(shí)具有強(qiáng)大的數(shù)據(jù)并行處理能力的特點(diǎn)，為突破上述 “瓶頸”提供了一個(gè)很好的思路[10]。Hadoop[11]是由 Apache基金會(huì)開發(fā)的開源分布式架構(gòu)，結(jié)合MapReduce能夠?qū)Ａ靠臻g數(shù)據(jù)以一種可靠、高效、可伸縮的方式進(jìn)行處理。

本文提出一種基于Hadoop的QR Tree分布式空間索引，索引存儲在HDFS文件系統(tǒng)中的空間數(shù)據(jù)；利用四叉樹對索引空間的分層劃分，減少R樹空間重疊和查找失敗路徑，有效的解決數(shù)據(jù)非均勻分布時(shí)的不平衡問題。借助Hadoop平臺強(qiáng)大的MapReduce并行編程框架設(shè)計(jì)相應(yīng)的數(shù)據(jù)處理算法，改善索引建立過程，提高查詢過程的效率。

1 Hadoop QR Tree索引結(jié)構(gòu)設(shè)計(jì)

邏輯結(jié)構(gòu)

基于Hadoop的QR樹將四叉樹與R樹結(jié)合起來。它通過四叉樹將整個(gè)空間劃分成至多個(gè)子空間 （k為空間維度）。四叉樹的每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)獨(dú)立的R樹。R樹通過其最小外包矩形 （MBR）確定所屬四叉樹節(jié)點(diǎn)?？臻g數(shù)據(jù)都存儲在R樹中。假設(shè)四叉樹節(jié)點(diǎn)的最大容量為Vmax，即各個(gè)子空間中數(shù)據(jù)量最大為Vmax。當(dāng)某數(shù)據(jù)空間中數(shù)據(jù)量超過Vmax時(shí)，需要進(jìn)行分裂。假設(shè)圖1（a）中數(shù)據(jù)量超過子空間最大容量Vmax，本文使用四叉樹將原數(shù)據(jù)空間劃分為5個(gè)子空間。如圖1（b）、圖1（c）所示，原空間中數(shù)據(jù)根據(jù)其空間位置劃歸到各子空間中。若原空間中有數(shù)據(jù)與多個(gè)下層子空間有交集，則將其劃分到上層子空間[12]。

Hadoop QR Tree（HQR Tree）索引支持離散數(shù)據(jù)查詢和區(qū)域查詢。HQR Tree利用四叉樹將整個(gè)索引空間分成多個(gè)子空間，并分別為每子空間中的數(shù)據(jù)建立R樹，不同子空間中空間數(shù)據(jù)彼此無交集。

如圖2所示的是一棵二維空間的QR樹，空間區(qū)域內(nèi)包含多個(gè)空間數(shù)據(jù) （包括點(diǎn)數(shù)據(jù)和面數(shù)據(jù)）。圖2中QR樹的高度為4，有14個(gè)R樹。整個(gè)空間區(qū)域被劃分成20個(gè)子區(qū)域，共有四層:S1，S2，S3……S20。其中S0＝S1∪S2∪S3∪S4，S1＝S5∪S6∪S7∪S8等。同時(shí)有20棵R樹R1，R2，R3……R20，每課R樹都對應(yīng)一個(gè)子空間。每個(gè)四叉樹節(jié)點(diǎn)包含的子空間均由其上層節(jié)點(diǎn)所包含的空間分裂而來。當(dāng)上層節(jié)點(diǎn)的中數(shù)據(jù)量超過節(jié)點(diǎn)最大容量時(shí)，需要分裂。以空間S1為例，S1中數(shù)量超過最大容量，使用四叉樹將S1劃分成S5，S6，S7，S8這5個(gè)子空間?？臻g區(qū)域上，S5，S6，S7，S8彼此無交集，且S1與原空間區(qū)域大小相同，為S5，S6，S7，S8空間區(qū)域之和，同時(shí)S5，S6，S7，S8在四叉樹中作為原節(jié)點(diǎn)的新增孩子節(jié)點(diǎn)存在，而S1取代原節(jié)點(diǎn)。原空間中數(shù)據(jù)根據(jù)空間位置插入子空間S5，S6，S7，S8中，若有數(shù)據(jù)同時(shí)與S5，S6，S7，S8中多個(gè)有交集，則插入S1中。數(shù)據(jù)r1落在子空間S5中且不與其他子空間相交，則r1被插入到R5中；而r2與S1，S5，S6，S7，S8相交，根據(jù)上述空間分裂規(guī)則，插入子空間S0中，因此數(shù)據(jù)r11被插入到中。

2 基于MapReduce并行創(chuàng)建索引

索引創(chuàng)建算法

本文利用MapReduce改造索引創(chuàng)建算法?；舅枷?首先用四叉樹將索引空間劃分成個(gè)子空間，建立一棵四叉樹，四叉樹的每個(gè)節(jié)點(diǎn)都對應(yīng)一棵R樹，當(dāng)四叉樹節(jié)點(diǎn)對應(yīng)子空間數(shù)據(jù)超過最大容量時(shí)將導(dǎo)致節(jié)點(diǎn)分裂。將數(shù)據(jù)的MBR與各子空間比較，尋找能夠完全將其包含的最小子空間，將數(shù)據(jù)映射到該子空間。若子空間達(dá)到最大容量，則進(jìn)行分裂。最后，為每個(gè)子空間分別建立R樹。數(shù)據(jù)空間的劃分和各個(gè)子空間R樹的建立過程由Map函數(shù)實(shí)現(xiàn)，完成后返回相應(yīng)信息，由Reduce函數(shù)將各個(gè)R樹合并起來并掛載到四叉樹節(jié)點(diǎn)上，最終形成一個(gè)全局的QR樹。

圖2 QR樹空間劃分和樹結(jié)構(gòu)

3 分布式并行查詢策略

3.1 離散數(shù)據(jù)查詢

基本思想:首先將給定的離散數(shù)據(jù)數(shù)據(jù)分組，根據(jù)每個(gè)空間數(shù)據(jù)的空間位置判斷是否在索引空間中。自上而下查詢HQR－tree，與各四叉樹節(jié)點(diǎn)比較，尋找完全包含數(shù)據(jù)的最小四叉樹節(jié)點(diǎn)，接著從此節(jié)點(diǎn)對應(yīng)的R樹中查詢數(shù)據(jù)。

3.2 區(qū)域查詢

基本思想:根據(jù)待查詢區(qū)域空間信息查詢索引空間中存在數(shù)據(jù)。自上而下查詢 HQR－tree，與各四叉樹節(jié)點(diǎn)比較，尋找出與待查詢區(qū)域相交的四叉樹節(jié)點(diǎn)，接著從這些節(jié)點(diǎn)對應(yīng)的R樹中查詢完全包含在相交區(qū)域中的數(shù)據(jù)。

3.3 索引算法性能分析

假設(shè)分布式環(huán)境下計(jì)算節(jié)點(diǎn)個(gè)數(shù)為N，每個(gè)節(jié)點(diǎn)所能并行運(yùn)行的Map函數(shù)和Reduce函數(shù)最多分別為Mn和Rn。則整個(gè)系統(tǒng)最大Map函數(shù)數(shù)為

遍歷四叉樹，耗時(shí)為τq，遍歷R樹，耗時(shí)為τr；

（1）離散數(shù)據(jù)

查詢待查詢數(shù)據(jù)量為O，劃分成若干組，每組最多有S個(gè)數(shù)據(jù) （S≤O），則有個(gè)分組。

1）處理單個(gè)分組中每個(gè)數(shù)據(jù)是否在四叉樹中所需時(shí)間為tQ，有

2）處理單個(gè)分組中每個(gè)數(shù)據(jù)是否在R樹中所需時(shí)間為tR，有

當(dāng)單次四叉樹和R樹查詢時(shí)間不變時(shí)，處理時(shí)間與每組的數(shù)據(jù)數(shù)S和Map函數(shù)個(gè)數(shù)有關(guān)，當(dāng)S越少同時(shí)Map函數(shù)個(gè)數(shù)越多時(shí)，處理單個(gè)組耗時(shí)越少，反之耗時(shí)變長。

由上述可得，系統(tǒng)需要順序執(zhí)行的Map數(shù)Mo為

查詢O個(gè)數(shù)據(jù)是否在四叉樹中耗時(shí)

查詢O個(gè)數(shù)據(jù)是否在R樹中耗時(shí)

則總處理時(shí)間

分析上式 （7）可得，相較于集中式索引響應(yīng)時(shí)間O×（τq＋τr），分布式QR樹通過分布式環(huán)境分散檢索的計(jì)算量，在數(shù)據(jù)個(gè)數(shù)不變的情況下通過增加計(jì)算節(jié)點(diǎn)來減少查詢時(shí)間，提高檢索效率。

（2）區(qū)域查詢

與待查詢區(qū)域相交節(jié)點(diǎn)數(shù)為Cn，對應(yīng)Cn棵R樹，劃分成若干組，每組有S個(gè)數(shù)據(jù) （S≤Cn），則至少有G＝個(gè)這樣的分組。

處理單個(gè)分組，遍歷R樹，查詢并返回相交區(qū)域中數(shù)據(jù)耗時(shí)為

由上述可得，系統(tǒng)需要順序執(zhí)行的Map數(shù)Ma為

則總處理時(shí)間

分析上式，當(dāng)增加計(jì)算節(jié)點(diǎn)的數(shù)量N和每個(gè)節(jié)點(diǎn)上的Map函數(shù)數(shù)量Mn時(shí)，能夠有效減少區(qū)域查詢的總處理時(shí)間T。而在集中式環(huán)境下相同條件的區(qū)域查詢總處理時(shí)間為τq＋τr×Cn。相比較可得，在分布式環(huán)境下算法查詢效率更高。

根據(jù)上述對離散數(shù)據(jù)檢索和區(qū)域檢索的性能分析 （見式 （7），式 （10）），響應(yīng)時(shí)間T與系統(tǒng)計(jì)算節(jié)點(diǎn)數(shù)成正比，當(dāng)計(jì)算節(jié)點(diǎn)個(gè)數(shù)增加時(shí)，能夠有效的減少響應(yīng)時(shí)間T。HQR－Tree相對于集中式算法能夠有效的減少系統(tǒng)響應(yīng)時(shí)間，提高檢索效率。

4 索引更新策略

索引空間區(qū)域插入或刪除數(shù)據(jù)時(shí)，可能帶來索引節(jié)點(diǎn)的分類或合并。其中節(jié)點(diǎn)的分裂和合并包括上層四叉樹節(jié)點(diǎn)的更新和各四叉樹節(jié)點(diǎn)對應(yīng)R樹的更新。

圖3 HQR－Tree更新

如圖3（a）所示，當(dāng)空間S中插入新的空間數(shù)據(jù)r10時(shí)，四叉樹節(jié)點(diǎn)S分裂成S0，S1，S2，S3，S4。相應(yīng)的空間S所對應(yīng)的R樹將分裂成五個(gè)不同的子R樹:R0，R1，R2，R3，R4，如圖3（b）所示。反之，若刪除空間數(shù)據(jù)r10，則四叉樹節(jié)點(diǎn)S0，S1，S2，S3，S4合并成一個(gè)節(jié)點(diǎn)S；同時(shí)各四叉樹節(jié)點(diǎn)對應(yīng)的R樹R0，R1，R2，R3，R4也合并成一棵R樹。

（1）數(shù)據(jù)插入

（2）數(shù)據(jù)刪除

5 實(shí)驗(yàn)及分析

5.1 實(shí)驗(yàn)環(huán)境設(shè)置

本實(shí)驗(yàn)比較集中式環(huán)境下和分布式環(huán)境下處理大規(guī)模數(shù)據(jù)。

集中式環(huán)境:操作系統(tǒng):Windows 7；CPU:英特爾酷睿i5－2300CPU ＠ 2.80GHz（單 核）；內(nèi) 存:1GB ，DDR3，單通道 ；硬盤:希捷ST31000524AS，7200轉(zhuǎn) ，1000GB。

分布式環(huán)境:一臺主節(jié)點(diǎn)，三臺從節(jié)點(diǎn)，Ip分別為10.196.80.90／91／92／93。

操作系統(tǒng)均為Oracle Linux Server release 6.3，hadoop版本:1.0.4。其中主節(jié)點(diǎn)內(nèi)存為1G，從節(jié)點(diǎn)為1G、1.5G、2G不等。CPU主節(jié)點(diǎn)為英特爾單核2.60GHz、從節(jié) 點(diǎn) 為 英 特 爾 雙 核 3.20GHz、 雙 核 1.60GHz、 單核2.66GHz。

實(shí)驗(yàn)程序?qū)崿F(xiàn):Myeclipse10.6，JDK1.6。

5.2 索引創(chuàng)建

實(shí)驗(yàn)采用隨機(jī)生成的10萬、20萬、50萬、100萬、200萬、500萬、800萬、1000萬8組空間數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，分別測試在集中式環(huán)境下和分布式環(huán)境下建立索引所耗費(fèi)的時(shí)間，用以分析比較并行計(jì)算和集中式計(jì)算的效率。其中四叉樹節(jié)點(diǎn)容量為512KB。

如圖4所示為集中式和分布式環(huán)境下創(chuàng)建QR樹的對比關(guān)系。其中橫坐標(biāo)為實(shí)驗(yàn)數(shù)據(jù)量，縱坐標(biāo)位創(chuàng)建索引所需的時(shí)間。在分析8組隨機(jī)空間數(shù)據(jù)可得，在數(shù)據(jù)量較小時(shí)，集中式創(chuàng)建索引較有優(yōu)勢。這是因?yàn)?，使用分布式?jì)算時(shí)，需要花費(fèi)時(shí)間進(jìn)行數(shù)據(jù)的分割和計(jì)算節(jié)點(diǎn)的通信，而單機(jī)環(huán)境下不存在此問題。但是，當(dāng)數(shù)據(jù)量開始變大時(shí)，如上實(shí)驗(yàn)，當(dāng)本實(shí)驗(yàn)環(huán)境下，在數(shù)據(jù)量超過500萬時(shí)，分布式環(huán)境在為空間數(shù)據(jù)建立索引時(shí)已經(jīng)開始比集中是創(chuàng)建索引具有優(yōu)勢。此時(shí)，隨著數(shù)據(jù)量的增大，計(jì)算節(jié)點(diǎn)的通信開銷及數(shù)據(jù)分割的開銷對建索引效率的影響將越來越低。

圖4 隨機(jī)數(shù)據(jù)在集中式環(huán)境和分布式環(huán)境下建立索引耗時(shí)圖 （單位:ms）

5.3 隨機(jī)數(shù)據(jù)查詢

隨機(jī)數(shù)據(jù)查詢實(shí)驗(yàn)采用500萬個(gè)數(shù)據(jù)的索引作為實(shí)驗(yàn)數(shù)據(jù)，分別在集中是環(huán)境下和分布式環(huán)境下進(jìn)行查詢。查詢次數(shù)為 （單位:次）:10，100，1000，1萬，10萬，20萬，50萬，100萬。

圖5 隨機(jī)數(shù)據(jù)在集中式環(huán)境和分布式環(huán)境下查詢耗時(shí)圖 （單位:ms）

圖5 所示為隨機(jī)數(shù)據(jù)在集中是環(huán)境和分布式環(huán)境下查詢的耗時(shí)，其中縱坐標(biāo)為查詢時(shí)間，橫坐標(biāo)為查詢次數(shù)。與建索引時(shí)類似，當(dāng)查詢次數(shù)較少時(shí)，單機(jī)查詢耗時(shí)要小于分布式環(huán)境下耗時(shí)，但當(dāng)次數(shù)增加到1000次及以上時(shí)，分布式環(huán)境下的隨機(jī)數(shù)據(jù)查詢耗時(shí)開始優(yōu)于集中是環(huán)境。

6 結(jié)束語

HQR－Tree是一種基于Hadoop的分布式QR樹索引方法，用于處理海量空間數(shù)據(jù)。QR樹作為兩層索引結(jié)構(gòu)結(jié)合了四叉樹和R樹的優(yōu)點(diǎn)，但由于其結(jié)構(gòu)復(fù)雜，創(chuàng)建與維護(hù)代價(jià)大。通過研究發(fā)現(xiàn)，在分布式環(huán)境下建立QR樹，將計(jì)算量分散到各個(gè)計(jì)算節(jié)點(diǎn)中分別處理，可以有效降低算法響應(yīng)時(shí)間，對處理海量空間數(shù)據(jù)具有良好的表現(xiàn)，大大提高數(shù)據(jù)處理效率。本文基于Hadoop平臺，結(jié)合MapReduce的思想，設(shè)計(jì)優(yōu)化了分布式環(huán)境下QR樹索引算法的建立和查詢過程 （包括點(diǎn)查詢和區(qū)域查詢）。理論分析與實(shí)驗(yàn)結(jié)果表明，HQR－Tree的分布式算法在時(shí)間復(fù)雜度優(yōu)于QR－Tree。本文的進(jìn)一步研究將針對HDFS文件系統(tǒng)的特點(diǎn)及動(dòng)態(tài)數(shù)據(jù)的問題進(jìn)行設(shè)計(jì)相應(yīng)的解決方案進(jìn)一步優(yōu)化HQR樹性能。

[1]Lee M W，Hwang S.Robust distributed indexing for localityskewed workloads[C]／／Proceedings of the 21st ACM International Conference on Information and Knowledge Management.ACM，2012:1342－1351.

[2]Wang J，Wu S，Gao H，et al.Indexing multi－dimensional data in a cloud system[C]／／Proceedings of the International Conference on Management of Data.ACM，2010:591－602.

[3]Wu S，Jiang D，Ooi B C，et al.Efficient b－tree based indexing for cloud data processing[J].Proceedings of the VLDB Endowment，2010，3 （1－2）:1207－1218.

[4]Zhu M，Shen D，Kou Y，et al.An adaptive distributed index for similarity queries in metric spaces[G].LNCS7418:Web－Age Information Management.Berlin:Springer Berlin Heidelberg，2012:222－227.

[5]Wang J，Wu S，Gao H，et al.Indexing multi－dimensional data in a cloud system[C]／／Proceedings of the International Conference on Management of Data.ACM，2010:591－602.

[6]Wu S，Jiang D，Ooi B C，et al.Efficient b－tree based indexing for cloud data processing[J].Proceedings of the VLDB Endowment，2010，3 （1－2）:1207－1218.

[7]Huang B，Wu Q.A spatial indexing approach for high performance location based services[J].Journal of Navigation，2007，60 （1）:83－94.

[8]Pelanis M，Saltenis S，Jensen C S.Indexing the past，present，and anticipated future positions of moving objects[J].ACM Transactions on Database Systems，2006，31 （1）:255－298.

[9]Zimek A，Schubert E，Kriegel H P.A survey on unsupervised outlier detection in high－dimensional numerical data[J].Statistical Analysis and Data Mining，2012，5 （5）:363－387.

[10]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.

[11]Apache.Welcome to ApacheTMHadoop ！[EB／OL].[S].[2012－03－19].http:／／hadoop.apache.org／.

[12]GUO Wei.Spatial database indexing techniques[M].Shanghai:Shanghai Jiaotong University Press，2006:129－143 （in Chinese）.[郭薇.空間數(shù)據(jù)庫索引技術(shù)[M].上海:上海交通大學(xué)出社，2006:129－143.]