[發明專利]基于p-stable lsh的時空伴隨查詢方法

在審

• 申請號: 202110292813.2
• 申請日: 2021-03-18
• 公開（公告）號: CN112988797A
• 公開（公告）日: 2021-06-18
• 發明（設計）人: 胡宇飛;陳成斌;葉智慧;蘇勝林;馬軍亮
• 申請（專利權）人: 中睿信數字技術有限公司
• 主分類號: G06F16/2453
• 分類號: G06F16/2453;G06F16/22;G06F16/29;G06F21/64
• 代理公司: 北京冠和權律師事務所 11399
• 代理人: 吳金水

本發明公開了基于p?stable lsh的時空伴隨查詢方法，包括：獲取時空伴隨對象軌跡的離線數據，對所述離線數據進行預處理，生成多維向量數據；基于p?stable lsh算法將所述多維向量數據生成離線的對象軌跡的數字簽名；將所述離線的數字簽名同步至在線的數據查詢大數據庫中；基于所述在線的數據查詢大數據庫，構建快速檢索工具，根據所述數字簽名查詢相似目標對象。采用p?stable lsh算法對整個軌跡做hash變換，使得軌跡維度大大降低，將復雜的伴隨分析轉變成指紋(hash值)比對，極大地提高了查詢效率及查詢效果，同時采用geohash做經緯度降維，對一定范圍內的經緯度誤差可以完成歸一化處理。此外，采用在線和離線結合的方式，極大的提升了用戶體驗。

技術領域

本發明涉及數據處理的技術領域，具體涉及基于p-stable lsh的時空伴隨查詢方法。

背景技術

時空軌跡是移動對象的位置和時間的記錄序列。作為一種重要的時空對象數據類型，時空軌跡的應用涵蓋了人類行為、交通物流等諸多方面。通過對各種時空軌跡數據進行分析，可以得到時空軌跡數據中的相似性異常特征，有助于發現其中有意義的軌跡模式。伴隨模式是時空軌跡模式中的一種，在交通管理，資源分配等領域有著重要的應用。

現有技術中，對時空軌跡的移動對象進行查詢方法一般采用geohash做時空軌跡伴隨，或者，將相鄰的幾個基站劃分成一個組并給一個組編號。然后利用組編號來做基于基站的時空軌跡伴隨。此方法僅適用于基站軌跡，并且對基站分組的要求較高，分組的效果直接影響最終伴隨結果。

但是，現有技術的方案都只是針對經緯度做hash變換，將經緯度降維。在時空比對過程中，依然要通過統計、碰撞等業務邏輯來實現，效率和效果方面都大打折扣，尤其是在海量數據情況下，效率低及效果差的問題顯得尤為突出。因此，亟需一種可以提高查詢效率及提高查詢效果的方法實現時空伴隨的查詢。

發明內容

本發明提供基于p-stable lsh的時空伴隨查詢方法，用以解決現有技術中存在的時空伴隨查詢效率低及效果差的問題。

本發明提供基于p-stable lsh的時空伴隨查詢方法，該方法包括：

獲取時空伴隨對象軌跡的離線數據；

對所述離線數據進行預處理，生成多維向量數據；所述預處理包括基于geohash算法按照時間節點生成的針對對象軌跡的位置點經緯度的多維向量數據；

基于p-stable lsh算法將所述多維向量數據生成離線的對象軌跡的數字簽名；

將所述離線的數字簽名同步至在線的數據查詢大數據庫中；

基于所述在線的數據查詢大數據庫，構建快速檢索工具，根據所述數字簽名查詢相似目標對象。

可選的，所述對所述離線數據進行預處理，生成多維向量數據，包括：

將對象軌跡的所有位置點基于geohash算法進行編碼；

按照預先設定的時間片段長度將預設的總時間長度進行時間切片處理，將總的時間長度切分為若干個時間切片；

對每個時間切片中的位置點的出現的geohash編碼進行排序，提取出現次數最多的geohash編碼作為相應位置點的geohash編碼；

將所有時間切片中的相應位置點geohash編碼的經緯度數據提取形成多維向量數據。

可選的，所述基于p-stable lsh算法將所述多維向量數據生成離線的對象軌跡的數字簽名，包括：

對所述多維向量數據中的每個向量附加hash值；

根據哈希碰撞概率公式確定分桶大小w；