CRII: AF: Breaking Barriers for Geometric Data

令人惊讶的是，几何抽象经常帮助我们理解大系统：分子变成球和棒，复杂的流体或燃烧模拟显示为等高线或等面线，电影变成高维空间中的点，以便根据最喜欢的电影附近的其他点进行推荐。计算几何为用几何术语表述的问题开发了有效的计算机算法，因此可以在数据分析中发挥核心作用。传统上，计算几何的重点是在所有可能的输入上保证性能的精确算法，包括最坏情况的输入。本项目认识到许多实际数据分析任务不会产生最坏情况，并试图确定给定问题的结构方面，这些问题允许现有或新算法具有比实际情况的最坏情况边界更好的保证，通常使用近似、概率分析、参数化复杂性或输出灵敏度。理解在超级计算机上运行的燃烧模拟的大量数据提供了一个3d示例：轮廓树，一种用于总结模拟中密度或温度等面的相互作用的数据结构，在最坏的情况下需要超过线性时间来计算，但通过参数化树的形状可以表明，平衡的树可以在线性时间内计算。机器学习和聚类问题，比如推荐系统，给出了高维的例子，在这些例子中，人们希望提取一个更小、更低维的输入表示，同时保留一些感兴趣的特征。这个问题的几何形式被称为提取核心集；在最坏的情况下，核心集的大小在维度上可能是指数级的。然而，在实际输入中，往往存在隐藏的低维结构；与其设计一个运行时间取决于最坏情况核心集大小的算法，不如让运行时间适应给定实例所需的大小。先进的非最坏情况分析技术有助于弥合理论与实践之间的差距，因为最坏情况分析预测的运行时间与实际数据集的运行时间之间经常存在脱节。研究者将把非最坏情况分析技术纳入他的课程课程，因为这些技术是必不可少的，但在标准算法课程中严重缺乏。这个项目也将用于支持研究生和本科生对这个主题的研究。

It is surprising how often geometric abstractions help us deal with understanding large systems: molecules become balls and sticks, complex fluid or combustion simulations are shown as contours or isosurfaces, and movies become points in a high dimensional space to allow recommendations based on which other points are near one's favorite movies. Computational Geometry, which develops efficient computer algorithms for problems stated in geometric terms, can thus play a central role in data analytics. Traditionally, the focus in Computational Geometry was on exact algorithms with guaranteed performance on all possible inputs, including worst-case inputs. This project recognizes that many practical data analysis tasks do not generate worst-case instances, and seeks to identify structural aspects of given problems that allow existing or new algorithms with better guarantees than the worst-case bounds for realistic cases, often using approximation, probabilistic analysis, parameterized complexity, or output sensitivity.Understanding the huge volume of data from a combustion simulation run on a super computer gives a 3d example: Contour trees, a data structure used to summarize interactions between density or temperature isosurfaces in a simulation, take more than linear time to compute in the worst case, but by parameterizing on tree shape one can show that trees that are balanced can be computed in linear time. Machine learning and clustering problems, like recommendation systems, give higher-dimensional examples in which one desires to extract a smaller and lower dimensional representation of the input, while preserving some feature of interest. A geometric form of this problem is known as extracting a coreset; in the worst case the coreset size can be exponential in the dimension. On real inputs however, there is often hidden low dimensional structure; rather than designing an algorithm whose running time depends on the worst case coreset size, the running time should adapt to the size required by the given instance.Advancing non-worst-case analysis techniques helps bridge the gap between theory and practice, as there is often a disconnect between running times predicted by worst-case analysis and those seen on real data sets. The investigator will incorporate non-worst-case analysis techniques into his course curricula, as such techniques are essential yet severely lacking in standard algorithms courses. This project will also be used to support student research at the graduate as well as undergraduate levels on this topic.