[發明專利]一種基于Geo-BTree的范圍查詢方法及裝置

有效

• 申請號: 201710843972.0
• 申請日: 2017-09-19
• 公開（公告）號: CN107766433B
• 公開（公告）日: 2021-05-14
• 發明（設計）人: 沈兵林;賈連印;丁家滿;游進國;李曉武;左喻灝;胡俊濤;雷妍
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F16/22
• 分類號: G06F16/22
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于Geo-BTree的范圍查詢方法，其特征在于：包括：

數據預處理步驟，將數據集中所有位置點編碼成長度為n的字符串string，根據字符串按字典序對數據集中的位置點排序并編號ID；

空間索引建立步驟，根據排序后的字符串構建B-Tree索引結構；

范圍查詢步驟，以檢索B-Tree索引結構返回的ID為起始點雙向搜索獲取查詢域內的ID，經過濾得到ID候選集，并對候選集中ID所對應的位置點驗證返回查詢范圍內的位置點；

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

步驟210：根據字符串構建B-Tree索引結構，每個結點至少存儲1個string,ID；

所述范圍查詢步驟，具體包括如下步驟：

步驟310：給定查詢位置點q和查詢距離范圍d，根據geohash精度表選定與d相對應的geohash編碼長度p，通過geohash算法將位置點q編碼為p位長度的字符串q_s，獲取字符串q_s周圍8個區域的geohash編碼，并將字符串q_s及其周圍8個區域的geohash編碼分別作為查詢域，共9個查詢域；其中，p對應的距離誤差不小于d且為最小值，每一個geohash編碼表示一個區域；

步驟320：根據檢索B-Tree索引結構返回的ID，在記錄集中以此ID為起始點雙向搜索至不滿足查詢條件，返回滿足查詢條件的ID，為一個查詢域內的ID；重復以上操作至獲取9個查詢域內的ID；其中，每一行數據稱為一條記錄，則由這些數據組成的數據集稱為記錄集，記錄由ID、緯度、經度、字符串組成；查詢條件指記錄集中字符串的前p位與查詢域的geohash編碼相同；

步驟330：根據查詢位置點q和查詢距離范圍d分別確定緯度范圍與經度范圍，通過經緯度范圍對9個查詢域內的ID進行篩選，最終得到ID候選集；

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

2.根據權利要求1所述的基于Geo-BTree的范圍查詢方法，其特征在于：所述數據預處理步驟，具體包括如下步驟：

步驟110：給定一個由一系列位置點構成的數據集D，通過geohash算法將D中的位置點編碼成長度為n的字符串string；其中，位置點由緯度、經度數據構成；

步驟120：根據字符串按字典序對數據集中的位置點排序并編號，該編號即為對應的位置點ID，每一行數據稱為一條記錄，則由這些數據組成的數據集稱為記錄集；其中，記錄由ID、緯度、經度、字符串組成。

3.根據權利要求2所述的基于Geo-BTree的范圍查詢方法，其特征在于：所述步驟110，包括下列步驟111、112：

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

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

4.根據權利要求1或2所述的基于Geo-BTree的范圍查詢方法，其特征在于：所述通過geohash算法將位置點編碼成字符串具體為：首先，將經緯度范圍看作二維平面坐標系；然后，采用二分法對經度/緯度進行劃分，根據位置點經度/緯度在劃分結果中的位置分別賦值0或1，直到劃分次數滿足對應的經/緯度位串的位數；之后，通過位交錯方法合并經度位串與緯度位串；最后，通過Base32編碼將經緯度位串編碼為相應長度的字符串。