[發明專利]一種基于小角編碼的矢量數據網格索引方法

有效

• 申請號: 201310051630.7
• 申請日: 2013-02-17
• 公開（公告）號: CN103106276A
• 公開（公告）日: 2013-05-15
• 發明（設計）人: 胡斌;邵華;朱進;張景云;陳伊玲
• 申請（專利權）人: 南京師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京知識律師事務所 32207
• 代理人: 汪旭東

技術領域

本發明涉及空間信息領域，特別涉及一種基于小角編碼的矢量數據網格索引方法。

背景技術

空間索引是提高矢量數據查詢效率的關鍵技術。現有空間索引技術有四叉樹索引、R樹索引、K-D-B樹、BSP樹、R樹、Cell樹和網格索引等。網格索引作為一種古老的索引方法，技術簡單，至今依然廣泛應用，但其最大的缺點是網格單元重復記錄多，在進行空間查詢時，需要對查詢區域覆蓋的網格單元所記錄的索引信息去除重復值。去重算法往往是網格索引算法中最耗時的部分。

一種去重算法是：把索引信息表先排序，然后順序掃描該有序表去除重復值。該算法的缺點是需要先排序，即使用快速排序其時間復雜度也達到O(???????????????????????????????????????????????)。另一種去重算法是：采用單一值集合記錄索引信息，在把索引信息添加到集合前，首先查詢集合中是否已經存在該值，只有不存在該值時才添加到集合中。該算法效率的高低與集合搜索和更新的效率密切相關比較耗時，為了提高集合查詢效率，一般采用高效的平衡二叉樹來實現集合，但也只能達到O(）的查詢效率，且平衡二叉樹是動態查找樹，更新效率較低，從而影響整體索引性能。因此，是否能快速過濾重復值，是網格索引效率高低的關鍵。本發明則能很好的解決了以上的這些問題。

發明內容

如圖1和圖2所示，本發明的主要目的在于提供了一種基于小角編碼的矢量數據網格索引方法，這種矢量數據網格索引方法包括如下步驟：

步驟1，矢量數據小角編碼和索引構建，其包括如下步驟：

（a）網格劃分：根據矢量空間范圍和應用需求，把矢量空間劃分成大小相等的規則網格，每一個網格單元由其行列號定義；?

（b）前綴編碼：確定矢量對象MBR的小角所在網格單元，根據該網格單元的行列值對矢量對象進行前綴編碼；

（c）索引構建：在矢量對象覆蓋的所有網格中添加該對象的索引信息（對象編碼，MBR），屬于同一網格的索引信息表按對象編碼遞增排列；

步驟2，小角編碼網格索引，其包括如下步驟：

（a）確定查詢窗口覆蓋的所有網格單元范圍，并設查詢起始網格行列為qrow，qcol；

（b）按照行列號從小到大的次序（先行后列）掃描每一網格單元（row,?col），依次獲取重復區的各索引記錄編碼前綴，得到對應的行列號（irow,?icol）：

（b1）?若icol<col?且?col<>qcol，剔除該記錄；

（b2）?若irow<row且row<>qrow，剔除該記錄；

（b3）用查詢窗口與沒剔除對象的MBR進一步測試，保留通過測試的對象編碼；

（c）根據最終的對象編碼列表進行詳細查詢，得到與查詢窗口相交的矢量對象信息。

由于采用小角編碼和遞增排列，每個網格單元中的索引信息列表自動分成兩部分，前一部分是對象編碼前綴小于該網格單元編碼的索引信息表，該部分需要進行去重操作，稱為重復區；后一部分是對象編碼前綴等于該網格單元編碼的索引信息表，該部分無需去重操作。

本發明的優點在于提出了一種基于小角編碼的矢量數據網格索引方法，這種方法把矢量數據MBR的小角編碼作為前綴編碼矢量數據，利用該編碼構造的網格單元索引信息表，自動分成重復區和非重復區，只需要針對重復區使用簡單的比較操作就能在O(N)時間內完成查詢，大大提高了矢量數據網格索引的查詢效率。

附圖說明

圖1為本發明的矢量數據編碼和索引構建的流程圖。

圖2為本發明的矢量數據和查詢窗口示意圖。

附圖標記說明：A、B、C、D、E、F-矢量要素MBR。

圖3為本發明的矢量數據小角編碼和網格索引示意圖。

附圖標記說明：A、B、C、D、E、F、G-矢量要素MBR。

具體實施方式

以下結合說明書附圖對本發明創造作進一步的詳細說明。

實施例一?

如圖3所示，本實施例中，本發明的這種基于小角編碼的矢量數據網格索引方法包括如下步驟：

步驟1，矢量數據小角編碼和索引構建，其包括如下步驟：

（a）網格劃分：設矢量數據空間范圍為XMIN（X起點），YMIN（Y起點），W（寬）和H（高），根據應用需求，確定網格行數m?=?10和列數n?=?10，建立索引網格，則每個網格單元寬△w?=?W/m,高△h?=?H/n；