Stable Trajectory Clustering: An Efficient Split and Merge Algorithm
Atieh Rahmani, Mansoor Davoodi, Justin M. Calabrese · 2025
Read Stable Trajectory Clustering: An Efficient Split and Merge Algorithm by Atieh Rahmani, Mansoor Davoodi, Justin M. Calabrese (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-21808.txt.
Introduction
Atieh Rahmani, Mansoor Davoodi, and Justin Calabrese present stable trajectory clustering in work from 2025. Clustering paths of people, animals, or vehicles helps reveal movement patterns across many fields.
Their methods build on density clustering of line segments, with split and merge events that capture movement history. Whole-path and sub-path versions use a sliding window for local patterns. Many rival methods split paths over brief glitches, which hides steady patterns. Their stable version selectively ignores short deviations, keeping clusters intact. Tests on real path datasets show the approach works and responds sensibly to settings.
Catalog record
| CREATOR | Atieh Rahmani, Mansoor Davoodi, Justin M. Calabrese |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-21808
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stable Trajectory Clustering: An Efficient Split and Merge Algorithm Atieh Rahmani, Mansoor Davoodi, Justin M. Calabrese Abstract Clustering algorithms group data points by characteristics to identify patterns. Over the past two decades, researchers have extended these methods to analyze trajectories of humans, animals, and vehicles, studying their behavior and movement across applications. This paper presents whole-trajectory clustering and sub-trajectory clustering algorithms based on DBSCAN line segment clustering, which encompasses two key events: split and merge of line segments. The events are employed by object movement history and the average Euclidean distance between line segments. In this framework, whole-trajectory clustering considers entire entities’ trajectories, whereas sub-trajectory clustering employs a sliding window model to identify similar sub-trajectories. Many existing trajectory clustering algorithms respond to temporary anomalies in data by splitting trajectories, which often obscures otherwise consistent clustering patterns and leads to less reliable insights. We introduce the stable trajectory clustering algorithm, which leverages the mean absolute deviation concept to demonstrate that selective omission of transient deviations not only preserves the integrity of clusters but also improves their stability and interpretability. We run all proposed algorithms on real trajectory datasets to illustrate their effectiveness and sensitivity to parameter variations. I Introduction Trajectory clustering is one of the most important data analysis methods developed for analyzing moving objects like humans, animals, and vehicles in various fields and applications. It can be used to identify common behaviors and recognize similar movement patterns, as well as to detect irregular or anomalous movements in different types of trajectory data. Among the use cases of trajectory clustering, we can mention exploring urban travel patterns that reflect the regularity of mobility patterns, which is an important factor in evaluating the optimality of city spatial structure and road network connectivity [ 1 ] , classifying animal behaviors (foraging, resting, walking) using high-frequency tracking data to study their environmental interactions [ 2 ] and clustering animals by species based on their daily movement patterns, which is complicated by the erratic nature of these movements [ 3 ] . Trajectory clustering is also used in air traffic categorization [ 4 , 5 ] , traffic network identification [ 6 ] and, weather prediction [ 7 ] . Anomalies frequently occur in trajectory clustering due to irregularities or deviations in movement patterns. To address this, numerous algorithms have been developed, each designed to effectively detect and analyze these anomalies [ 8 , 9 ] . Missing, however, is an algorithm that can filter out and ignore insignificant anomalies in trajectories to reveal clustering patterns that are otherwise stable. Researchers have focused in recent years on stable algorithms for clustering data points that select the optimal number of clusters [ 10 ] . Said another way, current stable clustering algorithms try to split and merge data points correctly in a way that is robust against random oscillations. Inspired by these developments for point clustering, we propose a stable algorithm for clustering trajectories based on the results of line segment clustering in each time interval. For line segment clustering in a time interval, we use the results from the previous time interval, which reflect the states of moving objects and their changes caused by split and merge events in each time interval. We also present an innovative approach that detects which trajectories can be assigned to their respective cluster despite anomalies, which is a prominent issue in real trajectory data that previous algorithms have not addressed. Building upon existing trajectory clustering algorithms, we propose algorithms for both whole-trajectory clustering and sub-trajectory clustering. A trajectory can be described as a piecewise linear function, where each segment represents an object’s movement in a specific time interval. Consequently, for trajectory clustering, a set of line segments exists for each time interval, and these sets need to be clustered. For this purpose, Density-Based Spatial Clustering of Applications with Noise (DBSCAN) line segment clustering defines the split and merge procedures of line segments. One key advantage of this approach is that the results from clustering in each time interval can be reused in the subsequent interval, as line segments often retain their previous cluster assignment. In this context, we use the continuous average Euclidean distance to measure the distance between segments. As a result, a data analyst can identify the behaviors of moving objects across all time intervals, determining which objects move together and belong to the same cluster in each interval. The sub-trajectory clustering algorithm focuses on specific time intervals to identify similar sub-trajectories. We employ a sliding window model that utilizes two parameters to recognize temporal patterns and similar sub-sequences. We then present an innovative definition and algorithm for the stable trajectory clustering algorithm, which is a first-of-its-kind advancement. This approach deals with insignificant anomalies and deviations in object movements that obscure broader clustering patterns and can thus be ignored when the goal is quantifying persistent trajectory clusters. It is often important to filter out anomalies in data where imprecision is small relative to the scale of the movement. For instance, in urban traffic analysis, a vehicle making a brief stop at a traffic light or a pedestrian crossing should still be classified within the main traffic cluster. Furthermore, a person briefly deviating from a common trajectory to look at a shop window should not be marked as an outlier in pedestrian movement studies. A related example can be seen in animal movement studies, where a migrating bird or herd of animals temporarily deviates from its migration trajectory to find food or rest, but then returns to their original trajectory afterward. In this algorithm, we employ the mean absolute deviation concept to assess how much each outlier trajectory deviates from its assigned cluster, enabling us to distinguish significant outliers from temporary anomalies. Finally, we apply all algorithms and concepts to two real trajectory datasets and demonstrate the parameter sensitivity and effectiveness of the stable trajectory clustering algorithm based on its impact on data, specifically on how the number of clusters changes after the algorithm is executed. In summary, our contributions are illustrated as a graphical abstract in Fig. 1 . The remainder of this paper is organized as follows: Section 2 covers the concepts and related algorithms for data point clustering, sub-trajectory clustering, whole-trajectory clustering, and stable data point clustering. Section 3 covers the foundational concepts and background information necessary for understanding our work, and then formally defines the problems to be solved. Section 4 addresses how whole-trajectories and sub-trajectories are clustered using the split and merge approaches. Section 5 introduces the principles and definitions of the stable trajectory clustering algorithm. Section 6 evaluates the algorithms and discusses their efficiency. Finally, Section 7 concludes the paper with remarks and directions for future work. Fig. 1 : Graphical abstract of the proposed approaches. II Related Work In the last two decades, many data point clustering algorithms have been discussed in various fields and applications such as wireless sensor networks [ 11 ] , flight anomaly detection [ 12 ] , and image processing [ 13 ] . These algorithms try to group similar data points based on their similarities or dissimilarities [ 14 ] . There are several types of methods to cluster data points, such as partitioning methods