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 arespliceable 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 algorithmfindmaxCTR 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 algorithmfindApproxMaxCTR 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.

1. Namely\((ti(\textit{STR}_m^n) \subset gap(\textit{STR}_i^j,\textit{STR}_i^{j+1}))\)\(\cap \)\((ti(\textit{STR}_i^j) \subset gap(\textit{STR}_m^{n-1},\textit{STR}_m^{n}))\)\(\cap \)\( (d(last(\textit{STR}{_i^j}),\)\(first(\textit{STR}{_m^n}))\le \gamma )\).

2. https://en.wikipedia.org/wiki/Dense_graph.

We would like to thank Professor Christian S. Jensen for useful discussions and comments. This work was supported by National Science and Technology Major Project (no. 2017ZX05018-005), National Natural Science Foundation of China (no. 61402532), Science Foundation of China University of Petroleum-Beijing (no. 01JB0415), and China Scholarship Council.

Authors and Affiliations

1. Beijing Key Lab of Petroleum Data Mining, China University of Petroleum-Beijing, Beijing, China

   Qiang Lu, Rencai Wang & Zhiguang Wang

2. Department of Computer Science, Aalborg University, Aalborg, Denmark

   Bin Yang

3. IFLYTEK CO.,LTD, Hefei, China

   Rencai Wang

Corresponding author

Correspondence toQiang Lu.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A Computing disjoint time set

Lemma

In the query interval timeT, the disjoint time set\(\textit{DT}_i\) of each trajectory\(\textit{TR}_i\) can be computed by Eq.6.

Proof

Let\(Q_i^{k,d}\) be a trajectory set where each trajectory\(\textit{TR}\) appears inT and its time interval set\(ti(\textit{TR})\) does not overlap with\(\textit{TR}_i\) in thekth time slice. So,\(Q_i^{k,d}=\textit{DT}_i^{k,d}\cup R^{k,d}\), where\(R^{k,d}\) is a trajectory set in which each trajectory appears inT except in thekth time slice. For example, in Fig. 2, assumed\(T=[0,3d]\),\(R_A^{3,d}=\lbrace D,E \rbrace \) and\(\textit{DT}_A^{3,d}=\lbrace B,C\rbrace \). Then,\(Q_A^{3,d}=\lbrace B,C,D,E \rbrace \). Therefore,

Due to\(P_i=P_i^{1,d}\cup P_i^{2,d} \cup \ldots \cup P_i^{n,d}\),

According to Eqs.5,16 and17, Eq.15 can be deduced as follows.

\(\square \)

Appendix B Finding spliced trajectory

Lemma 4. Assuming that Algorithm 2 is processing the current pair\(\langle \textit{STR}_k^v,\textit{STR}_i^j\rangle \), the sub-trajectory\(\textit{STR}_i^j\) is a temporary end vertex, and sub-trajectories from the same trajectory before trajectory\(\textit{STR}_k^v\) constitute a temporary trajectory, if a path from\(\textit{STR}_k^v\) to\(\textit{STR}_i^j\) is found by the functionexistPath, temporary trajectories that the path have passed through can form a spliced path.

Proof

Let\(P_c\) which is found byexistPath be a path from\(\textit{STR}_k^v\) to\(\textit{STR}_i^j\). We firstly prove there must exist a path\(P_l\) from\(\textit{STR}_k^v\) to\(\textit{STR}_i^j\) in the current graphSTLC-DAG.\(P_l\) is an time-ordered sequence where each\(\textit{STR} \in \)\(\lbrace \textit{STR}_m^n| ti(\textit{STR}_k^v).st< ti(\textit{STR}_m^n).st < ti(\textit{STR}_i^j).st, m\in M(P_c) \rbrace \cup \lbrace \textit{STR}_k^v,\textit{STR}_i^j\rbrace \). And,\(M(P_c)\) is a set of\(\textit{TR}\hbox {s}\) that\(P_c\) have passed through excepti andk. We prove the problem according to the following situations.

If\(|M(P_c)|=0\) or\(|M(P_c)|=1\),\(P_c\) must be\(P_l\).

If\(|M(P_c)| \ge 2\), suppose\(P_l\) does not exist in the currentSTLC-DAG. Let\(P_a\) be the path contains the maximum number of\(\textit{STR}\hbox {s}\) from\(P_l\), where\(M(P_c) \subseteq M(P_a)\). Then, at least one vertex\(\textit{STR}_m^n\) from\(P_l\) is not on\(P_a\). According to time, let\(\textit{STR}_m^n\) be between\(P_a[i]\) and\(P_a[i+1]\), namely\(ti(P_a[i]).st< ti(\textit{STR}_m^n).st < ti(P_a[i+1]).t\), where\(P_a[i](P_a[j])\) is aith orjth\(\textit{STR}\) in\(P_a\),\(m_i(m_{i+1})\) is the subscript of\(P_a[i](P_a[i+1])\), and\(m_i,m_{i+1}\in m(P_c)\). Therefore, before running the current pair, the algorithm has executed evaluation of the two pair\(\langle P_a[i],\textit{STR}_m^n \rangle \) and\(\langle \textit{STR}_m^n,P_a[i+1] \rangle \). The evaluation generated two following results. One is that, if there does not exist a path between\(\langle P_a[i],\textit{STR}_m^n \rangle \) or\(\langle \textit{STR}_m^n,P_a[i+1] \rangle \), it shows\(TR_m\) and\(TR_{m_i}\)(\(TR_{m_{i+1}}\)) cannot be spliced. So,\(m_i \notin SP_m\) or\(m_{i+1} \notin SP_m\). According toexistPath (Algorithm 3), it cannot find that a path contains\(\textit{STR}_{m_i}(\textit{STR}_{m_{i+1}})\) and\(\textit{STR}_m\). It contradicts with\(P_c\). The other is that, if there does exist both above paths,\(\textit{STR}_m^n\) can be added into\(P_a\). It contradicts with\(P_a\) that has the maximum number of\(\textit{STR}\hbox {s}\) from\(P_l\). Therefore,\(P_l\) must exist in the currentSTLC-DAG.

Then, since\(P_l\) from\(\textit{STR}_k^v\) to\(\textit{STR}_i^j\) exists inSTLC-DAG, it implies that there must exists a path\(P_b\) from the start vertex to\(\textit{STR}_k^v\) in the currentSTLC-DAG. And,\(P_b\) contains all\(\textit{STR}\hbox {s}\) of\(\textit{TR}\hbox {s}\) between the start vertex and\(\textit{STR}_k^v\)(\(P_c\) has passed through these\(\textit{TR}s\)). This is because the algorithm has processed previous pair\(\langle \textit{STR}_t^r,\textit{STR}_k^v\rangle \). And, there must exist a path\(P_t\) similar to\(P_a\) between\(\textit{STR}_t^r\) and\(\textit{STR}_k^v\) owing to the path found byexistPath. And so on, these previous pairs form the\(P_b\). Therefore, the\(P_b\) and\(P_l\) can form a spliced path.\(\square \)

Lemma 5 If and only if a path found by algorithm3 contains sub-trajectories from two different trajectories, the two trajectories can be spliced.

Proof

If there exists a path, which is found by Algorithm 3, between any two sub-trajectories from two trajectories, respectively, according to Lemma4, the trajectories that the path passed through can be spliced with the two sub-trajectories. So, the two two sub-trajectories can be spliced. According to the definition6, if two sub-trajectories are spliceable sub-trajectories, there exists a spliced path that can pass through all sub-trajectories of the two trajectories.\(\square \)

Theorem 1

If there exists a directed edge between two trajectories, the two trajectories can be spliced.

Proof

Suppose there is an edge between\(\textit{STR}_i^j\) and\(\textit{STR}_m^n\), which the twoSTRs belong to\(\textit{TR}_i\) and\(\textit{TR}_j\), respectively, and\(\textit{TR}_i\) cannot be spliced with\(\textit{TR}_m\). According to Lemma5, at least one pair of\(\textit{STR}\hbox {s}\) from the two\(\textit{TR}\hbox {s}\), respectively, cannot be connected by a path that is found byexistPath. But, a Algorithm 2 (Line 10) must have deleted all edges between\(\textit{TR}_i\) and\(\textit{TR}_j\) if it finds that a pair between them cannot be connected by a path. Therefore, there is not an edge between them. It contradicts the assumption that there is an edge between\(\textit{STR}_i^j\) and\(\textit{STR}_m^n\).

Theorem 2

For each\(\textit{SP}_i \in \textit{SP}\), where\(\textit{SP}\) is one of output parameters of Algorithm 2,\(\textit{SP}_i\) is a set of trajectories that can be spliced with the trajectory\(\textit{TR}_i\).

Proof

At initialized phase of Algorithm 2,\(\textit{SP} = \textit{DT}\). Suppose one\(SP_i\) has a subscriptm, and its corresponding\(\textit{TR}_m\) cannot be spliced with\(\textit{TR}_i\). According to Lemma5, there is not a path between one pair\(\langle \textit{STR}_i^j,\textit{STR}_m^n \rangle \). And,\(SP_i=SP_i-m\) (Line 12 in Algorithm 2), has been executed. It contradicts with\(SP_i\) because\(SP_i\) containsm.\(\square \)

Lemma 6. InSP-set graph, a clique is a group of spliceable trajectories, a maximal clique is a complete trajectory.

Proof

A group of spliceable trajectories can be directly or indirectly spliced with each other. Therefore, there exists an edge between any two of them. So, the group of spliceable trajectories is a clique in the graph. If the clique is the maximal clique, the group of spliceable trajectories on the maximal clique cannot be contained by other groups. So, the maximal clique in the graph is a complete trajectory\(\textit{CTR}\).\(\square \)

Reprints and permissions