[發明專利]一種相似軌跡搜索方法和系統

有效

• 申請號: 201810725065.0
• 申請日: 2018-07-04
• 公開（公告）號: CN110688435B
• 公開（公告）日: 2022-04-05
• 發明（設計）人: 丁建棟
• 申請（專利權）人: 北京嘀嘀無限科技發展有限公司
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06Q30/06;G06Q50/30
• 代理公司: 成都七星天知識產權代理有限公司 51253
• 代理人: 楊永梅

本發明公開了一種相似軌跡搜索方法、系統、裝置和存儲介質。主要包括一種相似軌跡搜索方法，所述方法包括：基于預設網格大小，確定地理區域的網格劃分；基于所述網格及所述地理區域內的目標軌跡點的先后順序，映射所述目標軌跡為定長的目標網格序列；映射所述定長的目標網格序列為縮短的定長目標特征向量；基于所述縮短的定長目標特征向量，確定與所述目標軌跡相似的軌跡集合。該發明可以實現搜索相似軌跡的功能。

技術領域

本技術涉及互聯網領域，特別涉及一種相似軌跡搜索的方法和系統。

背景技術

近年來，隨著通訊網絡、車聯網技術以及移動物聯網的快速發展，使用車載或者手機內置的傳感器收集車輛的移動軌跡已經變成了一個非常普遍的現象。出行軌跡的相似度分析是近年來的一大熱點，而傳統的軌跡分析方式僅僅對軌跡的起止點進行分析，并不足以滿足現在車輛共享業務的需求。

發明內容

本發明的一部分附加特性可以在下面的描述中進行說明。通過對以下描述和相應附圖的檢查或者對實施例的生產或操作的了解，本發明的一部分附加特性對于本領域技術人員是顯而易見的。本發明的特性可以通過對以下描述的具體實施例的各種方面的方法、手段和組合的實踐或使用得以實現和達到。

一方面，本發明實施例提供了一種相似軌跡搜索方法，可以包括：基于預設網格大小，確定地理區域的網格劃分；基于所述網格及所述地理區域內的目標軌跡點的先后順序，映射所述目標軌跡為定長的目標網格序列；映射所述定長的目標網格序列為縮短的定長目標特征向量；基于所述縮短的定長目標特征向量，確定與所述目標軌跡相似的軌跡集合。

在本發明中，所述基于所述縮短的定長目標特征向量，確定與所述目標軌跡相似的軌跡集合還包括：將數據庫中的所有軌跡轉化為縮短的定長特征向量集合；基于所述縮短的定長特征向量集合，生成索引數據庫；基于所述縮短的定長目標特征向量與所述索引數據庫中的特征向量的相似度，確定與所述目標軌跡相似的軌跡集合。

在本發明中，所述基于所述縮短的定長目標特征向量與所述索引數據庫中的特征向量的相似度，確定與所述目標軌跡相似的軌跡集合還可以包括基于距離算法及所述縮短的定長目標特征向量，確定與所述目標軌跡相似的軌跡集合。

在本發明中，所述距離可以包括漢明距離。

在本發明中，所述基于所述定長的特征向量集合，生成索引數據庫可以在離線時完成。

在本發明中，所述索引數據庫可以定時更新。

在本發明中，所述映射所述目標網格序列為目標特征向量具體可以為基于n元語法映射所述目標網格序列為目標特征向量。

在本發明中，所述n＝2。

在本發明中，所述映射所述目標特征向量為縮短的定長目標特征向量具體可以為基于哈希函數映射所述目標特征向量為縮短的定長目標特征向量。

在本發明中，所述基于哈希函數映射所述目標特征向量為縮短的定長目標特征向量還可以包括基于機器學習模型尋找合理的哈希函數。

在本發明中，所述機器學習模型的目標函數可以包括經驗風險最小目標函數。

另一方面，本發明實施例提供了一種相似軌跡搜索系統，可以包括網格劃分模塊、第一映射模塊、第二映射模塊和確定模塊：所述網格劃分模塊用于基于預設網格大小，確定區域的網格劃分；所述第一映射模塊用于基于所述網格及所述區域內的目標軌跡點的先后順序，映射所述目標軌跡為定長的目標網格序列；所述第二映射模塊用于映射所述定長的目標網格序列為縮短的定長目標特征向量；所述確定模塊用于基于所述縮短的定長目標特征向量，確定與所述目標軌跡相似的軌跡集合。

另一方面，本發明實施例提供了一種相似軌跡搜索的裝置，可以包括處理器，所述處理器運行搜搜程序，所述搜索程序運行時執行如上任一所述的相似軌跡搜索的方法。