Currently, the exponential growth of trajectory data, fueled by location-based services like ride-hailing and food delivery, demands greater efficiency in clustering methods. However, many existing trajectory clustering methods often prioritize accuracy at the expense of efficiency, resulting in inefficient clustering for massive trajectory datasets. The primary reasons for this inefficiency are: (1) the high computational cost of calculating pairwise distances between numerous trajectory points, and (2) unnecessary exhaustive similarity computations between trajectories that do not belong to the same cluster.
To solve the problems, a research team led by Ziqiang YU published their new research on large-scale, training-free trajectory clustering in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
The research team has developed an innovative Locality-Sensitive Hashing (LSH)-based Trajectory Clustering (LTC) algorithm that significantly improves upon existing trajectory clustering methods. The proposed LTC framework employs a grid-based spatiotemporal encoding mechanism and leverages LSH techniques from set similarity computation. This novel approach effectively reduces trajectory representation dimensionality while achieving highly efficient and accurate clustering without exhaustive pairwise comparisons, dramatically lowering computational complexity from from O(n2) to O(n), where n is the number of trajectories.
LTC divides the entire region that covers all trajectories into a grid of equal-sized cells, representing each trajectory as a sequence of cells it traverses. This way, similar trajectories exhibit high spatial similarity by sharing common cells and high temporal similarity by traversing those cells in a consistent sequential order. Leveraging this observation, LTC employs Location-Sensitive Hashing (LSH) to cluster trajectories in spatial and temporal dimensions.
The LTC algorithm uses LSH for spatial clustering by analyzing shared grid cells in trajectories. However, standard LSH only detects cell overlaps, missing temporal patterns. To address this limitation, the research team innovatively proposes an Order-Sensitive Encoding (OS-Encoding) mechanism that recalculates identifiers for shared cells within spatially grouped trajectories. The OS-Encoding mechanism ensures shared cells receive identical identifiers when maintaining consistent relative ordering across trajectories (even with differing absolute positions). This encoding method enables LSH-based clustering to effectively incorporate temporal similarity between trajectories.
DOI:10.1007/s11704-025-50766-6