TY - GEN
T1 - Moving Object Linking Based on Historical Trace
AU - Jin, Fengmei
AU - Hua, Wen
AU - Xu, Jiajie
AU - Zhou, Xiaofang
N1 - Funding Information:
This work was partially supported by the National Natural Science Foundation of China under Grant No. 61772356, 61872258, and the Open Program of Neusoft Corporation under item number SKLSAOP1801.
Publisher Copyright:
© 2019 IEEE.
PY - 2019/4
Y1 - 2019/4
N2 - The prevalent adoption of GPS-enabled devices has witnessed an explosion of various location-based services which produce a huge amount of trajectories monitoring an individual's movement. This triggers an interesting question: is movement history sufficiently representative and distinctive to identify an individual? In this work, we study the problem of moving object linking based on their historical traces. However, it is non-trivial to extract effective patterns from moving history and meanwhile conduct object linking efficiently. To this end, we propose four representation strategies (sequential, temporal, spatial, and spatiotemporal) and two quantitative criteria (commonality and unicity) to construct the personalised signature from the historical trace. Moreover, we formalise the problem of moving object linking as a k-nearest neighbour (k-NN) search on the collection of signatures, and aim to improve efficiency considering the high dimensionality of signatures and the large cardinality of the candidate object set. A simple but effective dimension reduction strategy is introduced in this work, which empirically outperforms existing algorithms including PCA and LSH. We propose a novel indexing structure, Weighted R-tree (WR-tree), and two pruning methods to further speed up k-NN search by combining weight and spatial information contained in the signature. Our extensive experimental results on a real world dataset verify the superiority of our proposals, in terms of both accuracy and efficiency, over state-of-the-art approaches.
AB - The prevalent adoption of GPS-enabled devices has witnessed an explosion of various location-based services which produce a huge amount of trajectories monitoring an individual's movement. This triggers an interesting question: is movement history sufficiently representative and distinctive to identify an individual? In this work, we study the problem of moving object linking based on their historical traces. However, it is non-trivial to extract effective patterns from moving history and meanwhile conduct object linking efficiently. To this end, we propose four representation strategies (sequential, temporal, spatial, and spatiotemporal) and two quantitative criteria (commonality and unicity) to construct the personalised signature from the historical trace. Moreover, we formalise the problem of moving object linking as a k-nearest neighbour (k-NN) search on the collection of signatures, and aim to improve efficiency considering the high dimensionality of signatures and the large cardinality of the candidate object set. A simple but effective dimension reduction strategy is introduced in this work, which empirically outperforms existing algorithms including PCA and LSH. We propose a novel indexing structure, Weighted R-tree (WR-tree), and two pruning methods to further speed up k-NN search by combining weight and spatial information contained in the signature. Our extensive experimental results on a real world dataset verify the superiority of our proposals, in terms of both accuracy and efficiency, over state-of-the-art approaches.
KW - Dimension reduction
KW - Historical trace
KW - K-nn search
KW - Moving object linking
KW - Signature
KW - Weighted r-tree
UR - http://www.scopus.com/inward/record.url?scp=85067930409&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2019.00098
DO - 10.1109/ICDE.2019.00098
M3 - Conference article published in proceeding or book
AN - SCOPUS:85067930409
T3 - Proceedings - International Conference on Data Engineering
SP - 1058
EP - 1069
BT - Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
PB - IEEE Computer Society
T2 - 35th IEEE International Conference on Data Engineering, ICDE 2019
Y2 - 8 April 2019 through 11 April 2019
ER -