Topological signatures for fast mobility analysis

Abhirup Ghosh, Benedek Rózemberczki, Subramanian Ramamoorthy, Rik Sarkar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Analytic methods can be difficult to build and costly to train for mobility data. We show that information about the topology of the space and how mobile objects navigate the obstacles can be used to extract
insights about mobility at larger distance scales. The main contribution of this paper is a topological signature that maps each trajectory to a relatively low dimensional Euclidean space, so that now they are amenable to standard analytic techniques. Data mining tasks: nearest neighbor search with locality sensitive hashing, clustering, regression, etc., work more efficiently in this signature space. We define the problem of mobility prediction at different distance scales, and show that with the signatures simple k nearest neighbor based regression perform accurate prediction. Experiments on multiple real datasets show that the framework using topological signatures is accurate on all 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.
Original languageEnglish
Title of host publicationProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
Place of PublicationSeattle, Washington
PublisherACM
Pages159-168
Number of pages10
ISBN (Electronic)978-1-4503-5889-7
DOIs
Publication statusPublished - 6 Nov 2018
Event26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2018) - Seattle, United States
Duration: 6 Nov 20189 Nov 2018
https://sigspatial2018.sigspatial.org/

Conference

Conference26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2018)
Abbreviated titleACM SIGSPATIAL 2018
CountryUnited States
CitySeattle
Period6/11/189/11/18
Internet address

Fingerprint Dive into the research topics of 'Topological signatures for fast mobility analysis'. Together they form a unique fingerprint.

Cite this