[發(fā)明專利]一種基于掩碼技術(shù)和剖分編碼的位置信息快速檢索方法

有效

• 申請?zhí)枺?/td>: 201410373107.0
• 申請日: 2014-07-31
• 公開（公告）號: CN104182475A
• 公開（公告）日: 2014-12-03
• 發(fā)明（設(shè)計）人: 程承旗;濮國梁;王慧玲
• 申請（專利權(quán)）人: 北京大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京理工大學(xué)專利中心 11120
• 代理人: 高燕燕;仇蕾安

技術(shù)領(lǐng)域

本發(fā)明涉及地球空間信息剖分組織、導(dǎo)航位置服務(wù)、空間數(shù)據(jù)網(wǎng)格化查詢檢索技術(shù)領(lǐng)域，具體涉及一種利用剖分編碼掩碼技術(shù)進(jìn)行編碼匹配實(shí)現(xiàn)位置信息快速檢索的方法。

背景技術(shù)

當(dāng)前，隨著遙感技術(shù)、計算機(jī)技術(shù)、衛(wèi)星通信技術(shù)的快速發(fā)展，空間信息獲取能力的不斷提升，空間數(shù)據(jù)呈爆炸式增長。不同空間分辨率，不同光譜分辨率，不同時間分辨率的海量對地觀測數(shù)據(jù)的存儲、組織、管理以及高效檢索問題成為至關(guān)重要的研究內(nèi)容。坐標(biāo)方式(常見的有經(jīng)緯度坐標(biāo)、大地坐標(biāo)、直角坐標(biāo)等)是目前能夠被人們普遍接受的空間位置信息的表達(dá)方法。各類空間信息無論是基礎(chǔ)地理數(shù)據(jù)，還是遙感、衛(wèi)星導(dǎo)航的數(shù)據(jù)，都需要最終提供詳細(xì)的坐標(biāo)描述信息，以便于提供基于空間范圍的查詢檢索。

基于坐標(biāo)空間范圍的查詢檢索目前的做法：提供待查詢區(qū)域的上、下、左、右四個邊界的坐標(biāo)信息，搜索數(shù)據(jù)庫中的記錄是否在待查詢區(qū)域時，需要進(jìn)行四次的浮點(diǎn)數(shù)大小比較運(yùn)算。另外，經(jīng)緯度網(wǎng)格是由任意的經(jīng)緯度點(diǎn)連接而成，點(diǎn)與點(diǎn)之間相互獨(dú)立，沒有層次上的遞歸關(guān)系，不同區(qū)域的空間數(shù)據(jù)較難建立空間上的從屬和關(guān)聯(lián)。當(dāng)數(shù)據(jù)條目達(dá)到千萬級別甚至更大時，即使在經(jīng)緯度字段建立了索引，得到檢索結(jié)果也需要較長的時間。特別是在查詢區(qū)域是不規(guī)則范圍時，這樣的耗時更加難以忍受。例如：設(shè)當(dāng)前位置經(jīng)緯度為(B,L)，位置區(qū)域范圍為X，查詢條件為：B-X/2≤LATITUDE≤B+X/2?AND?L-X/2≤LONGITUDE≤L+X/2，經(jīng)度和緯度字段分別建立B⁺樹索引，在2000萬條后臺數(shù)據(jù)記錄中，利用經(jīng)緯度字段查詢某區(qū)域所包含的地物信息，在目前的手機(jī)終端檢索測試中，耗時1830ms，時間復(fù)雜度比較高。

為了提高查詢檢索的效率，一些GIS與導(dǎo)航設(shè)備廠商在各類空間信息的坐標(biāo)基礎(chǔ)上，人為地在局部空間區(qū)域打上網(wǎng)格，利用這樣的局部網(wǎng)格建立空間編碼與索引，比較典型的如ArcGIS、MapInfo、超圖、高德地圖等采用的網(wǎng)格編碼與索引。但是這些局部網(wǎng)格的編碼和索引主要是針對局部數(shù)據(jù)的快速檢索而建立，網(wǎng)格和編碼本身往往是單一層次的，求取各類空間關(guān)系較復(fù)雜。更重要的是，局部網(wǎng)格與編碼是依據(jù)具體的對象而建立的，不同數(shù)據(jù)有不同的局部編碼，不同廠商生產(chǎn)的數(shù)據(jù)編碼也大不相同，數(shù)據(jù)編碼的共享存在很大問題。例如：高德的網(wǎng)格編碼完全不能被凱立德所使用，兩者之間的轉(zhuǎn)換耗費(fèi)巨大，如果將這兩種數(shù)據(jù)合并使用，還不如重新劃分網(wǎng)格，建立編碼來得快。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明提供了一種基于掩碼技術(shù)和剖分編碼的位置信息快速檢索方法，可實(shí)現(xiàn)對于檢索區(qū)域內(nèi)部各地理位置的快速檢索。

為達(dá)到上述目的，該方法的基本思想為：在GeoSOT剖分和編碼方案中，對應(yīng)每個層級j創(chuàng)建層級掩碼C_j，C_j與第32層級的GeoSOT編碼長度一致，且對應(yīng)層級1～j的位均為1、剩余位為0；1≤j≤32。

針對檢索區(qū)域，在GeoSOT剖分和編碼方案中選定與檢索區(qū)域有關(guān)聯(lián)關(guān)系的剖分面片集，剖分面片集中剖分面片p的GeoSOT編碼為Gd_p。

針對剖分面片集中的每一個剖分面片p獲取檢索結(jié)果：將剖分面片p的層級掩碼進(jìn)行邏輯非的位操作之后與Gd_p進(jìn)行邏輯或運(yùn)算，獲得剖分面片p范圍內(nèi)所包含的GeoSOT編碼數(shù)值最大的第32級剖分面片的編碼G_maxp；采用位比較方式，檢索獲得GeoSOT編碼大于或等于Gd_p且小于或等于G_maxp的所有剖分面片，檢索獲得的剖分面片的位置信息作為檢索結(jié)果。

最后，匯總剖分面片集中各剖分面片對應(yīng)的檢索結(jié)果。

優(yōu)選地，在GeoSOT剖分和編碼方案中選定與檢索區(qū)域有關(guān)聯(lián)關(guān)系的剖分面片集為：選定完全覆蓋檢索區(qū)域的一個剖分面片A。

優(yōu)選地，在GeoSOT剖分和編碼方案中選定與檢索區(qū)域有關(guān)聯(lián)關(guān)系的剖分面片集為：以GeoSOT剖分和編碼方案中覆蓋檢索區(qū)域的最小剖分面片A₀，A₀層級為k，找到該最小剖分面片周邊8個相鄰且層級為k的剖分面片A₁～A₈，由A₀～A₈組成剖分面片集。

進(jìn)一步地，選定剖分面片集后，對選定的剖分面片集進(jìn)行優(yōu)化，得到優(yōu)化剖分面片集；