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.