[發明專利]一種路網移動環境下的KNN查詢方法及系統

有效

• 申請號: 201710690023.3
• 申請日: 2017-08-14
• 公開（公告）號: CN107291963B
• 公開（公告）日: 2020-11-24
• 發明（設計）人: 吳洪麗
• 申請（專利權）人: 海南師范大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/29;G06F16/9535;G06F16/9537
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 陳歡

1.一種路網移動環境下的KNN查詢方法，其特征在于，包括：

獲取路網中移動對象和移動查詢點之間的距離范圍；

根據所述距離范圍在給定時間段內持續獲取所述移動對象信息，得到第一候選集；

將所述第一候選集中不可能成為所述移動查詢點的KNN查詢結果的所述移動對象信息過濾掉，得到第二候選集；

根據所述第二候選集向第三方互聯網地圖服務商發送時空查詢請求，并接收所述第三方互聯網地圖服務商返回的距離度量；

基于所述距離度量生成所述移動查詢點的KNN查詢結果；

為減少向第三方互聯網地圖服務商發送請求的次數，采用共享執行技術對時空查詢進行優化，通過分組相似的請求并通過空間連接以組為單位處理請求，能夠支持大規模的并發連續的范圍查詢和k最近鄰查詢請求；

所述根據所述第二候選集向第三方互聯網地圖服務商發送時空查詢請求，包括：

對所述第二候選集中的所述移動對象信息進行聚類，得到第一聚類結果，根據所述第一聚類結果向第三方互聯網地圖服務商發送時空查詢請求；

或對所述時空查詢請求進行聚類，得到第二聚類結果，并根據所述第二聚類結果向第三方互聯網地圖服務商發送時空查詢請求。

2.根據權利要求1所述的方法，其特征在于，所述獲取路網中移動對象和移動查詢點之間的距離范圍，包括：

獲取路網中所述移動對象和所述移動查詢點之間的最大距離；

獲取路網中所述移動對象和所述移動查詢點之間的最小距離；

根據所述最大距離和所述最小距離計算所述移動對象和所述移動查詢點之間的距離范圍。

3.根據權利要求1所述的方法，其特征在于，所述將所述第一候選集中不可能成為所述移動查詢點的KNN查詢結果的所述移動對象信息過濾掉，包括：

采用修剪算法刪減所述第一候選集中不可能成為所述移動查詢點的KNN查詢結果的所述移動對象信息。

4.根據權利要求1所述的方法，其特征在于，所述基于所述距離度量生成所述移動查詢點的KNN查詢結果，包括：

根據所述距離度量計算所述移動對象成為所述移動查詢點的KNN查詢結果的概率；

根據所述概率對所述移動對象進行降序排列，篩選前K個所述移動對象。

5.一種路網移動環境下的KNN查詢系統，其特征在于，包括：

第一獲取模塊，用于獲取路網中移動對象和移動查詢點之間的距離范圍；

第一構建模塊，用于根據所述距離范圍在給定時間段內持續獲取所述移動對象信息，得到第一候選集；

第二構建模塊，用于將所述第一候選集中不可能成為所述移動查詢點的KNN查詢結果的所述移動對象信息過濾掉，得到第二候選集；

查詢模塊，用于根據所述第二候選集向第三方互聯網地圖服務商發送時空查詢請求，并接收所述第三方互聯網地圖服務商返回的距離度量；為減少向第三方互聯網地圖服務商發送請求的次數，采用共享執行技術對時空查詢進行優化，通過分組相似的請求并通過空間連接以組為單位處理請求，能夠支持大規模的并發連續的范圍查詢和k最近鄰查詢請求；

生成模塊，用于基于所述距離度量生成所述移動查詢點的KNN查詢結果；

所述查詢模塊包括：

第一聚類模塊，用于對所述第二候選集中的所述移動對象信息進行聚類，得到第一聚類結果，根據所述第一聚類結果向第三方互聯網地圖服務商發送時空查詢請求；

第二聚類模塊，用于對所述時空查詢請求進行聚類，得到第二聚類結果，并根據所述第二聚類結果向第三方互聯網地圖服務商發送時空查詢請求。

6.根據權利要求5所述的系統，其特征在于，所述第一獲取模塊包括：

第二獲取模塊，用于獲取路網中所述移動對象和所述移動查詢點之間的最大距離；

第三獲取模塊，用于獲取路網中所述移動對象和所述移動查詢點之間的最小距離；

距離計算模塊，用于根據所述最大距離和所述最小距離計算所述移動對象和所述移動查詢點之間的距離范圍。