Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

10-2013

Abstract

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.

Keywords

Trajectory community discovery, multiple information, semantic information

Discipline

Software Engineering | Theory and Algorithms

Research Areas

Software and Cyber-Physical Systems

Publication

CIKM '13: Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, 27 October - 1 November 2013, San Francisco

First Page

2109

Last Page

2118

ISBN

9781450322638

Identifier

10.1145/2505515.2505552

Publisher

ACM

City or Country

New York

Copyright Owner and License

Publisher

Additional URL

https://doi.org/10.1145/2505515.2505552

Download

Share

COinS