Conference Proceeding Article
Existing algorithms for trajectory-based clustering usually rely on simplex representation and a single proximity-related distance (or similarity) measure. Consequently, additional information markers (e.g., social interactions or the semantics of the spatial layout) are usually ignored, leading to the inability to fully discover the communities in the trajectory database. This is especially true for human-generated trajectories, where additional fine-grained markers (e.g., movement velocity at certain locations, or the sequence of semantic spaces visited) can help capture latent relationships between cluster members. To address this limitation, we propose TODMIS: a general framework for Trajectory cOmmunity Discovery using Multiple Information Sources. TODMIS combines additional information with raw trajectory data and creates multiple similarity metrics. In our proposed approach, we first develop a novel approach for computing semantic level similarity by constructing a Markov Random Walk model from the semantically-labeled trajectory data, and then measuring similarity at the distribution level. In addition, we also extract and compute pair-wise similarity measures related to three additional markers, namely trajectory level spatial alignment (proximity), temporal patterns and multi-scale velocity statistics. Finally, after creating a single similarity metric from the weighted combination of these multiple measures, we apply dense sub-graph detection to discover the set of distinct communities. We evaluated TODMIS extensively using traces of (i) student movement data in a campus, (ii) customer trajectories in a shopping mall, and (iii) city-scale taxi movement data. Experimental results demonstrate that TODMIS correctly and efficiently discovers the real grouping behaviors in these diverse settings.
Trajectory community discovery, multiple information, semantic information
CIKM '13: Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, 27 October - 1 November 2013, San Francisco
City or Country
San Francisco, CA
LIU, Siyuan; WANG, Shuhui; Jayarajah, Kasthuri; MISRA, Archan; and Krishnan, Rammaya.
TODMIS: Mining Communities from Trajectories. (2013). CIKM '13: Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, 27 October - 1 November 2013, San Francisco. 2109-2118. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1958
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.