Qiang Lu · Rencai Wang · Bin Yang · Zhiguang Wang.

Received: 23 September 2018 / 30 June 2019

Abstract

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.

More info about thie paper

Please see KAIS-Link

Code Link

Please see Code on our GitHub.