1. Introduction
- Inter-trajectory studies have drawn more and more attention due to the increasing interest in understanding the social interaction among demographic groups
- A similarity measure for cellular space is different from one for Euclidean space because numerical information for cellular space is not necessarily continuous
- Therefore most of the existing algorithms, such as the time Synchronized Euclidean Distance (SED) and the Hausdorff distance, are not easily applicable
- This research focuses on measuring trajectory similarity based on a Spatio-temporal Edit Distance algorithm
- Calculates the minimum number of operations required to switch one string to another; therefore it is highly suitable for matching series of cell IDs in CDRs
- Also can deal with sequences of different lengths, a typical situation in CDRs
- Traditional Edit Distance deals with purely qualitative information such as alphabet letters. To preserve the spatial data in CDRs, they modified the cost function to incorporate the spatial distribution of cell towers
2. Background
2.1. Human mobility and trajectory similarity measures
- Larsen et al. (2006) identified five types of mobility: (1) Physical travel of people (e.g., work, leisure, family life); (2) Physical travel of objects (e.g., products to customers); (3) Imagination travel (e.g., memories, books, movies); (4) Visual travel (e.g., Internet surfing on Google Earth); and (5) Communication travel (e.g., person-to-person messages via telephones, letters, emails, etc.)
- In this research, when referring to ‘human mobility’ they focus on characterizing the Physical travel of people (trajectories) from records of Communication travel (CDRs)
- Zheng and Zhou (2011) summarized trajectory analysis and divided them into three categories:
- trajectory preprocessing (before the database level)
- trajectory indexing and retrieval (in databases)
- advanced topics (above the database level, e.g. similarity/dissimilarity analysis)
- Shape-based methods: only focus on the geometric characteristics (i.e., shape) of trajectories (e.g. Classical Euclidean Distance, Hausdorff Distance)
- Time-based methods: e.g. Synchronized Euclidean Distance, Discrete Fréchet Distance (aka the Coupling Distance), Dynamic Time Warping (DTW), and Longest Common Sub-Sequence (LCSS)
- They extended the traditional Edit Distance algorithm by incorporating the spatial distribution of cell towers and then applied the newly developed Spatio-temporal Edit Distance to compare trajectories extracted from CDRs and conduct clustering analysis
2.2. Edit Distance algorithm and its applications
- The Edit Distance algorithm measures the distance between two strings by computing the number of edit operations when transforming one string into another
- They extended the classic Edit Distance method
- It eliminates the disadvantage that every operation has equal influence (the same cost function)
- Investigate the effect of time in the modified cost function
3. Research design
3.1. Data set
- Includes the time, duration, and the location of the corresponding cell tower
3.2. Methodology
- i.e. A : XYYYYYYYYYYZ; B : XYZ; C : YYYYYYYYYY
- Since the calculation of Edit Distance is highly dependent on the number of operations, the result will indicate that distance (A, B) > distance (A, C), which is contradictory to our common sense
- If two points are located within the same mobile phone tower, and the time difference is less than ΔT (0.5 hours), the prior point is defined as a redundant point and removed
- Improves upon the classic Edit Distance by (1) eliminating redundant points and (2) incorporating the spatially enabled cost functions
4. Analysis and results
4.1. Generic analysis
4.1.1. Trajectory comparison
- The proposed method is effective in identifying the similarity of trajectory patterns in terms of identifying the range of activity space and the order of visited points
4.1.2. Clustering analysis
4.2. Extended analysis including time dimension
4.2.1. Time as a cost function parameter
4.2.2. Time as a constraint in partitioning trajectories
5. Discussion
- The extended Edit Distance method can be used to measure the similarity of mobile user trajectories from CDRs
- Adopted centroids as reference points when calculating the cost function
- a centroid can be considered as the center of an activity region
- the impact of each operation based on its spatial characteristics can be easily determined by the displacement of the centroid after each deletion/insertion/replacement operation
6. Conclusions and future work
- have developed a Spatio-temporal Edit Distance method for measuring trajectory similarity of mobile phone users
- The average distances of users follow a skewed normal distribution, which indicates that several outlier patterns of users behave differently compared to the other users in the sample set
