一種顧及導(dǎo)航數(shù)據(jù)屬性的K-DA樹索引方法

楊佳穎，毛 健，崔鐵軍，劉朋飛

（天津師范大學(xué)地理與環(huán)境科學(xué)學(xué)院，天津 300387）

現(xiàn)實世界中有許多數(shù)據(jù)與空間位置相關(guān)，而空間索引是一種依據(jù)空間對象的位置和形狀或空間對象間某種空間關(guān)系，按照一定順序排列的數(shù)據(jù)結(jié)構(gòu)，對海量空間數(shù)據(jù)進(jìn)行篩選，進(jìn)而提高空間操作速度和效率的方法.空間索引方法的選擇直接決定了地理空間數(shù)據(jù)檢索的整體性能.

導(dǎo)航體驗的好壞主要取決于導(dǎo)航數(shù)據(jù)的顯示效率，而導(dǎo)航數(shù)據(jù)顯示的核心是道路.道路又分為不同等級，不同等級的道路是否顯示取決于當(dāng)前用戶選擇的地圖顯示范圍.當(dāng)?shù)貓D顯示的范圍較大時，導(dǎo)航顯示較高等級的道路；當(dāng)?shù)貓D顯示范圍較小時，則顯示該區(qū)域內(nèi)的詳細(xì)道路.傳統(tǒng)空間索引往往僅依據(jù)當(dāng)前選擇范圍指導(dǎo)系統(tǒng)讀取該當(dāng)前范圍內(nèi)所有等級的道路數(shù)據(jù)，而并不是所需顯示等級的道路數(shù)據(jù)，導(dǎo)致導(dǎo)航數(shù)據(jù)讀取時間過長，效率降低，因此導(dǎo)航數(shù)據(jù)的讀取時間是影響導(dǎo)航數(shù)據(jù)顯示效率的關(guān)鍵.道路等級存在于導(dǎo)航數(shù)據(jù)的屬性中，如果能在傳統(tǒng)空間索引的檢索中加入對道路等級屬性的判讀，僅讀取需要顯示的等級道路勢必會提高導(dǎo)航數(shù)據(jù)的顯示效率.導(dǎo)航數(shù)據(jù)的多級顯示可以通過劃分道路等級來實現(xiàn)，而道路等級信息存在于導(dǎo)航數(shù)據(jù)的屬性中，因此，傳統(tǒng)空間索引與屬性索引相結(jié)合可以在多尺度顯示的前提下提高導(dǎo)航數(shù)據(jù)的索引效率.傳統(tǒng)的屬性索引依靠關(guān)鍵字來進(jìn)行檢索，多用于B+樹索引，它與空間索引是2種不同的索引形式，雖然屬性索引和空間索引的發(fā)展都已經(jīng)相對成熟，但二者結(jié)合的應(yīng)用還較少[1-2].現(xiàn)有的空間索引方法通常只考慮空間位置，對于導(dǎo)航數(shù)據(jù)的多級顯示特點未給予足夠支持[3-4].本研究從傳統(tǒng)空間索引K-D入手，結(jié)合導(dǎo)航數(shù)據(jù)道路等級屬性，構(gòu)建一種顧及屬性的空間索引機制，在保證索引效率的同時，減少當(dāng)數(shù)據(jù)目標(biāo)較大時系統(tǒng)產(chǎn)生的數(shù)據(jù)冗余.

1 傳統(tǒng)K-D樹空間索引技術(shù)

K-D樹是Bentley[5]在1975年提出的一種二叉索引樹，它支持k維空間點數(shù)據(jù)，每個K-D樹的節(jié)點根據(jù)大小將所表示的k維空間分為大于節(jié)點值和小于節(jié)點值兩部分，每個節(jié)點中都分散存儲了空間點數(shù)據(jù).此外，K-D樹繼承了二叉索引樹簡單、索引效率高的特點.一棵完整的K-D樹的節(jié)點描述包括中間節(jié)點（COUNT，DEPTH，＜CP1，MBR1＞，＜CP2，MBR2＞）和葉子節(jié)點（COUNT，DISLEVEL，＜OI1，MBR1＞，＜OI2，MBR2＞，…，＜OIM，MBRM＞）.其中＜OIi，MBRi＞為數(shù)據(jù)項；OIi為空間對象標(biāo)識；MBRi為該空間對象在k維空間中的最小外接矩形；CPi和MBRi為索引項，CPi為指向子樹根節(jié)點的指針，MBRi表示其子樹索引空間.COUNT≤M表示該節(jié)點中索引項或空間對象的個數(shù)，DEPTH表示該節(jié)點在樹中的深度.若m和M分別為索引項或數(shù)據(jù)集的最小和最大個數(shù)，H為樹的深度，N為空間對象總個數(shù)，則H∈[logmN，logMN]，LEVEL≤H.K-D樹的具體實現(xiàn)形式如圖1所示，其中A點為根節(jié)點，包含了指向左、右兩棵子樹的指針；B、C和G為中間節(jié)點，包含了指向父節(jié)點的指針和指向其左、右兩棵子樹的指針；D、E、F、H和I為葉節(jié)點，包含了指向父節(jié)點的指針以及數(shù)據(jù)的地址等信息.

圖1 K-D樹的形式Fig.1 Form of K-D tree

K-D樹屬于動態(tài)索引結(jié)構(gòu)，為非平衡樹[6].同時，K-D樹在每一層的分枝決策都可以通過該層的分辨器對相應(yīng)對象進(jìn)行實現(xiàn)，并以此類推，在各維中不斷劃分，直至某一節(jié)點中的點數(shù)小于給定的最大點數(shù)，結(jié)束這種劃分.劉宇等[7]對此問題加以研究，對本研究具有一定的指導(dǎo)意義.隨著嵌入式導(dǎo)航的快速發(fā)展，國內(nèi)外學(xué)者在以上幾種空間索引的基礎(chǔ)上，結(jié)合嵌入式導(dǎo)航數(shù)據(jù)的特點，進(jìn)行了一系列研究和改進(jìn).劉春等[8]研究了道路數(shù)據(jù)的空間組織，分析了路網(wǎng)的3個描述層次，并概括了路網(wǎng)的基本組成要素和用來描述路網(wǎng)的數(shù)據(jù)集，同時采用K-D樹進(jìn)行空間索引和組織，組成路網(wǎng)的主要要素道路節(jié)點.由于K-D樹實現(xiàn)算法簡單，且符合導(dǎo)航數(shù)據(jù)通過不同等級屬性（尤其是道路等級）的對比進(jìn)行篩選的特點，可以大幅提高空間索引的效率.

2 顧及屬性的空間索引構(gòu)建

2.1 設(shè)計思想

根據(jù)導(dǎo)航數(shù)據(jù)中不同等級道路顯示取決于當(dāng)前地圖顯示范圍的特點，在不改變傳統(tǒng)空間數(shù)據(jù)存儲結(jié)構(gòu)的前提下，將道路等級屬性嵌入到K-D樹索引中，在依據(jù)用戶選擇進(jìn)行檢索時，使新空間索引不僅進(jìn)行空間范圍的判斷，同時進(jìn)行簡單道路等級的判斷，從而進(jìn)一步減少導(dǎo)航數(shù)據(jù)的讀取量，提高導(dǎo)航數(shù)據(jù)的顯示效率.

2.2 基本算法

K-DA樹的構(gòu)建過程如圖2所示.

圖2 顧及屬性情況下K-DA樹的構(gòu)建過程Fig.2 Construction of the K-DA tree in view of the attributes

（1）首先定義一棵完整的K-D樹，這棵樹具有傳統(tǒng)K-D樹索引的形式，葉節(jié)點中不帶有屬性信息（如圖2中黑色部分所示）.

（2）在樹的葉節(jié)點中添加屬性信息（如圖2中紅色部分所示）.

（3）為使屬性判定盡量上移，需要從葉子節(jié)點開始，遞歸構(gòu)建每個節(jié)點的屬性信息，直至根節(jié)點.一般過程為：若同一棵子樹的2個葉節(jié)點所包含的屬性信息一致，則將該屬性信息移至這2個葉節(jié)點對應(yīng)的父節(jié)點處，如屬性信息不一致，則父節(jié)點屬性為null.如圖2中紅色部分所示，設(shè)H和I兩葉節(jié)點所包含的屬性信息一致，均為att1，則其父節(jié)點G的屬性信息為att1；而D和E兩葉子節(jié)點屬性信息不同，則其父節(jié)點B的屬性為null，以此類推直到根節(jié)點A.

構(gòu)建完成后，K-DA樹的節(jié)點由中間節(jié)點（COUNT，DEPTH，＜CP1，MBR1，ATT1＞，＜CP2，MBR2，ATT2＞）和葉子節(jié)點（COUNT，DISLEVEL，＜OI1，MBR1，ATT1＞，＜OI2，MBR2，ATT2＞，…，＜OIM，MBRM，ATTM＞）組成.其中＜OIi，MBRi＞為數(shù)據(jù)項；OIi為空間對象標(biāo)識；MBRi為該空間對象在k維空間中的最小外接矩形；ATTi為葉節(jié)點中儲存的屬性；＜CPi，MBRi＞為索引項，CPi為指向子樹根節(jié)點的指針，MBRi代表其子樹索引空間；COUNT≤M代表該節(jié)點中索引項或空間對象的個數(shù)；DEPTH表示該節(jié)點在樹中的深度.若m和M分別為索引項或數(shù)據(jù)集的最小和最大個數(shù)，H為樹的深度，N為空間對象總個數(shù)，則H∈[logmN，logMN]，LEVEL≤H.

2.2.1 K-DA樹的算法思路

構(gòu)建K-DA樹算法的主要步驟為：

（1）對每個對象構(gòu)建最小外包矩形：根據(jù)外包矩形的構(gòu)建方法，對每個對象（每條道路）建立最小外包矩形，當(dāng)有一個對象小于特定值導(dǎo)致最小外包矩形很小時，對它及其相鄰的對象放在一起構(gòu)造最小外接矩形.

（2）構(gòu)建整體的最小外包矩形：根據(jù)已構(gòu)建好的若干對象的最小外包矩形，通過獲取將要包含的最小外包矩形的min x、max x、min y和max y，逐個構(gòu)造出包含所有對象的最小外包矩形.

（3）構(gòu)造子樹：設(shè)定K-DA樹的最大深度maxdepth，判定條件為若當(dāng)前深度小于樹的最大深度，葉節(jié)點的最小對象數(shù)要大于2，且滿足外包矩形的面積大于最小閾值或?qū)ο罅斜頂?shù)大于5，則通過比較當(dāng)前對象最小外包矩形中點的x1與所得最小外包矩形中點的x2，將x1小于x2的對象放入左子樹objBuckets[0]，將x1大于x2的對象放入右子樹objBuckets[1]，再分別對左右子樹進(jìn)行類似判斷，繼續(xù)劃分左右子樹直至葉節(jié)點，其中，葉節(jié)點中存儲了地址和屬性信息.

（4）如果不滿足判定條件，則當(dāng)前節(jié)點為葉節(jié)點.

（5）當(dāng)節(jié)點被判定為葉節(jié)點后，將屬性嵌入葉節(jié)點中，當(dāng)一棵子樹2個葉節(jié)點所嵌入的屬性相同時，則將葉節(jié)點中的屬性嵌入至這2個葉節(jié)點對應(yīng)子樹的父節(jié)點中.具體構(gòu)建算法為

2.2.2 索引查詢過程

（1）構(gòu)建用戶所要求的窗口，從K-DA樹的根節(jié)點開始由上至下進(jìn)行遞歸查詢.如有節(jié)點的對象不為空（即節(jié)點中包含道路對象），則將其判定為葉節(jié)點.此時開始依次判斷葉節(jié)點中道路對象的最小外接矩形是否與用戶要求的窗口有相交部分.如果有相交部分，則將該葉節(jié)點中的屬性（道路等級）與用戶要求的屬性（道路等級）進(jìn)行對比.如屬性（道路屬性）匹配，則將葉節(jié)點對應(yīng)的數(shù)據(jù)輸出；如屬性（道路等級）不匹配，則不輸出葉節(jié)點對應(yīng)的數(shù)據(jù).如果葉節(jié)點中道路對象的最小外接矩形與用戶要求的窗口沒有相交部分，則不輸出對應(yīng)的數(shù)據(jù).以上過程將“先讀取后判斷”轉(zhuǎn)化為“先判斷再讀取”，避免了冗余數(shù)據(jù)的讀取.

（2）當(dāng)某節(jié)點中的對象為空時（即節(jié)點中不包含道路對象），其不是葉節(jié)點，而是中間節(jié)點，也稱非葉節(jié)點.在非葉節(jié)點的情況下，判斷非葉節(jié)點的最小外接矩形與用戶要求的窗口是否有相交部分.如果有相交部分，則繼續(xù)判斷非葉節(jié)點中的屬性（道路等級）和用戶要求的屬性（道路等級）是否匹配.如果屬性（道路等級）匹配，則繼續(xù)向下查詢子節(jié)點時不需要再對比屬性；如果非葉節(jié)點中的屬性為空，證明該節(jié)點2個子節(jié)點的屬性不一樣，則繼續(xù)向下查詢子節(jié)點.如果非葉節(jié)點的最小外接矩形與用戶要求的窗口沒有相交部分，則停止查詢，依次類推.

以上過程的具體實現(xiàn)算法為

3 實驗

3.1 實驗方法

（1）硬件條件：實驗所用嵌入式設(shè)備處理器為四核，運算速度為1.2 GHz；運行內(nèi)存為2 GB；手機儲存為16 GB.

（2）軟件條件：java編程軟件為eclipse，需Android 4.4.4平臺.

（3）數(shù)據(jù)來源：天津地區(qū)的導(dǎo)航數(shù)據(jù)，其中道路總數(shù)99 369條，共分8個等級.

（4）測試方案：為了測評K-DA樹的性能，在Android平臺分別編寫K-D與K-DA樹索引方法的java代碼.按照查詢的空間對象個數(shù)，共分8組數(shù)據(jù)，并對比相同查詢范圍內(nèi)，傳統(tǒng)索引與顧及屬性新索引的耗時.每組數(shù)據(jù)測試10次，取其平均值作為最終結(jié)果.每次實驗均需重啟程序，避免內(nèi)存空間對測試結(jié)果的影響.

3.2 測試結(jié)果與分析

分別取 133、1 334、2 752、4 330、7 167、11 215、14 804和20 424條道路的8組數(shù)據(jù)進(jìn)行測試，得到傳統(tǒng)索引的耗時分別為 28、121、225、381、1 069、1 585、2 100和3 372 ms，新索引方法的耗時分別為10、41、105、167、350、560、692 和 1 248 ms，結(jié)果圖 3 所示.

圖3 傳統(tǒng)索引和新索引耗費的時間對比Fig.3 Comparison of the time spent between traditional and new indexes

由圖3可以看出，隨著查詢空間對象個數(shù)的增加，2種空間索引的檢索耗時都在增加.這是因為隨著查詢空間對象數(shù)量的增多，索引數(shù)據(jù)節(jié)點的訪問次數(shù)、數(shù)據(jù)的讀取次數(shù)以及屬性的判定次數(shù)均隨之增多，導(dǎo)致耗時增加.但與傳統(tǒng)空間索引相比，K-DA在每組查詢中的耗時分別約為傳統(tǒng)索引花費時間的50%、40%和30%，且隨著查詢數(shù)量的增加，節(jié)約的時間更多.其原因主要為

（1）節(jié)省讀取時間.傳統(tǒng)空間索引沒有顧及屬性，在索引時將所有數(shù)據(jù)全部讀取，并根據(jù)用戶所給定的索引條件，從全部讀取出的數(shù)據(jù)中篩選出符合條件的信息，再進(jìn)行顯示；而顧及屬性的新索引已經(jīng)將屬性信息添加至K-D樹的葉節(jié)點中，所以在索引時，根據(jù)用戶給定的索引條件，可以直接篩選出符合要求的葉節(jié)點中的屬性對應(yīng)的數(shù)據(jù)，不用讀出全部數(shù)據(jù)，因此在此環(huán)節(jié)節(jié)省大量時間.

（2）節(jié)省檢索時間.傳統(tǒng)的空間索引在檢索時，需要檢索所有數(shù)據(jù)，搜索范圍很大.而新的K-DA檢索過程中，由于在K-D樹的葉節(jié)點添加了屬性，縮小了需要搜索的范圍，所以節(jié)約了檢索時間，提高了檢索的效率.

4 結(jié)論

本研究將導(dǎo)航數(shù)據(jù)道路等級屬性與空間索引相結(jié)合，研究顧及屬性的K-D樹空間索引方法，提出的K-DA空間索引機制在傳統(tǒng)K-D空間索引的基礎(chǔ)上，擴展了屬性項，使其在保留傳統(tǒng)空間篩選功能的同時，增加了屬性判斷，減少了數(shù)據(jù)的冗余讀取，讀取速度在每組查詢中的耗時分別約為傳統(tǒng)索引耗時的50%、40%和30%，且隨著數(shù)據(jù)量的增加，K-DA樹索引時間與傳統(tǒng)索引時間比例更小，索引效率更高.新索引機制不僅可以用于導(dǎo)航數(shù)據(jù)，還可以用于傳統(tǒng)空間數(shù)據(jù)的索引，且算法不會對傳統(tǒng)空間索引的本質(zhì)產(chǎn)生影響，方法靈活，具有一定的普適性.

參考文獻(xiàn)：

[1] 牛紅光.基于R樹和Petri網(wǎng)的多尺度表達(dá)模型研究[D].鄭州：信息工程大學(xué)，2006.NIU H G.Research on Multi Scale Expression Model Based on R Tree and Petri Net[D].Zhengzhou：Information Engineering University，2006（in Chinese）.

[2]付偉.基于R樹的空間索引技術(shù)的研究與應(yīng)用[D].成都：四川大學(xué)，2006.FU W.Research and Application of Spatial Indexing Technology Based on RTree[D].Chengdu：Sichuan University，2006（in Chinese）.

[3] 余登峰.基于R樹的空間數(shù)據(jù)索引技術(shù)研究與實現(xiàn)[D].武漢：中國地質(zhì)大學(xué)，2006.YU D F.Research and Implementation of Spatial Data Indexing Technology Based on R Tree[D].Wuhan：China University of Geosciences，2006（in Chinese）.

[4]周帆.基于R-樹的空間數(shù)據(jù)索引技術(shù)的研究與實現(xiàn)[D].哈爾濱：哈爾濱理工大學(xué)，2009.ZHOU F.Research and Implementation of Spatial Data Indexing Technology Based on R-tree[D].Haerbin：Harbin Polytechnic University，2009（in Chinese）.

[5] BENTLY J L.Multidimensional binary search trees used for associative searching[J].Communications of the ACM，1975，18（9）：509-517.

[6]閻德超，趙學(xué)勝.GIS空間索引方法述評[J].地理與地理信息科學(xué)，2004，20（4）：23-26.YAN D C，ZHAO X S.A review of GIS spatial indexing methods[J].Geography and Geographic Information Science，2004，20（4）：23-26（in Chinese）.

[7] 劉宇，熊有倫.基于有界K-D樹的最近點搜索方法[J].華中科技大學(xué)學(xué)報（自然科學(xué)版），2008，36（7）：73-76.LIU Y，XIONG Y L.The nearest point search method based on bounded K-D tree[J].Journal of Huazhong University of Science and Technology（Natural Science Edition），2008，36（7）：73-76（in Chinese）.

[8]劉春，史文中，劉大杰.導(dǎo)航電子地圖中道路數(shù)據(jù)的空間索引和組織[J].工程勘察，2003（1）：38-41.LIU C，SHI W Z，LIU D J.Spatial index and organization of road data in navigation electronic map[J].Engineering Investigation，2003（1）：38-41（in Chinese）.