[發明專利]一種基于文本-域倒排的空間文本查詢方法及裝置

有效

• 申請號: 201810292840.8
• 申請日: 2018-04-04
• 公開（公告）號: CN108628950B
• 公開（公告）日: 2022-07-19
• 發明（設計）人: 沈兵林;賈連印;丁家滿;游進國;李曉武;左喻灝;胡俊濤;雷妍
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06F16/31
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于文本-域倒排的空間文本查詢方法，其特征在于：包括：

數據預處理步驟，將數據集D中所有位置點編碼成長度為n的字符串，以該字符串為排序對象按字典序對數據集中的記錄排序并生成編號id，每一行數據稱為一條記錄r，則由一至多行記錄r組成的數據集稱為記錄集R；

空間文本索引建立步驟，對記錄集R中的文本建立倒排索引，倒排索引的列表元素為與字符串相對應的id列表，得到文本-域倒排索引結構；

布爾范圍查詢步驟，檢索文本-域倒排索引結構，獲取滿足查詢條件的id，經過濾得到id候選集，并對候選集驗證返回查詢范圍內的所有位置點；

所述數據預處理步驟，具體包括如下步驟：

步驟110：給定一個由一系列位置點、關鍵詞集構成的數據集D，通過geohash空間編碼方法將D中的位置點編碼成長度為n的字符串geoStr；其中，位置點由緯度、經度數據構成；geoStr即geohash編碼，表示geohash精度表中n對應的范圍區域；

步驟120：以geoStr為排序對象按字典序對數據集中的記錄排序并生成編號id，每一行數據稱為一條記錄r，則由一至多行記錄r組成的數據集稱為記錄集R；其中，記錄r由id、緯度lat、經度lon、字符串geoStr、關鍵詞集items組成，items至少包含一個關鍵詞item；

所述空間文本索引建立步驟，具體為：

步驟210：對R_items中每個獨立元素關鍵詞item，構建一個由r_part組成的倒排索引；其中，R_items表示記錄集R中全部關鍵詞，r_part由item包含于r.items的r.id、r.geoStr組成，r.items表示記錄r的關鍵詞集，r.id表示記錄r的id，r.geoStr表示記錄r的字符串，R_part表示由一至多行r_part組成的記錄集，r∈R；

步驟220：對R_pgStrs中每個獨立元素geoStr，構建一個由r_part.geoStr等于geoStr的r_part.id組成的倒排列表；其中，R_pgStrs表示R_part中全部geoStr，r_part.geoStr表示r_part的字符串，r_part.id表示r_part的id，r_part∈R_part。

2.根據權利要求1所述的基于文本-域倒排的空間文本查詢方法，其特征在于：所述布爾范圍查詢步驟，具體包括如下步驟：

步驟310：給定查詢位置點q、查詢距離范圍d、查詢關鍵詞集q_items，根據geohash精度表選定與查詢距離范圍d相對應的geohash編碼長度p，通過geohash空間編碼方法將位置點q編碼為p位長度的字符串q_s，獲取字符串q_s周圍8個區域的geohash編碼，并將字符串q_s及其周圍8個區域的geohash編碼分別作為查詢域，共9個查詢域；其中，p對應的距離誤差不小于d且為最小值；q_items至少由一個關鍵詞item構成；

步驟320：在文本-域倒排索引結構上快速獲取滿足查詢條件的id；其中，查詢條件指查找距離位置點q不大于d且包含全部q_items的id，即布爾范圍查詢；

步驟330：根據查詢位置點q和查詢距離范圍d分別確定緯度范圍與經度范圍，根據經緯度范圍對與步驟320返回的id相對應的位置點進行篩選，最終得到id候選集；

步驟340：計算候選集中id對應的位置點到查詢位置點q的距離d_q：若d_q≤d，則返回該位置點，否則，不返回。

3.根據權利要求1所述的基于文本-域倒排的空間文本查詢方法，其特征在于：所述步驟110，包括下列步驟111、112：

步驟111：根據geohash精度表確定geohash編碼長度n；

步驟112：通過geohash空間編碼方法將所有位置點編碼成長度為n的字符串。