勞潔瑩，孫志磊

(浙江工業(yè)大學(xué) 信息化辦公室，浙江 杭州 310014)

一種改進(jìn)的嵌入式電子地圖空間索引

勞潔瑩，孫志磊

(浙江工業(yè)大學(xué) 信息化辦公室，浙江 杭州 310014)

摘要：空間索引在嵌入式設(shè)備中有廣泛的應(yīng)用，按照不同的空間映射方式，可以分為不同的索引方法，如二叉樹索引、網(wǎng)格索引、四叉樹索引和R樹索引及其變種，指出了各種空間索引的利弊和適用環(huán)境.目前嵌入式系統(tǒng)中硬件資源不足，人們對其功能的需求卻在不斷的增加，因此如何快速的檢索到需要的空間數(shù)據(jù)以滿足相應(yīng)的功能成為了一個(gè)亟需的問題.根據(jù)各個(gè)索引方法優(yōu)勢以及其相關(guān)的使用環(huán)境，提出了一種四叉樹和R*-樹相結(jié)合的空間索引—QR*-樹索引，此空間索引雖然在存儲空間上比R*樹略有增加，但是在插入、刪除、查找等操作中的性能遠(yuǎn)遠(yuǎn)優(yōu)于R*-樹，非常適合作為嵌入式系統(tǒng)的數(shù)據(jù)庫空間索引，最后在S3C2440平臺上驗(yàn)證了其有效性.

關(guān)鍵詞：電子地圖；QR*-樹；嵌入式系統(tǒng)

An improved spatial index method for embedded electronic map

LAO Jieying, SUN Zhilei

(Information Manager, Zhejiang University of Technology, Hangzhou 310014, China)

Abstract:Spatial index is widely used in the embedded devices, which can be divided into various different index methods depending on space mapping method, such as binary tree index, grid index, quad tree index and R tree index. The advantages and disadvantages of various spatial index methods and the application environment are pointed out. But the hardware resources in embedded systems are insufficient for meeting the increasing requirements. Therefore, how to quickly retrieve spatial data needed to meet the corresponding function has become an urgent issue. A new spatial index-QR*-tree index method combined with quad tree and R*-tree is proposed in this paper. Although this spatial index has a little increase in storage space than R*- tree, but the performances in the insertion, deletion and search operations are far superior that R*- tree. It’s very suitable for database spatial index in embedded system. The experiments show that the QR*-tree index in the S3C2440 platform has a good performance.

Keywords:electronic map; QR*-tree; embedded system

嵌入式導(dǎo)航設(shè)備由于良好的可移動(dòng)性得到了廣泛的應(yīng)用，但是相對于PC而言，嵌入式設(shè)備的硬件資源比較匱乏，存儲空間較小、處理器的主頻較低.隨著人們需求的不斷增加，嵌入式設(shè)備上需要實(shí)現(xiàn)的功能越來越多，需要同時(shí)實(shí)現(xiàn)地圖的顯示、路徑的尋優(yōu)和興趣點(diǎn)的搜索等功能.近年來，隨著三維電子地圖的出現(xiàn)和國家城鎮(zhèn)化速度的加快，電子地圖的數(shù)據(jù)量大大增加了.因此，如何快速的檢索到需要的空間數(shù)據(jù)以滿足相應(yīng)的功能需求成為了一個(gè)重要的問題.

空間索引是指依據(jù)空間對象的位置和形狀或空間對象之間的某種空間關(guān)系按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)[1].索引是介于算法和數(shù)據(jù)之間的一種輔助的結(jié)構(gòu)，通過它可以排除大量與操作無關(guān)的數(shù)據(jù)，提高檢索的效率.空間索引的優(yōu)劣是衡量一個(gè)嵌入式GIS的重要指標(biāo)[2].GIS經(jīng)歷了40多年的發(fā)展，基于PC的GIS系統(tǒng)已經(jīng)比較成熟，近年來，隨著移動(dòng)導(dǎo)航設(shè)備的飛速發(fā)展，嵌入式GIS成為研究焦點(diǎn).有不少的學(xué)者對空間索引進(jìn)行了研究并提出了一些空間索引算法，如網(wǎng)格索引、四叉樹索引、R-樹索引、R+-樹索引等.不過每種索引方法都有各自的優(yōu)缺點(diǎn)和適應(yīng)的領(lǐng)域，通過對這些索引方法的研究，提出了一種適合嵌入式GIS的空間索引方法—QR*-樹.QR*-樹索引結(jié)構(gòu)結(jié)合了Quadtree(四叉樹)和R*-樹各自的優(yōu)點(diǎn)，將要搜索的領(lǐng)域用四叉樹的結(jié)構(gòu)劃分成為小的單元，然后在每個(gè)小的單元中建立R*-樹索引結(jié)構(gòu)，如此既減少了數(shù)據(jù)量的冗余又提高了檢索的速度.最后使用Android平臺驗(yàn)證了此種索引方法的有效性和實(shí)用性.

1空間索引算法性能對比

GIS經(jīng)歷了多年的發(fā)展，得到了廣泛的應(yīng)用.空間索引是它其中的重要組成部分，決定著GIS性能的好壞，很多學(xué)者對其進(jìn)行了研究，提出了不少的空間索引的方法.對于空間索引，按照不同方式，可以分為不同的類別.從空間目標(biāo)的映射方式不同，可以分為基于空間目標(biāo)排序的索引方法和專門的索引方法；根據(jù)存儲介質(zhì)的不同可以分為內(nèi)存空間索引和外存空間索引；根據(jù)劃分區(qū)間的規(guī)則性，將其分為規(guī)則區(qū)域劃分索引結(jié)構(gòu)和R樹及其變種索引結(jié)構(gòu).

1.1規(guī)則劃分索引結(jié)構(gòu)

規(guī)則劃分索引是指對待建立空間索引的空間領(lǐng)域采用規(guī)則剖分的方法建立起來的空間索引.規(guī)則剖分的形狀多采用便于操作的矩形，由此產(chǎn)生且常用的空間索引有BSP樹索引、網(wǎng)格索引和四叉樹索引.BSP樹結(jié)構(gòu)又稱為二叉樹，即將待建立索引的區(qū)域遞歸的剖分成為規(guī)則的兩個(gè)區(qū)域，直到滿足剖分的停止條件為止.BSP樹索引結(jié)構(gòu)剖分方法比較簡單，易于實(shí)現(xiàn).但是也存在缺點(diǎn)，由于BSP樹節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，若作為大范圍電子地圖的空間索引，BSP樹的深度勢必會(huì)比較大，如此檢索的效率便不高.由于空間物體的分布不均勻，空間剖分時(shí)可能并非等分，如果所形成的BSP樹不平衡，最壞的情況可能退化成為線性索引結(jié)構(gòu)，其檢索效率便會(huì)大大的下降.規(guī)則劃分的空間索引結(jié)構(gòu)應(yīng)用最為廣泛的是網(wǎng)格索引和四叉樹索引.

網(wǎng)格索引的建立方法是將待建立索引的空間區(qū)域均勻的劃分成為R*S矩形單元，空間實(shí)體和網(wǎng)格單元形成了多對多的關(guān)系.即一個(gè)網(wǎng)格單元可能包含多個(gè)空間對象，而一個(gè)空間對象也可能位于多個(gè)網(wǎng)格單元之中.對于每個(gè)網(wǎng)格，可以通過Hilbert編碼將二維映射成為一維，既有利于存儲，也利于查詢.由于Hilbert曲線具有空間聚類性，可以基本保證空間相鄰的網(wǎng)格在存儲空間上亦是相鄰.查詢某個(gè)空間實(shí)體時(shí)，可以通過空間實(shí)體的經(jīng)、緯度坐標(biāo)立刻計(jì)算出它所在的網(wǎng)格，通過網(wǎng)格的行、列號可以立刻計(jì)算出它的Hilbert編碼，然后便可定位該空間實(shí)體所在的存儲空間的位置.由于網(wǎng)格索引是多對多的索引結(jié)構(gòu)，因此它存在數(shù)據(jù)冗余的缺點(diǎn).由于一個(gè)空間實(shí)體可能落入多個(gè)網(wǎng)格之中，因此為了保證每個(gè)網(wǎng)格中數(shù)據(jù)的完整性，多個(gè)網(wǎng)格中都必須存儲該空間實(shí)體的ID，這樣該空間實(shí)體的ID被多次存儲，造成了數(shù)據(jù)冗余，網(wǎng)格劃分越精細(xì)，數(shù)據(jù)的冗余就越多.網(wǎng)格索引作為空間索引的另一大問題是網(wǎng)格劃分的精細(xì)程度非常難以確定.如果劃分得過于細(xì)致，那么會(huì)造成實(shí)體ID數(shù)據(jù)冗余量大增且維護(hù)索引本身的數(shù)據(jù)量也會(huì)增加；而如果網(wǎng)格劃分過于粗略，那么每個(gè)網(wǎng)格中的空間實(shí)體的數(shù)據(jù)量會(huì)較多，不能夠?qū)臻g實(shí)體進(jìn)行精確定位，實(shí)體的檢索效率又會(huì)大大降低[3].

四叉樹索引又稱為四元樹，它的每個(gè)非葉子節(jié)點(diǎn)都有四個(gè)子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)表示一塊區(qū)域，每個(gè)區(qū)域的形狀可以是規(guī)則的矩形或者其它形狀，于1974年由Raphael Finke和J. L. Bentley提出[4].四叉樹可以分為點(diǎn)四叉樹、區(qū)域四叉樹和CIF四叉樹.作為空間索引，區(qū)域四叉樹應(yīng)用最為廣泛.區(qū)域四叉樹索引的建立方法是將待建立空間索引的區(qū)域遞歸的劃分為四個(gè)子區(qū)域，直到滿足劃分的停止條件，子區(qū)域的大小是相等的，劃分的停止條件可以根據(jù)實(shí)際情況而定.每個(gè)區(qū)域中包含了各種的空間實(shí)體，區(qū)域和空間實(shí)體之間也是多對多的映射關(guān)系，即每個(gè)區(qū)域可以包含多個(gè)空間實(shí)體，同時(shí)一個(gè)空間實(shí)體也可能位于多個(gè)區(qū)域之中.MX四叉樹和PR四叉樹是兩種最典型的區(qū)域四叉樹，MX四叉樹是一棵平衡四叉樹，每個(gè)節(jié)點(diǎn)的子空間是均等的，結(jié)構(gòu)比較簡單.MX樹的每個(gè)葉子節(jié)點(diǎn)要么是黑色節(jié)點(diǎn)，表示該節(jié)點(diǎn)空間包含空間實(shí)體；要么是空節(jié)點(diǎn)，表示不包括任何空間實(shí)體數(shù)據(jù).MX四叉樹的主要缺點(diǎn)是對MX四叉樹進(jìn)行更新后，可能會(huì)導(dǎo)致它的深度發(fā)生變化，每個(gè)葉子節(jié)點(diǎn)的位置都會(huì)發(fā)生變化.PR四叉樹是完全的四叉樹，如果其區(qū)域中包含的數(shù)據(jù)點(diǎn)數(shù)多于1，那么就均勻四分該區(qū)域，因此每個(gè)葉子節(jié)點(diǎn)區(qū)域中包含的數(shù)據(jù)點(diǎn)都不會(huì)超過1.空間實(shí)體數(shù)據(jù)的分布不均勻，完全四叉樹作為空間索引會(huì)造成數(shù)據(jù)的嚴(yán)重冗余.在空間實(shí)體稀疏的區(qū)域，會(huì)出現(xiàn)很多空的區(qū)域；在空間實(shí)體分布稠密的區(qū)域，會(huì)出現(xiàn)很多一個(gè)空間實(shí)體落入多個(gè)區(qū)域的情況，造成索引結(jié)構(gòu)數(shù)據(jù)和空間實(shí)體ID數(shù)據(jù)冗余.

1.2R樹及其變種索引

與區(qū)域劃分不同，人們提出了另外一類空間索引結(jié)構(gòu)R樹及其變種.R樹索引結(jié)構(gòu)[5]由學(xué)者Guttman提出，它和B樹比較類似，但是B樹比較適合作為一維數(shù)據(jù)的索引，而R樹比較適合作為高維數(shù)據(jù)的索引.R樹一經(jīng)提出，便在空間索引領(lǐng)域得到了廣泛的應(yīng)用，針對R樹的不足，人們提出了一些R樹的變種索引結(jié)構(gòu)，如R+樹、R*-樹、QR樹、SS樹和X樹等.

R樹是B樹在高維的延伸，它的平衡度高，因此空間利用率比較高.R樹由若干節(jié)點(diǎn)構(gòu)成，R樹的每個(gè)葉子節(jié)點(diǎn)都位于R樹的最底層，并且每個(gè)非葉子節(jié)點(diǎn)包含的子節(jié)點(diǎn)的個(gè)數(shù)有上限和下限，這是為了保持空間的有效利用.每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)最小的包圍盒，此包圍盒是包含該節(jié)點(diǎn)中所有空間對象的最小外接圖形.包圍盒的形狀可以是規(guī)則的矩形、圓形或者其他圖形.每個(gè)節(jié)點(diǎn)中包含了一個(gè)引用，此引用指向該節(jié)點(diǎn)的孩子節(jié)點(diǎn)或者該節(jié)點(diǎn)包含的空間實(shí)體的數(shù)據(jù).如圖1所示，有8個(gè)實(shí)體，每個(gè)實(shí)體的外接矩形編號是從4~11，編號為1，2，3的矩形分別表示它們的包圍盒，1號包圍盒包含了實(shí)體6，7，8；2號包圍盒包含了實(shí)體9，10，11；3號包圍盒包含了實(shí)體4，5.每個(gè)包圍盒對應(yīng)R樹中的一個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)構(gòu)成的R樹索引結(jié)構(gòu)如圖2所示，0號節(jié)點(diǎn)表示根節(jié)點(diǎn)，它有3個(gè)子節(jié)點(diǎn)，分別為1，2，3.節(jié)點(diǎn)4~1都是葉子節(jié)點(diǎn).

圖1　空間實(shí)體分布及包圍盒Fig.1　The distribution of spatial entity and bounding box

圖2　R樹索引結(jié)構(gòu)圖Fig.2　R-tree index structure

R樹索引的存儲效率相對較高，檢索的效率也較高，檢索的時(shí)間復(fù)雜度為logN.但是R樹也存在弊端，它的主要缺陷是節(jié)點(diǎn)的包圍盒區(qū)域相互重疊，重疊的區(qū)域面積和次數(shù)與空間實(shí)體的分布均勻度成反比，與空間的數(shù)量成正比.包圍盒重疊會(huì)影響空間實(shí)體的檢索效率，當(dāng)要檢索的空間實(shí)體位于幾個(gè)包圍盒的重疊區(qū)域以內(nèi)，那么在檢索該空間實(shí)體時(shí)，這幾個(gè)包圍盒都需要查詢，就降低了檢索的效率，并且檢索的時(shí)間也沒法準(zhǔn)確的估計(jì).為了解決這個(gè)問題，人們提出了R樹一些變種.典型的有R+樹、R*-樹.R+樹是由Sellis等于1987年提出的，它結(jié)合了R樹和KDB的優(yōu)點(diǎn)，規(guī)定R樹的所有葉子節(jié)點(diǎn)的包圍盒不能夠有重疊情況[6].如果有存在包圍盒重疊的情況，那么就將包圍盒劃分為多個(gè)包圍盒.由于接近了包圍盒重疊的情況，因此空間實(shí)體的檢索效率提高了，但是用于維護(hù)空間索引的數(shù)據(jù)量增加了，并且對空間索引結(jié)構(gòu)的更新變得非常的復(fù)雜和繁瑣.Beckmann等于1990年提出了另外一種R樹的變種—R*-樹，此種索引結(jié)構(gòu)仍然允許包圍盒的空間重疊，但是它優(yōu)化了節(jié)點(diǎn)分裂的方式，提出了強(qiáng)制重新插入的技術(shù)，在一定程度上提高了檢索的性能，但是作為高維的空間索引，性能仍然不能夠達(dá)到要求[7].

人們還提出了一些其他的R樹索引的變種，如SS樹和X樹等.SS樹的特點(diǎn)是，它的包圍盒是圓不是矩形，對鄰近元素的查詢效率提高了，并且節(jié)省了存儲空間.但是操作起來非常復(fù)雜[8].X樹結(jié)合了R樹和線型數(shù)組的優(yōu)點(diǎn)，在一定程度上減少了包圍盒重疊的情況，但由于X樹中的超級節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)不定，在高維的空間索引中，檢索效率不高.

2四叉樹和R*樹的組合索引

現(xiàn)實(shí)世界豐富多彩，空間實(shí)體的數(shù)量巨大且分布非常的不均勻；嵌入式系統(tǒng)的資源非常有限，存儲空間小、處理速度慢，因此作為嵌入式系統(tǒng)的空間索引需要考慮時(shí)間和空間的利用率，權(quán)衡它們之間的關(guān)系.R樹系列的索引常常作為空間索引，特別是R*-樹，不過雖然R*-樹在一定程度上減少了包圍盒區(qū)域重疊的情況，但是R*-樹非葉子節(jié)點(diǎn)的包圍盒區(qū)域重疊情況還是在所難免，并且會(huì)隨著空間實(shí)體數(shù)量的增加而增加.綜合考慮時(shí)空的利用率，提出了一種規(guī)則劃分和R樹索引相結(jié)合的空間索引方法—QR*-樹.QR*-樹結(jié)合了四叉樹和R*樹的優(yōu)點(diǎn).首先對空間區(qū)域建立四叉樹索引，然后在每個(gè)小的四叉樹節(jié)點(diǎn)單元區(qū)域中建立R*-樹索引，將R*-樹索引的搜索空間限定在了一個(gè)小的區(qū)域當(dāng)中，減少了R*-樹索引中的重疊情況，同時(shí)減少了四叉樹的數(shù)據(jù)冗余.

2.1QR*樹空間索引結(jié)構(gòu)

QR*-樹是一種組合的空間索引，它融合了四叉樹和R*-樹的思想.QR*-樹由一棵區(qū)域四叉樹QT和m棵R*-樹組成，m可表示為

其中：d為空間的維度；k為區(qū)域四叉樹的深度.區(qū)域四叉樹有m個(gè)節(jié)點(diǎn)，分別用QT0，QT1，…，QTm-1表示.此區(qū)域四叉樹將要研究的空間區(qū)域S剖分成了m個(gè)k級的子空間，每個(gè)子空間等級由高到低分別用S0，S1，…，Sm-1表示，其中S=S0，每個(gè)級別的子空間相互之間不相交且并集等于S.

圖3　空間剖分實(shí)例圖Fig.3　The instance of space partition

圖4　實(shí)例QR*-樹空間索引結(jié)構(gòu)圖Fig.4　The instance of QR*- tree spatial index structure

非葉子節(jié)點(diǎn)：,,…,>

葉子節(jié)點(diǎn)：,,…,>

其中：RANK表示該節(jié)點(diǎn)在R*-樹中的等級；NUM表示包含的子節(jié)點(diǎn)或者空間對象的數(shù)量；C_Pi為指向該節(jié)點(diǎn)孩子節(jié)點(diǎn)的指針；MBRi表示孩子節(jié)點(diǎn)或者空間實(shí)體的最小外接矩形；O_Pi表示空間實(shí)體的指針或者空間實(shí)體標(biāo)識.

2.2基本操作

空間索引的優(yōu)劣通常使用它的更新和查詢操作效率來衡量，提出的QR*-樹索引結(jié)合了兩種索引的思想，因此各種操作也略微復(fù)雜一點(diǎn).

2.2.1查找

空間查找中最典型的便是區(qū)域查找.首先給定一個(gè)查找的區(qū)域SS，查找與區(qū)域SS相交或者完全落入SS中的空間實(shí)體.區(qū)域查找必須遍歷所有與給定區(qū)域SS相交的子空間所對應(yīng)的R*-樹索引.查找的過程為：從QR*樹的根節(jié)點(diǎn)開始，對每個(gè)四叉樹節(jié)點(diǎn)，遍歷其子節(jié)點(diǎn)，若子節(jié)點(diǎn)對應(yīng)的空間與SS不相交，則不用再查找該條支路；若子節(jié)點(diǎn)對應(yīng)的空間與SS相交，且SS與對應(yīng)的空間索引R*-樹也相交，那么在該R*-樹中繼續(xù)查找；然后遞歸的調(diào)用如上方法，遍歷所有的四叉樹節(jié)點(diǎn).

如圖3所示，查找與區(qū)域SS相交或者完全落入SS中的空間實(shí)體，步驟如下：

2)S0的子空間S1，S3，S4，S與區(qū)域SS不相交，因此排除它們及其子區(qū)域.

查找算法Search(R,SS)(其中：R表示QR*-樹的根節(jié)點(diǎn)；SS表示要查找的空間區(qū)域)：

1) 集合S表示所有根節(jié)點(diǎn)的子空間(包括根節(jié)點(diǎn)的空間)的并集.

2) 如果S中所有元素都與SS都不相交，則返回沒有滿足要求的空間實(shí)體.

4) 對所有節(jié)點(diǎn)遞歸的調(diào)Search(R.C_P,SS).

通過以上查找步驟表明：QR*-樹的查找，先從四叉樹開始，再到子空間對應(yīng)的R*樹.

2.2.2插入

1) 如果R是葉子節(jié)點(diǎn)，則直接調(diào)用R*-樹的插入算法插入M即可.

2) 如果R是非葉子節(jié)點(diǎn)，那么查找R的所有子節(jié)點(diǎn)空間，找出包含M的最小的子空間Si，然后調(diào)用Insert(Si, M)；若不能夠在R的子空間中找到包含M的最小空間，則將M插入到根節(jié)點(diǎn)中.

2.2.3刪除

1) 如果R為葉子節(jié)點(diǎn)，則直接調(diào)用R*-樹的刪除算法刪除M即可.

2) 如果R為非葉子節(jié)點(diǎn)，那么查找R的所有子節(jié)點(diǎn)空間，找出包含M的最小的子空間Si，然后調(diào)用Delete(Si,M)；若不能夠在R的子空間中找到包含M的最小空間，則從根節(jié)點(diǎn)中刪除M.

3實(shí)驗(yàn)評估

將提出的改進(jìn)空間索引QR*-樹與R*樹索引進(jìn)行對比，驗(yàn)證QR*樹作為空間索引的優(yōu)勢.實(shí)驗(yàn)環(huán)境的硬件平臺以S3C2440為微處理器，其主頻為400 MHz，其他的硬件配置為：128 M MDDR，256 M Nand Flash和8 G SD卡.軟件平臺采用Android2.2.實(shí)驗(yàn)數(shù)據(jù)采用杭州的電子地圖，實(shí)驗(yàn)結(jié)果如表1所示，其中l(wèi)eveli表示QR*樹索引中四叉樹的深度為i.從表1中可以看出：QR*樹索引每項(xiàng)所占的存儲空間比R*-樹略大一點(diǎn)，其存儲的開銷隨著四叉樹的增加而增加，但是增加的幅度并沒有太多.而對空間索引的各種操作：插入、刪除、查詢，QR*-樹空間索引比R*-樹空間索引所涉及的存儲空間都要少，并且在四叉樹深度不是太大的情況下，四叉樹深度越大，各種操作性能越好.

表1　QR*-樹與R*-性能對照

4結(jié)論

QR*-樹索引結(jié)合了四叉樹和R*-樹的優(yōu)點(diǎn)，是由一棵四叉樹和若干棵R*-樹組成.由于空間實(shí)體的分布往往是不均勻的，某些空間的R*-樹索引包含的實(shí)體數(shù)量會(huì)比較少，QR*-樹索引所占的存儲空間比R*-樹略大，但是在插入、刪除、查找等方面的性能遠(yuǎn)遠(yuǎn)優(yōu)于R*-樹且數(shù)量越多，優(yōu)越性越明顯.最后，實(shí)驗(yàn)證明QR*-樹空間索引非常適合作為嵌入式系數(shù)據(jù)庫的空間索引.

參考文獻(xiàn)：

[1]沈永增,王燕,鄭曄.基于ARM-Linux導(dǎo)航電子地圖數(shù)據(jù)模型[J].浙江工業(yè)大學(xué)學(xué)報(bào),2010,38(2):186-191.

[2]沈永增,姚萌萌,周巍.空間數(shù)據(jù)在嵌入式導(dǎo)航系統(tǒng)中的索引[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2010,19(4):85-87.

[3]趙波,邊馥苓.面向移動(dòng)GIS的動(dòng)態(tài)四叉樹空間索引算法[J].計(jì)算機(jī)工程,2007,33(15):86-87.

[4]維基百科.四叉樹[EB/OL].[2013-03-13].http://zh.wikipedia.org/wiki/四叉樹.

[5]黃曉明,楊紅雨.基于R樹的空管GIS數(shù)據(jù)模型索引的設(shè)計(jì)[J].微計(jì)算機(jī)信息,2008,24(8):144-146.

[6]SELLIS T K, ROUSSOPOULOS N,FALOUTSOS C. The R+-tree :a dynamic index for multi-dimensional objects[C]//Proceedings of the 13th VLDB.Brighton,England：The Proceedings of the VLDB Endowment，1987:507-518.

[7]BECKMANN N,KRIEGEL H P,SCHNEIDER R, et al. The R*-tree:an efficient and robust access method for points and rectangles[C]//Proceedings of SIGMOD.Anlantic City,New Jersey：ACM SIGMOD,1990：322-331.

[8]薄樹奎.空間數(shù)據(jù)庫中最近鄰和反最近鄰查詢技術(shù)的研究[D].秦皇島:燕山大學(xué),2004.

(責(zé)任編輯：劉巖)

中圖分類號：TP399

文獻(xiàn)標(biāo)志碼：A

文章編號：1006-4303(2015)03-0340-06

作者簡介：勞潔瑩(1980—)，女，浙江杭州人，工程師，主要從事應(yīng)用研究，E-mail：ljy@zjut.edu.cn.

基金項(xiàng)目：浙江省教育廳科研項(xiàng)目(20130251)

收稿日期：2014-12-15