Topological Signatures For Fast Mobility Analysis

Abhirup Ghosh, Benedek Rozemberczki, Subramanian Ramamoorthy, and Rik Sarkar



Abstract. Trajectories of mobile agents are complex objects that are expensive to store and compare. Analytic systems for trajectory datasets are correspondingly difficult to build and costly to train. In this paper, we show that information about the topology of the space and how the trajectories navigate the obstacles can be used to efficiently extract insights about mobility. We develop topological signatures that map each trajectory to a relatively low dimensional Euclidean space, so that now they are amenable to standard analytic techniques. Data mining: nearest neighbor search with locality sensitive hashing, clustering, regression, etc., work more efficiently in this signature space. We define a question of mobility prediction at different distance scales and apply machine learning to this task. Experiments on multiple real datasets show that the framework using topological signatures is accurate on all the tasks, and substantially more efficient than machine learning applied to raw data. Theoretical results show that the signatures contain enough topological information to reconstruct non-self-intersecting trajectories upto homotopy type. The construction of signatures is based on a differential form that can be generated in a distributed setting using local communication, and a signature can be locally and inexpensively updated and communicated by a mobile agent.


Download the full paper