[發明專利]一種柵格數據索引及查詢方法

有效

• 申請號: 201510733308.1
• 申請日: 2015-11-02
• 公開（公告）號: CN105354291B
• 公開（公告）日: 2018-06-19
• 發明（設計）人: 劉奕夫;賀楷鍇
• 申請（專利權）人: 武大吉奧信息技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京天奇智新知識產權代理有限公司 11340
• 代理人: 蔡飛燕

本發明涉及一種索引及查詢方法，屬于地理信息數據處理領域，具體涉及一種柵格數據索引及查詢方法。包括：將瓦片數據劃分為若干個大小相同的單元格組，所述單元格組內的瓦片數據在位置上相鄰，利用狀態整數表示單元格組內瓦片數據的狀態，其中，所述狀態整數屬于計算機整數，其每一位對應單元格組內的一個瓦片數據的狀態。該柵格數據索引及查詢方法存儲密度高且存儲容量穩定，在瓦片數據連續存在或者非連續存在的情況下都能夠存儲的數據結構一致，且計算量完全恒定；在實現具有空間相關性的檢索時有更高的性能；并且可以充分利用計算機的數據結構，計算量低，效率更高。

技術領域

本發明涉及一種索引及查詢方法，屬于地理信息數據處理領域，具體涉及一種柵格數據索引及查詢方法。

背景技術

隨著互聯網技術和GIS技術的高速發展，基于互聯網技術的瓦片地圖得到了廣泛的使用。

瓦片本身是一種非常簡單的數據結構，同一級瓦片之間保持平鋪，因此利用簡單的線性計算公式就可以輕易做各種計算，瓦片不同級別之間也是一種線性的比率關系。瓦片地圖這樣非常易于計算的特性使得使用互聯網上提供的TMS(Tiled Map Service,瓦片地圖服務)基本上不需要使用索引，或者可以說瓦片的各種計算公式就是索引。

因此在常規使用情況下瓦片數據并不需要特別的索引來提升效率。但在一些特殊的場合，瓦片數據仍然需要索引來提升效率?？紤]到數據生產成本，數據存儲成本等因素，瓦片數據并不一定都存儲為矩形的范圍。如圖1所示，為了降低數據生產或者存儲的成本或者考慮使用的業務需求，瓦片數據可能會以行政區劃邊界作為瓦片邊界，考慮到行政區劃的不規則性，因此瓦片的范圍不能簡單的以矩形范圍定義。

對于邊界不規則的瓦片數據可以使用適合對柵格數據進行壓縮存儲的行程索引技術。如圖1所示的湖北省境界瓦片通過這樣的行程索引即可表達，如圖2所示。

瓦片數據如果按照行列以連續的方式存在，這樣的瓦片數據非常適用行程索引的方式存儲其邊界。如圖3所示。邊界不規則的瓦片數據，如果邊界內部的瓦片以連續的方式存在，那么使用行程索引數據存儲結果非常簡單，數據存儲的密度可以很高。例如某行的瓦片為1000個連續存儲，那么通過單個行程索引段[0-1000]即可表達，實際只花費了2個整數(64bit)的存儲空間。

然而并非所有的瓦片數據都能夠按照行列連續存在，一些特殊的瓦片數據，如點、文字等數據比較稀疏，那么形成的瓦片數據將會是不連續的，類似鏤空的效果，這樣類型的瓦片數據如圖4所示。當瓦片數據不是連續方式存在時，采用行程索引存儲瓦片數據的范圍會造成行程索引數據復雜度增加，相應的檢索效率實際上也會降低。過于稀疏的瓦片數據會讓行程索引的數據存儲密度大大降低。如一個行程索引段[3-3],實際上只記錄了一個瓦片的存在，然而卻花費了兩個整數(64bit)的存儲空間。

對于連續存在的瓦片數據采用行程索引可以非常高效，而非連續存在的瓦片數據采用行程索引可能會效率降低，因此行程索引并不是一種在性能上足夠穩定的瓦片索引方法，本發明采用一種比行程索引更為直接、簡單的柵格索引方法來存儲瓦片的邊界，不論瓦片是否連續存在，采用本發明的索引方法可以保證計算量的恒定，數據存儲的密度也能保持恒定。

發明內容

本發明主要是解決現有技術所存在的數據存儲密度較低，計算量變化較大的技術問題，提供了一種柵格數據索引及查詢方法。該柵格數據索引及查詢方法存儲密度高且存儲容量穩定，在瓦片數據連續存在或者非連續存在的情況下都能夠存儲的數據結構一致，且計算量完全恒定；在實現具有空間相關性的檢索時有更高的性能；并且可以充分利用計算機的數據結構，計算量低，效率更高。

本發明的上述技術問題主要是通過下述技術方案得以解決的：