[發明專利]空間查詢方法、設備、系統及存儲介質

有效

• 申請號: 202010224727.3
• 申請日: 2020-03-26
• 公開（公告）號: CN113449208B
• 公開（公告）日: 2022-09-02
• 發明（設計）人: 曲斌
• 申請（專利權）人: 阿里巴巴集團控股有限公司
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06F16/29;G06Q30/06
• 代理公司: 北京太合九思知識產權代理有限公司 11610
• 代理人: 張愛;劉戈

1.一種空間查詢方法，包括：

獲取待關聯的多個數據集以及查詢距離，所述多個數據集中的數據點表示各自對應的數據對象的位置信息；

根據所述查詢距離，創建空間網格，所述空間網格的網格單元寬度大于或等于所述查詢距離；

將所述多個數據集中的數據點映射至所述空間網格，以得到所述多個數據集中的數據點在所述空間網格中的分布情況；

根據所述多個數據集中的數據點在所述空間網格內的分布情況，從所述多個數據集中確定目標數據組，以得到查詢結果，包括：根據所述多個數據集中的數據點在所述空間網格內的分布情況，確定所述多個數據集中數據量最小的目標數據集中的數據點所在的目標網格單元；根據所述多個數據集中的數據點在所述空間網格內的分布情況，判斷除所述目標數據集之外的其它數據集中的數據點是否映射在所述目標網格單元的鄰域內；若判斷結果為是，則根據鄰域內映射有所述其它數據集中的數據點的第一目標網格單元以及所述其它數據集中映射在所述第一目標網格單元的鄰域內的數據點，確定所述目標數據組；

其中，所述目標數據組中屬于不同數據集的數據點之間的距離小于或等于所述查詢距離。

2.根據權利要求1所述的方法，所述根據所述查詢距離，創建空間網格，包括：

根據所述查詢距離，確定所述空間網格所需的網格單元寬度和網格單元數量；所述網格單元寬度大于或等于所述查詢距離；

按照所述空間網格組所需的網格單元寬度和所述網格單元數量，創建所述空間網格。

3.根據權利要求2所述的方法，所述根據所述查詢距離，確定空間網格所需的網格單元寬度和網格單元數量，包括：

將所述查詢距離在已知的網格精度等級中進行匹配，以確定目標網格精度等級；其中，不同網格精度等級對應不同的網格單元寬度和網格單元數量；所述目標網格精度等級是所述已知的網格精度等級中網格單元寬度大于或等于所述查詢距離且與所述查詢距離的差值最小的網格精度等級；

將所述目標網格精度等級對應的網格單元寬度和網格單元數量，作為所述空間網絡所需的網格單元寬度和網格單元數量。

4.根據權利要求3所述的方法，所述已知的空間網格精度等級為基于Hilbert曲線網格對應的網格精度等級。

5.根據權利要求1所述的方法，所述將所述多個數據集中的數據點映射至所述空間網格，包括：

對所述空間網格進行編碼，得到每個網格單元對應的編碼；

根據所述每個網格單元對應的編碼以及每個網格單元對應的坐標范圍，將所述多個數據集中的數據點映射至所述空間網格。

6.根據權利要求5所述的方法，所述對所述空間網格進行編碼，包括：

利用空間填充曲線對所述空間網格進行編碼，得到每個網格單元對應的編碼。

7.根據權利要求6所述的方法，所述空間填充曲線為希伯爾特曲線或基于希伯爾特曲線的變形曲線。

8.根據權利要求1所述的方法，所述根據鄰域內映射有所述其它數據集中的數據點的第一目標網格單元以及所述其它數據集中映射在所述第一目標網格單元的鄰域內的數據點，確定所述目標數據組，包括：

計算所述其它數據集映射在所述第一目標網格單元的鄰域內的第二數據點分別與所述目標數據集中映射在所述第一目標網格單元的第一數據點之間的距離；

從所述第二數據點中選擇與所述第一數據點之間的距離小于或等于所述查詢距離的目標數據點；并將所述目標數據點和所述第一數據點作為一個目標數據組。

9.根據權利要求1所述的方法，所述目標網格單元的鄰域包括：所述目標網格單元以及與所述目標網格單元相鄰的網格單元確定的區域。

10.根據權利要求1所述的方法，在得到所述查詢結果之后，所述方法還包括：

輸出所述目標數據組；和/或，輸出所述目標數據組的關聯信息。