一種顧及導航數據屬性的K-DA樹索引方法

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

（天津師范大學地理與環境科學學院，天津 300387）

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

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

1 傳統K-D樹空間索引技術

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

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

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

2 顧及屬性的空間索引構建

2.1 設計思想

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

2.2 基本算法

K-DA樹的構建過程如圖2所示.

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

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

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

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

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

2.2.1 K-DA樹的算法思路

構建K-DA樹算法的主要步驟為：

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

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

（3）構造子樹：設定K-DA樹的最大深度maxdepth，判定條件為若當前深度小于樹的最大深度，葉節點的最小對象數要大于2，且滿足外包矩形的面積大于最小閾值或對象列表數大于5，則通過比較當前對象最小外包矩形中點的x1與所得最小外包矩形中點的x2，將x1小于x2的對象放入左子樹objBuckets[0]，將x1大于x2的對象放入右子樹objBuckets[1]，再分別對左右子樹進行類似判斷，繼續劃分左右子樹直至葉節點，其中，葉節點中存儲了地址和屬性信息.

（4）如果不滿足判定條件，則當前節點為葉節點.

（5）當節點被判定為葉節點后，將屬性嵌入葉節點中，當一棵子樹2個葉節點所嵌入的屬性相同時，則將葉節點中的屬性嵌入至這2個葉節點對應子樹的父節點中.具體構建算法為

2.2.2 索引查詢過程

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

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

以上過程的具體實現算法為

3 實驗

3.1 實驗方法

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

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

（3）數據來源：天津地區的導航數據，其中道路總數99 369條，共分8個等級.

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

3.2 測試結果與分析

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

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

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

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

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

4 結論

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

參考文獻：

[1] 牛紅光.基于R樹和Petri網的多尺度表達模型研究[D].鄭州：信息工程大學，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樹的空間索引技術的研究與應用[D].成都：四川大學，2006.FU W.Research and Application of Spatial Indexing Technology Based on RTree[D].Chengdu：Sichuan University，2006（in Chinese）.

[3] 余登峰.基于R樹的空間數據索引技術研究與實現[D].武漢：中國地質大學，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-樹的空間數據索引技術的研究與實現[D].哈爾濱：哈爾濱理工大學，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]閻德超，趙學勝.GIS空間索引方法述評[J].地理與地理信息科學，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].華中科技大學學報（自然科學版），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]劉春，史文中，劉大杰.導航電子地圖中道路數據的空間索引和組織[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）.