Browse Prior Art Database

A system and method to infer trajectories from partial observations

IP.com Disclosure Number: IPCOM000235869D
Publication Date: 2014-Mar-28
Document File: 5 page(s) / 104K

Publishing Venue

The IP.com Prior Art Database

Abstract

Majority of the trajectorie data generated at plenty these days, are collected at a low sampling rate and only provide partial observations on their actually traversed routes. Consequently, they are mired with uncertainty. A system is designed here, to infer uncertain trajectories from network-constrained partial observations. Rather than predicting the most likely route, the inferred uncertain trajectory takes the form of an edge-weighted graph and summarizes all probable routes in a holistic manner.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 30% of the total text.

Page 01 of 5

A system and method to infer trajectories from partial observations

Trajectory analytics on road networks is central to a multitude of tasks such as congestion modelling [1], community discovery [2], and urban resource management
[3]. The last decade has witnessed an unprecedented growth in the availability of location-tracking technologies, which can be deployed at large scales to collect trajectory data. However, these trajectories are often recorded at a low sampling rate wherein the time interval between two consecutive recorded locations is large. As a result, these trajectories only provide partial observations of the actual traversed route and the intermediate portions remain hidden.

Disclosed is a device (system, circuit, etc.) for inferring road-constrained trajectories from partial observations based on an underlying dynamic network mobility model, learnt using a set of historical trajectories. The system integrates many rich features like, time of traversal, previous nodes visited in the journey etc. to enhance the inference quality.

The last decade has witnessed an unprecedented growth in the availability of devices equipped with location-tracking sensors. Examples of such devices include cellphones, in-car navigation systems, etc. The wide-spread usage of these devices has resulted in an abundance of data that are in the form of trajectories. Querying and mining these trajectories is critical to extract the knowledge hidden in the raw datasets and to design intelligent spatio-temporal data management systems.

Unfortunately, majority of these location tracking devices only provide partial observations on the actual trajectories. For example, cell phones, a ubiquitous device, is used to estimate the locations of their users based on the base stations through which calls or data usages are routed through. As a cellphone user moves, the routing base stations change and thus recording a series of observations on the trajectory. Additionally, such location tracking is possible only when the cellphone (or a 3G/4G dongle) is in use. Rest of the time no information is recorded. Similar situations arise also while tracking movements of a vehicle through snapshots generated from cameras installed at signals, and from credit card transactions.

    Prior art [4,5,6,7] includes map-matching techniques which provide the maximum likelihood path from a series of observations. A maximum likelihood path does not capture the uncertainty around the prediction. Moreover, existing techniques completely ignore historical trajectory information which characterises location and time-specific mobility patterns in a region.

The core ideas are described as follows:

1. In an offline computation, build a dynamic network mobility model (DNMM) to characterise movement of vehicles in a road network. The DNMM takes two inputs: a road network and historical trajectory information. Based on these

1


Page 02 of 5

inputs, it generates a model to predict the pro...