QS-STT: QuadSection clustering and spatial-temporal trajectory model for location prediction

Po Ruey Lei, Shou Chung Li, Wen-Chih Peng*

*Corresponding author for this work

研究成果: Article同行評審

13 引文 斯高帕斯(Scopus)

摘要

Location prediction is a crucial need for location-aware services and applications. Given an object's recent movement and a future time, the goal of location prediction is to predict the location of the object at the future time specified. Different from traditional location prediction using motion function, some research works have elaborated on mining movement behavior from historical trajectories for location prediction. Without loss of generality, given a set of trajectories of an object, prior works on mining movement behaviors will first extract regions of popularity, in which the object frequently appears, and then discover the sequential relationships among regions. However, the quality of the frequent regions extracted affects the accuracy of the location prediction. Furthermore, trajectory data has both spatial and temporal information. To further enhance the accuracy of location prediction, one could utilize not only spatial information but also temporal information to predict the locations of objects. In this paper, we propose a framework QS-STT (standing for QuadSection clustering and Spatial-Temporal Trajectory model) to capture the movement behaviors of objects for location prediction. Specifically, we have developed QuadSection clustering to extract a reasonable and near-optimal set of frequent regions. Then, based on the set of frequent regions, we propose a spatial-temporal trajectory model to explore the object's movement behavior as a probabilistic suffix tree with both spatial and temporal information of movements. Note that STT is not only able to discover sequential relationships among regions but also derives the corresponding probabilities of time, indicating when the object appears in each region. Based on STT, we further propose an algorithm to traverse STT for location prediction. By enhancing the quality of the frequent region extracted and exploring both the spatial and temporal information of STT, the accuracy of location prediction in QS-STT is improved. QS-STT is designed for individual location prediction. For verifying the effectiveness of QS-STT for location prediction under the different spatial density, we have conducted experiments on four types of real trajectory datasets with different speed. The experimental results show that our proposed QS-STT is able to capture both spatial and temporal patterns of movement behaviors and by exploring QS-STT, our proposed prediction algorithm outperforms existing works.

原文English
頁(從 - 到)231-258
頁數28
期刊Distributed and Parallel Databases
31
發行號2
DOIs
出版狀態Published - 1 六月 2013

指紋 深入研究「QS-STT: QuadSection clustering and spatial-temporal trajectory model for location prediction」主題。共同形成了獨特的指紋。

引用此