[發明專利]一種基于Flink的實時軌跡co-movement運動模式檢測方法

有效

• 申請號: 201910044540.2
• 申請日: 2019-01-17
• 公開（公告）號: CN109800231B
• 公開（公告）日: 2020-12-08
• 發明（設計）人: 高云君;陳璐;房子荃;潘璐
• 申請（專利權）人: 浙江大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/28;G06F16/2458
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 邱啟旺

1.一種基于Flink的實時軌跡co-movement運動模式檢測方法，其特征在于，該方法的步驟如下：

步驟（1）對應用中某段時間的實時軌跡數據進行收集，得到樣本數據；

步驟（2）對得到的樣本數據根據時間戳進行離散化得到多個快照；

步驟（3）利用步驟（2）中得到的每個快照，對其數據構建GR-index，得到相應的空間劃分；

步驟（4）在聚類階段，根據步驟（3）中得到的空間劃分，對其中的數據進行范圍查詢以及使用DBSCAN方法聚類；所述步驟（4）具體為：

步驟（4.1）首先對步驟（3）得到的空間劃分進行范圍查詢，找到符合DBSCAN要求的中心對象以及符合距離要求的可達對象，形成鄰域；

步驟（4.2）再使用DBSCAN聚類方法對每張移動對象快照進行聚類得到簇快照；

步驟（5）在枚舉階段，對步驟（4）中得到的聚類后的每個快照使用基于id的分區技術，實時枚舉，輸出每個時間片符合約束條件的co-movement運動模式，所述步驟（5）具體為：

步驟（5.1）在枚舉階段，對于每個簇快照，用基于id的分區技術進行分區，然后根據約束條件枚舉出每個時間片對應的運動模式；

步驟（5.2）利用兩種壓縮算法，即固定長度位壓縮方法FBA和不固定長度位壓縮方法UBA，減少基于id分區技術的時間復雜度以及存儲開銷；

所述固定長度位壓縮方法FBA和不固定長度位壓縮方法UBA算法是指：固定長度位壓縮方法FBA通過給定某個分區Pt (o)里的一個軌跡o_i，一個固定的位串B[o_i]用來表示o_i，其中|B[o_i]|=η，如果B[o_i ][j] = 1 (0 ≤ j ≤ η?1)表示o與o_i在時間t+j內屬于同一個簇，B[o_i ][j] = 0則表示o與o_i在時間t+j內不屬于同一個簇，該算法用來表示η個快照內該移動對象是否與同個id分區內的特定軌跡屬于同一個簇；不固定長度位壓縮方法UBA則通過給定某個與軌跡o同屬于一個子任務的軌跡o_i，一個不固定的位串?st_i , et_i , B[o_i ]?來表示o_i,st_i代表起始時間片，et_i代表終止時間片，如果B[o_i ][t ?st_i ] = 1表示o與o_i在t ∈[st_i , et_i ]內屬于同一個簇，B[o_i ][t ?st_i ] = 0則表示o與o_i不屬于同一個簇，該算法減少固定長度位壓縮方法FBA里不必要的快照驗證，判斷該時間片序列內該移動對象是否與同個id分區內的特定軌跡屬于同一個簇；

所述基于id的分區技術是指：對于每個簇快照t，將特定軌跡o的分區Pt (o)分配給其相應的id，其余與o在相同簇的擁有更大id的移動對象分配給這個分區Pt (o)。

2.根據權利要求1所述的基于Flink的實時軌跡co-movement運動模式檢測方法，其特征在于：所述步驟（2）具體為：

步驟（2.1）將處于同一個時間段的移動對象數據聚集到一起，給定一個時間片長度和時間片起始時刻，將實際時間轉換成時間片；

步驟（2.2）將擁有相同時間片的移動對象放在一起處理，并且會追蹤移動對象更新后的時間片信息last time；

步驟（2.3）根據時間片信息確保移動對象有序的被處理，并且可以確認某一時間片的移動對象位置丟失是由于本身還是Flink操作失誤所致；最后得到多個快照，每個快照內的移動對象的時間片信息相同。

3.根據權利要求2所述的基于Flink的實時軌跡co-movement運動模式檢測方法，其特征在于：所述步驟（3）具體為：

步驟（3.1）對步驟（2）得到的每個快照，對其中的移動對象建立全局網格索引；

步驟（3.2）對步驟（3.1）得到的每個網格計算其鍵的值，與Flink中的分區相對應；

步驟（3.3）對每個網格內的移動對象建立局部R樹索引，葉子結點代表每個移動對象的實際位置；

步驟（3.4）步驟（2）的每個快照經過網格索引與R樹索引處理后得到空間劃分結果。