CAREER: Algorithmic Challenges and Opportunities in Spatial Data Analysis

职业：空间数据分析中的算法挑战和机遇

基本信息

批准号：
2017980
负责人：
Donald Sheehy
金额：
$ 27.75万
依托单位：
North Carolina State University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-08-23 至 2023-01-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2017980&HistoricalAwards=false
关键词：
CAREER Algorithmic Challenges Opportunities Spatial

项目摘要

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.

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

项目成果

期刊论文数量（12）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

The Sum of Squares in Polycubes

多立方体的平方和

DOI：
发表时间：
2023-01
期刊：
International Symposium on Computational Geometry (SoCG 2023
影响因子：
0
作者：
Sheehy; Donald R.
通讯作者：
Donald R.

Efficient Algorithm for the Topological Characterization of Worm-like and Branched Micelle Structures from Simulations

通过模拟对蠕虫状和支化胶束结构进行拓扑表征的有效算法

DOI：
10.1021/acs.jctc.0c00311
发表时间：
2020-07
期刊：
Journal of Chemical Theory and Computation
影响因子：
5.5
作者：
Conchuir, Breanndan O.;Gardner, Kirk;Jordan, Kirk E.;Bray, David J.;Anderson, Richard L.;Johnston, Michael A.;Swope, William C.;Harrison, Ale;Sheehy, Donald R.;Peters, Thomas J.
通讯作者：
Peters, Thomas J.

Maximum Subbarcode Matching and Subbarcode Distance

最大子条码匹配和子条码距离