Cluster "by part" instead of "as a whole"?

Question

A definition before I start:

A trajectory $t$ of length $n$ is here defined as a series of 2D coordinates $$\{(x_1,y_1), (x_2, y_2),..., (x_n, y_n)\}$$ Now I have a set comprised of such trajectories denoted by set $T=\{t_1, t_2,...,t_n\}$.

---

Take $t_1$ and $t_2$ as an example: let's say a segment of $t_1$ denoted by $S_{t_1}$ overlaps with a part of $t_2$ denoted by $S_{t_2}$. But for the other parts, they do not overlap.

All the trajectories may have such a "partially-overlapping" relationship with the others.

Obviously in this case, we cannot treat every trajectory as a whole, find a distance metric and finally cluster them. We have to sort of cluster the trajectories by part instead of as a whole.

Is there any already-existed clustering technique that does the job?

Any suggestions or pointers are very much welcomed.

Answer 1

The closest existing clustering technique I know of matching your description is:

[Lee et al., 2007] Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. Trajectory Clustering: A Partition-and-Group Framework. In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, pages 593–604, Beijing, China, June 2007.

From the abstract:

"Existing trajectory clustering algorithms group similar trajectories as a whole, thus discovering common trajectories. Our key observation is that clustering trajectories as a whole could miss common sub-trajectories."

I implemented this a few years ago and it works as advertised.