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

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.