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.