NSF-BSF:AF:Small:Algorithmic Tools for Proximity Problems among Curves

近年来，已经获得了大量的路径和轨迹数据。这些数据来自各种各样的来源，如演员的动作捕捉、鸟类的飞行路线、公共汽车路线、出租车旅行、体育分析、牛身上的GPS传感器和股票表现记录。最近的技术进步，例如具有gps功能的移动电话的普及，使得这些数据源无处不在。这带来了一些挑战，例如存储数据、识别和删除冗余、对数据进行集群化以及对数据进行预处理，以促进各种常见和有用的查询。因此，世界正在见证围绕路径和轨迹数据的研究的爆发。其中大部分都是实验性的，很少关注用于处理海量信息的各种启发式方法在时间、存储和质量方面的保证性能。在这个项目中，研究人员团队正在设计有效的算法和数据结构，具有可证明的性能保证，用于处理路径和轨迹数据的基本问题。他们将注意力集中在接近性问题上，包括最近邻搜索、聚类和相关问题。然而，与之前的许多相关研究相比，该团队打算通过考虑现实生活中经常发现的属性，特别强调所获得结果的有用性。他们也在考虑流模型中的这些问题，流模型通常适合实际情况。（在这个模型中，我们假设总的信息量非常大，数据以频繁的小更新的形式到达，并且用于处理每次更新的可用时间和内存有限。）该团队正在开发新方法，并将其与现有方法相结合，以解决在各种环境下处理大量曲线和轨迹数据时遇到的具有挑战性的算法问题。该方法旨在适用于计算几何及其他领域的其他问题。研究人员正在设计适用于与学术界、工业界和社会相关的现实问题的算法。此外，路径和轨迹数据的接近性问题特别适合向高中生和大学生介绍算法的世界，因为理解问题本身所需的背景很小，并且可以通过易于访问的插图呈现各种复杂程度的好想法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

In recent years, a vast volume of path and trajectory data has become available. The data comes from a variety of sources, as different as motion capture of actors, flight paths of birds, bus routes, taxi trips, sports analysis, GPS sensors on cattle, and stock-performance recordings. Recent advancements of technology, such as the proliferation of GPS-enabled mobile phones, makes such data sources ubiquitous. This gives rise to several challenges, such as storing the data, identifying and removing redundancies, clustering it, and preprocessing it to facilitate a variety of common and useful queries.Consequently, the world is witnessing an outburst of research surrounding path and trajectory data. Much of it is experimental, with little focus on the guaranteed performance, in terms of time, storage, and quality, of the various heuristics used for processing the sea of information. In this project, the team of researchers is designing effective algorithms and data structures with provable performance guarantees for fundamental problems dealing with path and trajectory data. They are concentrating their attention on proximity problems, including nearest-neighbor searching, clustering, and related questions. However, in contrast with much of the previous related research, the team intends to put special emphasis on the usefulness of the obtained results, by taking into account properties that are often found in real-life inputs. They are also considering these problems in the streaming model, which often suits the circumstances in practice. (In this model one assumes that the overall volume of information is overwhelmingly large, that the data arrives in small frequent updates, and that limited amounts of time and memory are available to handle each update.) The team is developing new methods and combine them with existing ones to attack challenging algorithmic questions in processing of massive amounts of curve and trajectory data in various settings. The methodology is intended to be applicable to other problems in computational geometry and beyond. The researchers are designing algorithms that are applicable to real-life problems of relevance to the academia, industry, and society. Moreover, proximity problems for path and trajectory data are especially suitable for introducing high-school and university students to the world of algorithms, as the background needed for understanding the problems themselves is minimal and nice ideas at various levels of sophistication can be presented through easily accessible illustrations.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.