[發明專利]一種基于時隙的時空索引方法

在審

• 申請號: 202011362738.4
• 申請日: 2020-11-27
• 公開（公告）號: CN112395467A
• 公開（公告）日: 2021-02-23
• 發明（設計）人: 陳剛;龐志飛;魯鵬;伍賽;姚暢
• 申請（專利權）人: 浙江大學計算機創新技術研究院
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/909;G06F16/29
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 林超

本發明公開了一種基于時隙的時空索引方法。根據運動對象的軌跡，構建TS?TPR索引結構，將實時獲得的預測軌跡插入到TS?TPR中對應的TPR樹中；批量更新TS?TPR索引結構中的軌跡數據；以分而治之方式使用TS?TPR回答預測性時空查詢。通過本發明的索引能索引預測軌跡，可以索引連續軌跡，完成有關的預測性查詢，提升了預測性查詢的準確率。

技術領域

本發明涉及數據庫領域中的時空索引技術，具體涉及到一種基于時隙的時空索引技術。

背景技術

在時空數據庫中，預測性時空查詢被廣泛用于回答諸如“10分鐘后返回1平方公里以內的對象”之類的問題。這類時空查詢可以表示為三元組t_s，t_e，R，其中t_s是查詢開始的時間，t_e是查詢結束時間，R是多維多邊形(Multi-dimensional Polygon)。為了回答這類查詢，研究人員們提出了一系列具有時間參數的索引。這些索引針對未來[t_c，t_c+H]的預測性時空查詢進行了優化，其中t_c是當前時間，而參數H則稱為“視野(Horizon)”，表示將來索引可以“看到”未來多遠。

TPR(Time Parameterized Tree)樹是使用最廣泛的一種的時空索引。TPR樹中的移動模型是由線性函數來表示的。傳統TPR樹回答的預測性查詢只是依賴當前對象的速度以及位置，并應用線性模型來預測未來某一個時刻的位置。例如，假設r是TPR樹在時間t被索引的運動對象。r的當前位置為r_l，速度為r_v。根據線性運動模型來計算，該對象在任何將來時間t_f的位置為r_l+(t_f-t)×r_v。

近年來，人工智能迅速發展，越來越多的模型可以準確的預測運動對象最近一段時間內的運動軌跡。例如，給定某個移動物體的過去10分鐘的軌跡，預測模型可以給出未來10分鐘該對象每分鐘的位置坐標。智能模型對軌跡的預測準確率遠遠高于僅應用直線運動模型的準確率。因此當使用智能模型來替換TPR樹中的直線運動模型將會極大地提高預測性查詢的準確性。然而，傳統的TPR樹無法索引利用這些預測的軌跡信息，即無法索引未來一段時間的軌跡，只能保存當前時間點位置和速度。

發明內容

針對現有技術的不足，為了解決背景技術中存在的問題，本發明的目的在于提供了一種基于時隙的時空索引(TS-TPR，Time-slot based TPR)以及相關的構建、更新以及查詢方法。

本發明所采用的技術方案如下：

1)根據運動對象的軌跡，構建TS-TPR索引結構，將實時獲得的預測軌跡插入到TS-TPR中對應的TPR樹中；

2)批量更新TS-TPR索引結構中的軌跡數據；

3)以分而治之方式使用TS-TPR回答預測性時空查詢。

所述步驟1)中，

1.1)根據預測軌跡，確定TS-TPR索引結構的關鍵參數，關鍵參數是時隙的長度Δt；按照以下公式處理確定時隙的長度Δt：

Δt＝H/m

其中，m表示TS-TPR索引結構中建立的TPR樹的數量，H表示TS-TPR索引結構的預測性查詢最長時間；

1.2)TS-TPR索引結構由若干TPR樹(Time-Parameterized Tree)組成，若干TPR樹之間按照時序排列，相鄰TPR樹之間具有時間間隔，且時間間隔相等作為時隙；各個TPR樹存儲有運動對象的軌跡中各個時刻的位置和速度信息，同一TPR樹存儲有各個運動對象在同一時刻的位置坐標和速度信息，不同TPR樹存儲有各個運動對象在不同時刻的位置和速度信息。