[發明專利]分布式訂閱發布模式下的空間范圍-關鍵字查詢方法

有效

• 申請號: 202110078248.X
• 申請日: 2021-01-20
• 公開（公告）號: CN112507689B
• 公開（公告）日: 2023-08-01
• 發明（設計）人: 鄧澤;王力哲;王月;劉韜;陳小島;陳云亮
• 申請（專利權）人: 中國地質大學（武漢）
• 主分類號: G06F40/194
• 分類號: G06F40/194;G06F16/31;G06F16/332;G06F16/29
• 代理公司: 北京隆源天恒知識產權代理有限公司 11473
• 代理人: 吳航

1.一種分布式訂閱發布模式下的空間范圍-關鍵字查詢方法，其特征在于，包括：

發布服務器接收地理文本流數據，其中，所述發布服務器上部署有每個訂閱服務器的空間簽名和文本簽名組，其中，所述空間簽名針對空間范圍-關鍵字查詢的空間范圍部分采用空間布谷鳥過濾器技術生成，所述文本簽名組針對空間范圍-關鍵字查詢的關鍵字集合部分采用單排序最小哈希算法和倒排文件四叉樹方法生成；

所述發布服務器遍歷每個所述空間簽名和每個所述文本簽名組，與所述地理文本流數據進行空間包含關系判斷和文本相似性計算；

所述發布服務器基于所述空間包含關系判斷和所述文本相似性計算結果，判斷所述地理文本流數據是否命中至少一個所述訂閱服務器；

若是，則由所述發布服務器把所述地理文本流數據轉發到命中的訂閱服務器上；

在所述發布服務器接收地理文本流數據之前，還包括：

把整個二維空間劃分為多個等大小區域的集合ε，并對ε中的每個區域分配一個唯一的標記ID，一個區域的標記信息定義為r.ID，所述訂閱服務器上的每個空間范圍-關鍵字查詢的空間范圍為ε的子集合，該子集合表示為△，子集合Δ由至少一個區域組成；

在所述訂閱服務器上初始化一個布谷鳥哈希表；

遍歷空間范圍-關鍵字查詢的每個區域，計算區域r.ID的指紋finger(r.ID)，并基于第一預設公式計算所述區域r.ID在所述布谷鳥哈希表中對應的兩個桶值，其中，所述第一預設公式包括：h₁＝hash(r.ID)，其中，是異或運算符號，h₁與h₂的計算結果為所述區域r.ID在所述布谷鳥哈希表中對應的兩個桶值；

分別判斷空間范圍-關鍵字查詢中的所述區域r.ID在所述布谷鳥哈希表中對應的兩個桶中是否有空閑位置，其中，所述兩個桶表示為bucket[h₁]和bucket[h₂]；

若是，則將空間范圍-關鍵字查詢中的所述區域r.ID的指紋插入到所述空閑位置中；

若否，則使用空間范圍-關鍵字查詢中的所述區域r.ID的指紋替換掉bucket[h₁]或bucket[h₂]的一個指紋；

得到最終的哈希表，所述最終的哈希表作為所述訂閱服務器的所述空間簽名；

在所述發布服務器接收地理文本流數據之前，還包括：

在所述訂閱服務器上利用所述單排序最小哈希算法生成訂閱關鍵字集合的簽名，得到所述訂閱服務器中四叉樹所有葉子結點的關鍵字的簽名，并把所述所有葉子結點的關鍵字的簽名匯總到簽名集合中；

當所有葉子節點所對應的文本簽名組大于預設閾值時，把擁有同一個父節點的四個子節點的文本簽名合并為一個新的文本簽名，匯聚成新的簽名集合，直到簽名集合中簽名的個數小于或等于所述預設閾值，并將此時的簽名集合作為所述文本簽名組。

2.如權利要求1所述的分布式訂閱發布模式下的空間范圍-關鍵字查詢方法，其特征在于，所述在所述訂閱服務器上利用單排序最小哈希算法生成訂閱關鍵字集合的簽名包括：

將所述訂閱關鍵字集合進行哈希運算，得到由0和1組成的字符串；

將所述字符串進行分組，得到多個字符串組；

獲取每個所述字符串組中第一個非零值所處的位置；

將每個所述字符串組中第一個非零值所處的位置所組成的集合作為所述訂閱關鍵字集合的簽名。