Mining Algorithms for Network-Constrained Trajectories

Abstract

With the advent of ubiquitous computing, a massive amount of trajectory data has been published and shared in many websites. Such computing also motivates the needs of the online mining of such data, to fit user-specific preferences or context (\eg, time of the day).While many trajectory analysis algorithms have been proposed, they typically do not consider the restrictions of the underlying road network and have focused on a spatio-temporal query. This dissertation discusses desirable properties for mining the road network trajectories. As the existing work does not fully satisfy these properties, we develop (1) trajectory representation and (2) distancemeasure that satisfy all the desirable properties we identified. Based on the representation and distance measure, we discuss how to efficiently evaluate similarity search queries which include three types of similarity semantics-- whole, subpattern, and reverse subpattern.With the distance measure that reflects the spatial proximityof the road network trajectories, we develop efficient clustering algorithms that reduce the number of distance computations during the clustering process. Moreover, we devise a clustering algorithm considering selection conditions representing user contexts to fit user-specific preferences or context (\eg, time of the day).Our experimental results demonstrate the efficiency and effectiveness of our proposed method using real-life trajectory data.