III: Small: Trajectory Computing

处理空间数据的需要是稳步增加的应用程序数量的先决条件。从智能手机应用程序到存储在云端数据仓库中的大型数据库，空间数据往往是关键。空间数据传统上指的是位置数据，例如GPS坐标值(即经度和纬度)。然而，位置数据不需要被限制为单一坐标。取而代之的是，位置数据可以基于许多因素，例如接近性、邻接性、连通性等。该奖项涉及与道路网络中的顶点相对应的数据点，其中数据集合代表对象的轨迹。轨迹是许多应用的核心。该奖项审查了轨迹发挥重要作用的一些应用。特别是，识别公路网中高比例司机路径上的地标。这些知识可以帮助司机设计信息，或在拼车时方便多人访问。第一个应用程序处理机动车辆轨迹，其中我们获得了一组地标和大量的个人轨迹。这里的目标是(1)确定每个人在从个人的起点和目的地出发的最短路径上通过的地标，以及(2)为每个地标确定其最短路径经过该地标或在该地标的指定距离内的所有个人。这些查询被称为路径内查询，并用于例如广告场景中，其中广告被显示给通过特定地标的那些个人，这意味着他们的源位置和目的地位置之间的最短路径包含它们。计算路网距离是计算密集的，因此经常使用欧几里得距离(如乌鸦飞翔)，但代价是大大低估了真实距离，并可能导致不可能的路径。该奖项试图采用研究人员的距离预言方法，使用道路网络中的顶点数量除以误差容差的平方的顺序，通过查表而不是搜索来获得近似的道路网络距离。第二项申请也涉及机动车辆，尽管并不局限于它们。目标是找到相似的轨迹，其中相似性是通过距离度量来衡量的。这是一个研究得很好的问题，因为它取决于所使用的相似性度量。一个常用的度量是Hausdorff距离度量。然而，Hausdorff距离的计算只考虑了轨迹的顶点，而本奖项的重点是计算Frechet距离，该距离也考虑了轨迹的边缘。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.