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

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

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.