TY - JOUR
T1 - Trajectory splicing
AU - Lu, Qiang
AU - Wang, Rencai
AU - Yang, Bin
AU - Wang, Zhiguang
PY - 2020
Y1 - 2020
N2 - With continued development of location-based systems, large amounts of trajectories become available which record moving objects’ locations across time. If the trajectories collected by different location-based systems come from the same moving object, they are spliceable trajectories, which contribute to representing holistic behaviors of the moving object. In this paper, we consider how to efficiently identify spliceable trajectories. More specifically, we first formalize a spliced model to capture spliceable trajectories where their times are disjoint, and the distances between them are close. Next, to efficiently implement the model, we design three components: a disjoint time index, a directed acyclic graph of sub-trajectory location connections, and two splice algorithms. The disjoint time index saves a disjoint time set of each trajectory for querying disjoint time trajectories efficiently. The directed acyclic graph contributes to discovering groups of spliceable trajectories. Based on the identified groups, the splice algorithm findmaxCTR finds maximal groups containing all spliceable trajectories. Although the splice algorithm is efficient in some practical applications, its running time is exponential. Therefore, an approximate algorithm findApproxMaxCTR is proposed to find trajectories which can be spliced with each other with a certain probability within polynomial run time. Finally, experiments on two datasets demonstrate that the model and its components are effective and efficient.
AB - With continued development of location-based systems, large amounts of trajectories become available which record moving objects’ locations across time. If the trajectories collected by different location-based systems come from the same moving object, they are spliceable trajectories, which contribute to representing holistic behaviors of the moving object. In this paper, we consider how to efficiently identify spliceable trajectories. More specifically, we first formalize a spliced model to capture spliceable trajectories where their times are disjoint, and the distances between them are close. Next, to efficiently implement the model, we design three components: a disjoint time index, a directed acyclic graph of sub-trajectory location connections, and two splice algorithms. The disjoint time index saves a disjoint time set of each trajectory for querying disjoint time trajectories efficiently. The directed acyclic graph contributes to discovering groups of spliceable trajectories. Based on the identified groups, the splice algorithm findmaxCTR finds maximal groups containing all spliceable trajectories. Although the splice algorithm is efficient in some practical applications, its running time is exponential. Therefore, an approximate algorithm findApproxMaxCTR is proposed to find trajectories which can be spliced with each other with a certain probability within polynomial run time. Finally, experiments on two datasets demonstrate that the model and its components are effective and efficient.
KW - Trajectory computation
KW - Trajectory fusion
KW - Trajectory linking
KW - Trajectory recovery
UR - http://www.scopus.com/inward/record.url?scp=85069471740&partnerID=8YFLogxK
U2 - 10.1007/s10115-019-01382-x
DO - 10.1007/s10115-019-01382-x
M3 - Journal article
AN - SCOPUS:85069471740
SN - 0219-1377
VL - 62
SP - 1279
EP - 1312
JO - Knowledge and Information Systems
JF - Knowledge and Information Systems
IS - 4
ER -