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

無效

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

1.一種移動地理信息空間索引方法，其特征在于，所述的方法主要分三個步驟：

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

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

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

2.根據(jù)權利要求1所述的移動地理信息空間索引方法，其特征在于，在步驟(2)中DOQR核心包括四個步驟：

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

B、當空間對象聚集到一定數(shù)量時，當再增加1個空間對象，假定四分節(jié)點閾值QM＝4，總空間對象個數(shù)增加到5個時，以包含當前空間對象集的MBR中心為分割點，將空間區(qū)域劃分為四個子空間，整個空間的根節(jié)點變?yōu)橐粋€中間節(jié)點，或稱四分節(jié)點，四個子空間對應四個子節(jié)點，且四個子空間也是動態(tài)開放的；

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

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

3.根據(jù)權利要求1所述的移動地理信息空間索引方法，其特征在于，在步驟(3)中包括以下算法：

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

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

查詢算法：空間查詢又稱空間檢索、空間查找，是指從空間數(shù)據(jù)庫或空間數(shù)據(jù)集合中查找出滿足某一條件的空間目標的過程。根據(jù)查找的條件的不同，一般空間查詢可以分為點查詢和區(qū)域查詢兩種，點查詢與區(qū)域查詢過程基本相同，不同點在于，點查詢結果為0或1條記錄，而區(qū)域查詢結果則是多條記錄，在DOQR樹中，空間查詢是先通過查詢條件篩選出候選集合，再對候選集合進行精確幾何判斷，從而得到查詢結果；

更新策略算法：當空間實體的形狀發(fā)生改變時，如果這種改變沒有影響其MBR，那么對于空間索引來說，這個實體在索引中的位置不變，如果空間實體的形狀變化導致其MBR的變化，那么該實體的索引記錄在空間索引的位置也需要做相應的調(diào)整，一般空間索引更新方法都采用先刪除舊的索引記錄項，然后插入更新后的索引記錄項，DOQR樹刪除操作是局部定位調(diào)整更新，不會影響整個索引結構的穩(wěn)定性。