[發明專利]基于路網的移動對象位置索引結構及索引方法

有效

• 申請號: 201310178443.5
• 申請日: 2013-05-15
• 公開（公告）號: CN103235831A
• 公開（公告）日: 2013-08-07
• 發明（設計）人: 余建橋;王芹;譚曉天
• 申請（專利權）人: 西南大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京海虹嘉誠知識產權代理有限公司 11129
• 代理人: 謝殿武

1.一種基于路網的移動對象位置索引結構，其特征在于：包括：針對路網建立的上層索引結構和針對路網中的移動對象建立的下層索引結構，所述上層索引結構包括：路網R樹，路徑哈希表和交叉口轉向表，所述下層索引結構包括：移動對象R樹、靜態對象R樹、移動對象哈希表和動態鏈表。

2.如權利要求1所述的基于路網的移動對象位置索引結構，其特征在于：

所述路網R樹為二維路網R樹，且所述路網R樹的葉子節點的數據結構包括：路徑標識號、指向移動對象R樹的指針、指向靜態對象R樹的指針、與路徑哈希表中指針相對應的雙向指針和限行標志；

所述路徑哈希表的數據結構包括：路徑標識號、限行標志、路徑所含交叉口標識和指向路網R樹中對應葉子節點的指針；

所述交叉口轉向表的數據結構包括：交叉口標識、可轉向路徑標識和交叉口位置屬性。

3.如權利要求1或2所述的基于路網的移動對象位置索引結構，其特征在于：所述靜態對象R樹的每個葉子結點均指向一個最近鄰鏈表，且所述靜態對象R樹中葉子結點的數據結構包括：靜態對象標識號、靜態對象位置信息和靜態對象名稱；

所述移動對象R樹中的葉子結點的數據結構包括：移動對象標識號、移動對象在路徑中的運動方向、路徑標識號、以及指向動態鏈表中相應結點的指針；

所述移動對象哈希表的數據結構包括：移動對象標識號、移動對象插入表的時間、移動對象插入表時的速度、移動對象插入表時的相對位置，指向動態鏈表隊首的指針、以及指向動態鏈表隊尾的指針；

所述動態鏈表數據結構包括：移動對象標識號，移動對象當前所處的路徑標識號，更新移動對象時的速度、時間、移動方向，移動對象在路徑中的相對位置，以及指向移動對象R樹中對應葉子結點的指針。

4.一種基于權利要求1-3中任一項的索引結構的移動對象位置的索引方法，該方法用于預測移動對象過去將來時刻的位置，其特征在于：包括：

接收預測移動對象在t時刻的位置的預測請求；

若t介于移動對象兩次更新的時刻t_i和t_i+1之間，則根據移動對象的位置偏移預測移動對象在t時刻的位置f_pos1和根據移動對象的平均速度預測移動對象在t時刻的位置f_pos2；

根據f_pos1和f_pos2預測移動對象在t時刻的最終預測位置f_pos。