[發明專利]一種移動地理信息空間索引方法

無效

• 申請號: 201110241074.0
• 申請日: 2011-08-22
• 公開（公告）號: CN102306166A
• 公開（公告）日: 2012-01-04
• 發明（設計）人: 田根;李二芳;李建;李晉芳;王芳
• 申請（專利權）人: 河南理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于電信增值業務和計算機應用技術領域，具體涉及一種移動地理信息空間索引方法。

背景技術

傳統的空間索引理論的背景是在以資源豐富的PC機或服務器這樣的硬件條件，存儲量、CPU計算速度、屏幕顯示、有線電源等都和移動設備具有很大的不同。如果直接將這些空間索引技術應用到移動GIS中，往往性能達不到原來設計的要求。

現有的技術缺點：

(1)現有的技術方法較多依賴于預先知道空間索引區域；

(2)現有的技術方法具有固定的空間區域劃分，缺乏靈活性；

(3)現有的技術方法在空間數據量發生變化后需要重新建立整個空間索引結構，浪費了大量計算時間；

(4)現有的技術方法主要以硬件性能較好的臺式機為平臺，在移動設備上則缺乏適應性；

(5)現有的技術方法因以臺式機為平臺考慮，允許空間對象具有不同程度的重復存儲，浪費了一定的存儲量。

發明內容

為了解決現有技術存在的不足，本發明解決的技術問題是提供一種使用簡便、存儲效率高的移動地理信息空間索引方法。其技術方案如下：

一種移動地理信息空間索引方法，所述的方法主要分三個步驟：

(1)移動地理信息空間數據的存儲：主要包括圖形數據和屬性數據的存儲，圖形數據采用本地文件的方式進行存儲，采用用戶系統定制的序列化二進制文件，所述序列化二進制文件在進行讀存時的必須按照相同的步驟，存入的數據的類型、順序必須與讀取的該數據的數據類型、順序相同，屬性數據采用嵌入式數據系統存儲，本地文件中的圖形數據通過唯一標識ID與嵌入式數據庫中的圖形文件對應的屬性表ID進行管理；

(2)移動地理信息空間索引結構的建立：DOQR索引樹核心利用空間對象的外接矩形MBR代表空間對象的本身所占區域范圍，按照空間區域和空間區域存儲空間對象的個數進行組織存儲，利用空間區域的索引，可以在進行空間信息查詢、顯示、分析時，從大量空間分布不均勻的空間對象中檢索出某一特定區域的空間對象；

(3)移動地理信息空間索引方法的設計：在一張建有空間索引的表中，若進行空間數據插入、刪除、或修改，那么在索引中也要插入，刪除、或修改相應的索引記錄項。

進一步優選，在步驟(2)中DOQR核心包括四個步驟：

A、在沒有工作范圍邊界限定的全開放空間范圍(簡稱開放空間)上，將空間對象聚集到一個開放的空間區域中，整個開放空間的根節點對應1個葉節點LNode(Leaf?Node)，并且將空間對象的索引記錄(OID，MBR)存放到該葉節點的存儲桶里即存放索引記錄(OID，MBR)集合的地方；

B、當空間對象聚集到一定數量時，當再增加1個空間對象，假定四分節點閾值QM＝4，總空間對象個數增加到5個時，以包含當前空間對象集的MBR中心為分割點，將空間區域劃分為四個子空間，整個空間的根節點變為一個中間節點，或稱四分節點，四個子空間對應四個子節點，且四個子空間也是動態開放的；

C、然后將步驟A存儲桶中空間對象集中的空間對象重新進行分配，分配規則是：利用每一個空間對象的MBR，判斷每一個空間對象是否與中心分割線相交；如相交，則將空間對象索引記錄(OID，MBR)保存到屬于中間節點的R樹結構中存儲桶中；如不相交，先判斷每一個空間對象位于四個子空間的哪一個空間區域中，然后把每一個空間對象索引記錄保存到該子空間區域對應的子節點存儲桶中，以此類推，分配所有的空間對象；

D、根據空間對象分配規則，當四個子節點的任何一節點中的空間對象聚集到一定數量時，把子節點空間區域再劃分為四個子空間，按照B、C、D步驟以此類推。

進一步優選，在步驟(3)中包括以下算法：

插入算法：當把一個新增的空間實體加入到建有空間索引的實體集時，需要把該實體生成的索引記錄項加入到相應的空間索引DOQR樹中，如果開放空間節點未“滿”，則直接將新索引記錄項添加到節點相應數組中；如果已“滿”，則需四分開放節點，并將數組中的索引記錄項同新增條目一起依次添加到新的子開放節點和R樹中；

刪除算法：當從空間實體集中刪除了一個空間實體時，需要將相應的DOQR樹中指向該實體的索引記錄項也一同刪除，即刪除對象前先獲取其索引記錄項，然后利用索引記錄的MBR來判斷其所在的開放節點，最后進行OID匹配，匹配成功，則刪除該索引項，同樣地，在刪除后為了維護DOQR樹的性質，需要對DOQR樹進行調整；