III: Small: Trajectory Computing

点击翻译按钮获取中文摘要

The need to deal with spatial data is a pre-requisite to a steadily increasing number of applications. From smartphone apps to large databases stored in data warehouses on the cloud, spatial data is often key. Spatial data has traditionally meant location data such as GPS coordinate values (i.e., longitude and latitude). However, location data need not be restricted to be single coordinates. Instead, location data may be based on numerous factors such as proximity, adjacency, connectivity, etc. This award deals with data points that correspond to vertices in a road network, where the collection of data represents the object's trajectory. Trajectories lie at the heart of many applications. This award examines a number of applications where trajectories play an important role. In particular, identifying landmarks that are in the paths of a high percentage of drivers in the road network. This knowledge can help the design of information for drivers or ease access for multiple people in ride sharing.The first application deals with motor vehicle trajectories where we are given a set of landmarks and a large number of individual trajectories. The objective here is (1) to determine the landmarks through which each individual travels on the shortest path from an individual's starting and destination locations, and (2) to determine for each landmark all the individuals whose shortest paths pass through that landmark or within a specified distance of that landmark. These queries are termed in-path queries and find use in, for example, advertising scenarios where ads are displayed to those individuals who pass through particular landmarks which means that the shortest path between their source and destination locations contains them. Computing road network distance is computationally intensive and hence the Euclidean distance ("as the crow flies") is often used but at the price of greatly under-estimating the true distance and possibly leading to impossible paths. This award attempts to adopt the investigator's distance oracle methods which enable approximate road network distance to be obtained using order of the number of vertices in the road network divided by the square of the error tolerance and by table lookup instead of search. The second application also deals with motor vehicles, although is not limited to them. The goal is to find similar trajectories where similarity is measured by a distance metric. This is a well-studied problem in that it depends on the similarity metric that is used. One commonly used metric is the Hausdorff distance metric. However, the computation of the Hausdorff distance only takes into account the vertices of the trajectory while this award focuses on the computation of the Frechet distance which also takes into account the edges of the trajectory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.