[發(fā)明專利]一種非關(guān)系數(shù)據(jù)庫中的時(shí)空數(shù)據(jù)索引方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710516384.6
• 申請(qǐng)日: 2017-06-29
• 公開（公告）號(hào): CN107423368B
• 公開（公告）日: 2020-07-17
• 發(fā)明（設(shè)計(jì)）人: 李成名;吳政;肖斐;沈建明;孫偉;洪志遠(yuǎn);路文娟;武鵬達(dá);劉麗;孫隆祥
• 申請(qǐng)（專利權(quán)）人: 中國測繪科學(xué)研究院
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22;G06F16/2455;G06F16/2458
• 代理公司: 北京華仲龍騰專利代理事務(wù)所(普通合伙) 11548
• 代理人: 李靜

1.一種非關(guān)系數(shù)據(jù)庫中的時(shí)空數(shù)據(jù)索引方法，其特征在于，包括以下步驟：

A、在分布式環(huán)境中，為時(shí)空數(shù)據(jù)建立基于四叉樹與Hilbert曲線的空間索引；

B、在空間索引的基礎(chǔ)上，結(jié)合時(shí)空數(shù)據(jù)的時(shí)間屬性，形成統(tǒng)一的時(shí)空索引；

C、將時(shí)空索引分為分區(qū)鍵和排序鍵兩部分，并使用一致性哈希實(shí)現(xiàn)空間數(shù)據(jù)在動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)渲蟹植即鎯?chǔ)和路由，其中，分區(qū)鍵包括空間索引的第N層索引值與時(shí)間索引的YYMM，其中N為用戶自定的最高分區(qū)層次，YYMM表示年、月；排序鍵是指時(shí)空索引中去除分區(qū)鍵內(nèi)容的部分；

D、當(dāng)收到查詢請(qǐng)求時(shí)，根據(jù)時(shí)間及空間范圍確定查詢范圍的分區(qū)鍵和排序鍵并在存儲(chǔ)節(jié)點(diǎn)中進(jìn)行檢索，返回查詢結(jié)果。

2.根據(jù)權(quán)利要求1所述的非關(guān)系數(shù)據(jù)庫中的時(shí)空數(shù)據(jù)索引方法，其特征在于，空間索引的構(gòu)建包括如下步驟：

步驟1：建立包圍整個(gè)地球的立方體：[-1，1]×[-1，1]×[-1，1]；

步驟2：地球上的某一點(diǎn)P投影到立方體某一面上；

步驟3：在每一個(gè)立方體面上構(gòu)建四叉樹，每個(gè)四叉樹單元都由一個(gè)控制點(diǎn)進(jìn)行標(biāo)識(shí)；

步驟4：找到包含點(diǎn)P對(duì)應(yīng)投影點(diǎn)的四叉樹單元；

步驟5：將該四叉樹單元映射到到某一級(jí)的Hilbert曲線上，生成時(shí)空數(shù)據(jù)的Cell ID。

3.根據(jù)權(quán)利要求2所述的非關(guān)系數(shù)據(jù)庫中的時(shí)空數(shù)據(jù)索引方法，其特征在于，步驟4中，找到包含點(diǎn)P對(duì)應(yīng)投影點(diǎn)的四叉樹單元的過程為：從四叉樹根節(jié)點(diǎn)開始，判斷投影點(diǎn)屬于哪個(gè)象限，遞歸到相應(yīng)的節(jié)點(diǎn)，重復(fù)步驟，直到到達(dá)葉節(jié)點(diǎn)，然后將該點(diǎn)加入存儲(chǔ)節(jié)點(diǎn)的索引點(diǎn)列表中。

4.根據(jù)權(quán)利要求1所述的非關(guān)系數(shù)據(jù)庫中的時(shí)空數(shù)據(jù)索引方法，其特征在于，空間索引中含有應(yīng)用Hilbert曲線層次分解的30個(gè)level。

5.根據(jù)權(quán)利要求1所述的非關(guān)系數(shù)據(jù)庫中的時(shí)空數(shù)據(jù)索引方法，其特征在于，查詢的過程包括如下步驟：

步驟1：用戶輸入任意多邊形M與時(shí)間區(qū)間[t₁，t₂]作為查詢窗口；

步驟2：計(jì)算M所在的最小外包細(xì)胞cell_min與分區(qū)細(xì)胞集合C＝{cell_i|i∈R，i≥1}，其中，R表示集合理論中的實(shí)數(shù)集；

步驟3：計(jì)算時(shí)間區(qū)間[t₁，t₂]所對(duì)應(yīng)的時(shí)期集合：E＝{epoch_j|j∈R，j≥1}，其中，R表示集合理論中的實(shí)數(shù)集；

步驟4：計(jì)算cell_min的區(qū)域編碼最大值：和區(qū)域編碼最小值

步驟5：遍歷分區(qū)細(xì)胞集合C與時(shí)期集合E中的所有元素進(jìn)行兩兩組合，并計(jì)算一致牲哈希值H＝{hash(cell，epoch)|cell∈C，epoch∈E}；

步驟6：根據(jù)一致性哈希值H查找所有時(shí)空數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)集合N；

步驟7：存儲(chǔ)節(jié)點(diǎn)集合N中的每個(gè)存儲(chǔ)節(jié)點(diǎn)按照查詢條件對(duì)時(shí)空數(shù)據(jù)進(jìn)行掃面并返回掃描結(jié)果，其中pos為存儲(chǔ)節(jié)點(diǎn)集合N中每一條時(shí)空數(shù)據(jù)對(duì)應(yīng)的區(qū)域編碼；

步驟8：將存儲(chǔ)節(jié)點(diǎn)集合N返回的掃描結(jié)果與多邊形M進(jìn)行相交查詢，得到最終查詢結(jié)果。