Common Sub-Trajectory Clustering via Hypercubes in Spatiotemporal Space

Abstract

Conventional sub-trajectory clustering is used to identify similarities among multiple trajectories. Existing methods tend to overlook many of the relevant sub-trajectories; others require a road network as input; all are significantly slowed down considerably by large datasets. In this paper, we propose a novel approach to clustering sub-trajectory in which trajectories are transformed into a set of Hypercubes. The Hypercubes are pairwise-matched to find an intersection and then clustered accordingly. The performance of the proposed scheme was compared with that of grid clustering (i.e., constant time technique) in terms of memory usage, computational speed, and compared with a state-of-art method, TraClus, by assessing their accuracy. The experiment results show that Hypercube clustering can identify common sub-trajectories more swiftly and with less memory usage than grid clustering. The accuracy of Hypercube clustering is superior to TraClus.

Keywords

• Urban computing
• similar trajectories
• ridesharing paths
• common sub-trajectories clustering