CAREER: Algorithmic Challenges and Opportunities in Spatial Data Analysis

空间数据有多种形式，包括机器人或蛋白质的配置空间，形状或测量的集合，以及新传感技术的物理模型和测量。这些数据集通常包含内在的，非线性的，低维的结构隐藏在复杂的高维输入表示。 为了揭示这种结构，需要适应局部尺度变化，识别多尺度结构，表示数据的内在空间，计算粗略的近似距离，并将异构数据集成到有意义的距离函数中。需要能够有效地搜索、表示和汇总这些数据集的算法和数据结构。 PI将开发新的数据结构，计算模型，采样理论，采样算法和度量来应对这些挑战。 该项目的具体目标是采用仅使用近似距离比较的新计算模型来调整分层度量数据结构，以适应局部自适应距离。 这些模型承认了这样一个现实，即对于足够复杂的数据，即使是单个距离计算也可能是昂贵的。 第二个具体目标是开发新的多尺度采样理论以及计算此类样本的新算法。 这些样本和采样算法将适用于广泛的问题，并将扩展和推广贪婪和最远点策略。 第三个具体目标是为异构数据开发新的度量和距离函数的算法，以更准确地表示数据的内在结构。 这些算法将推广用于Voronoi细分网格生成和拓扑数据分析的方法。 该项目将使几何方法适用于更广泛的问题，并与需要更广泛的理解先进的几何和拓扑。 PI将整合研究和教育，向本科和研究生级别的计算机科学学生介绍空间数据分析的基本思想，从几何到拓扑。 PI还将一对一地指导传统上代表性不足的群体的本科生，并帮助培训高中教师。

Spatial data takes many forms including configuration spaces of robots or proteins, collections of shapes or measures, and physical models and measurements from new sensing technologies. These data sets often contain intrinsic, nonlinear, low-dimensional structure hidden in complex high-dimensional input representations. To uncover such structure one needs to adapt to local changes in scale, recognize multiscale structure, represent the intrinsic space underlying the data, compute with coarse approximate distances, and integrate heterogeneous data into meaningful distance functions. There is a need for algorithms and data structures that can search, represent, and summarize such data sets efficiently. The PI will develop new data structures, models of computation, sampling theories, sampling algorithms, and metrics for addressing these challenges. The specific aim of the project is to adapt hierarchical metric data structures to work with locally adaptive distances using new models of computation that only use approximate distance comparisons. These models acknowledge the reality that with sufficiently complex data, even a single distance computation can be expensive. A second specific aim is to develop new multiscale sampling theories as well as new algorithms for computing such samples. These samples and sampling algorithms will be applicable to a wide range of problems and will extend and generalize greedy and farthest-point strategies. A third specific aim is to develop algorithms for new metrics and distance functions for heterogeneous data to more accurately represent intrinsic structure in data. These algorithms will generalize methods used in both Voronoi refinement mesh generation and topological data analysis. The project will make geometric methods applicable to a much wider range of problems and with that comes the need for wider understanding of advanced geometry and topology. The PI will integrate research and education, introducing computer science students at both the undergraduate and graduate level to foundational ideas in spatial data analysis, from geometry to topology. The PI will also work one-on-one to mentor undergraduates from traditionally underrepresented groups and help train high school teachers.