[發明專利]一種路網移動對象預測概率范圍查詢方法

有效

• 申請號: 201811060534.8
• 申請日: 2018-09-12
• 公開（公告）號: CN109359164B
• 公開（公告）日: 2022-03-25
• 發明（設計）人: 史涯晴;黃松;李輝;鄭長友;洪宇;韓敬利;王兆麗;王梅娟
• 申請（專利權）人: 中國人民解放軍陸軍工程大學
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/22;G06F16/245
• 代理公司: 南京鐘山專利代理有限公司 32252
• 代理人: 戴朝榮

1.一種路網移動對象預測概率范圍查詢方法，其特征在于，包括以下步驟：

步驟1：依據Hash表定位查詢條件中查詢路段RID所在空間索引葉結點，定位對應時間索引B⁺-tree根結點；

步驟2：找到所有移動對象OID早于預測時刻t_c的最晚采樣點sample_s，形成sample_s數據集；

步驟3：將所有待查詢的sample_s數據集分割為M個片段，對應M個Map任務；

步驟4：調用Map函數處理空間限制，實現Map操作，具體包括：

步驟4.1：對于輸入的sample_s，判斷其OID在t_c時刻是否可能處于路段RID；

步驟4.2：符合空間限制條件則依據sample_s判斷所屬空間索引葉結點表示的子劃分，輸出子劃分ID,sample_s；

步驟4.3：依據子劃分ID將輸出集進行排序，生成元組子劃分ID,list；

步驟5：調用Reduce函數處理可能路徑查詢和概率計算，實現Reduce操作，具體包括：

步驟5.1：執行t_s與t_c時刻間移動對象OID的可能路徑查詢；

步驟5.2：利用時間關系計算u、v間可能路徑ph(u,v)內路段RID上的位置概率

步驟6：設置輸入與輸出路徑，開始MapReduce并行運算；

步驟7：調用子查詢結果合并程序，將所有查詢結果合并成完整的結果。

2.如權利要求1所述的一種路網移動對象預測概率范圍查詢方法，其特征在于，步驟1具體包括：

構建時空間多維索引結構：空間維度為路網索引結構，通過各層結點的邊界頂點、鄰接矩陣、路段最大限速行駛下的最短時間表示路網關系，解決可能路徑查詢，設計Hash表將空間維度的葉結點與其中的路段RID快速對應；

時間維度采用基于時間粒度的B⁺-tree索引創建方式，對采樣時間點基于上層粒度進行索引；

查詢進行中逐步記錄下結點邊界頂點間路徑以Region表形式保存，實現間接索引部分不確定數據。

3.如權利要求1所述的一種路網移動對象預測概率范圍查詢方法，其特征在于，步驟4.1具體包括：

如果移動對象OID預測時刻t_c在路段RID上，則其在RID上的可能位置必定在路段RID的兩個頂點v_s與v_e之間；

假設v_i為路段RID上v_s與v_e之間任意一點，t_c時刻OID在v_i點，sample_s為所有OID早于預測時刻t_c的最晚采樣點，t_s為其采樣時刻；

設sample_s與v_i的最大時間間隔設為Δt，則Δt必須滿足Δt≤t_c-t_s，移動對象速度的最大值取實際城市道路的最大限速s_max＝70km/h，故sample_s與v_i的路網距離r≤(t_c-t_s)﹒s_max，可以得到以v_i為圓心，(t_c-t_s)﹒s_max為半徑的圓形區域，又因為v_i的邊界位置分別為v_s與v_e，因而圓心的取值范圍為[v_s,v_e]，將圓形區域沿著圓心從v_s推至v_e，形成空間限制區域。