权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CAREER: AF: Giving Form to Data with a Geometric Scaffold

职业：AF：用几何支架赋予数据形式

基本信息

批准号：
1750780
负责人：
Benjamin Raichel
金额：
$ 49.7万
依托单位：
University of Texas at Dallas
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-09-01 至 2024-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750780&HistoricalAwards=false
关键词：
CAREER AF Giving Form Data

项目摘要

Using geometry to find structure in data is an old idea (Plato is quoted as saying, "God ever geometrizes") that gains fresh application as our data changes. Today's data sets, from areas such as machine learning, are often massive and high-dimensional: for example, when trying to classify news articles, each article may be represented as a point where the frequency of each word is a different dimension. This leads to geometries that are hard to grasp intuitively and hard to work with computationally (the "curse of dimensionality"). Finding a smaller and lower dimensional subset of the data points that approximately preserves geometric structure not only reduces computation time but also can improve results by suppressing extraneous features. Representing inter-point distances of a general space in a more structured space can support new operations, such as data visualization by mapping the 2-D plane of the screen, or more efficient computation by mapping to the hierarchical structure of a tree. This project takes the age-old practice of teasing out geometric structure and applies it to the large- and high-dimensional data sets of the modern world. By taking a geometric approach to foundational problems in areas such as big data and machine learning, this project seeks to more closely connect computational geometry and these other areas, in turn both modernizing the classical field of computational geometry and advancing these other areas. The educational goals of this project will be achieved by directly supporting student research on the outlined topics, incorporating topics into developing new courses, and organizing regular seminars in order to grow the visibility and interdisciplinary nature of algorithms and theoretical computer science at the awardee institution.Given a data set, the goal is to specify its geometric structure, use this structure to summarize and embed into simpler spaces where computations can be done efficiently, and when this is not possible, identify how to minimally fix the data to facilitate these tasks. The project's focus is on three interrelated topics concerning geometric structure that lie at the intersection of big data, geometry, and machine learning: 1) data factorization and sparsification, 2) metric embeddings for structured spaces, and 3) metric violation distance. The ultimate purpose is to develop better algorithms for handling data, ranging from better clustering algorithms to better classification algorithms. The ubiquity of such algorithms implies that any progress has the potential for significant real world impact.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.

使用几何来寻找数据中的结构是一个古老的想法（柏拉图被引用说，“上帝总是几何化”），随着我们的数据变化而获得新的应用。今天的数据集，来自机器学习等领域，通常是海量和高维的：例如，当试图对新闻文章进行分类时，每篇文章可能被表示为一个点，其中每个词的频率是不同的维度。这就导致了很难直观地把握几何形状，也很难通过计算来处理几何形状（“维数灾难”）。找到近似保留几何结构的数据点的较小且较低维度的子集不仅减少了计算时间，而且可以通过抑制无关特征来改善结果。在更结构化的空间中表示一般空间的点间距离可以支持新的操作，例如通过映射屏幕的2-D平面的数据可视化，或者通过映射到树的分层结构的更有效的计算。该项目采用了梳理几何结构的古老实践，并将其应用于现代世界的高维数据集。通过采用几何方法解决大数据和机器学习等领域的基础问题，该项目旨在将计算几何与其他领域更紧密地联系起来，从而使计算几何的经典领域现代化并推进其他领域。该项目的教育目标将通过直接支持学生对概述主题的研究来实现，将主题纳入开发新课程，并定期组织研讨会，以增加获奖机构算法和理论计算机科学的知名度和跨学科性质。给定一个数据集，目标是指定其几何结构，使用这种结构来总结和嵌入到更简单的空间中，在这些空间中可以有效地完成计算，当这是不可能的时候，确定如何最小限度地修复数据以促进这些任务。该项目的重点是关于几何结构的三个相互关联的主题，这些主题位于大数据，几何和机器学习的交叉点：1）数据因子分解和稀疏化，2）结构化空间的度量嵌入，以及3）度量违规距离。最终目的是开发更好的算法来处理数据，从更好的聚类算法到更好的分类算法。这种算法的普遍性意味着任何进展都有可能对真实的世界产生重大影响。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

项目成果

期刊论文数量（18）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Sparse convex hull coverage

DOI：
10.1016/j.comgeo.2021.101787
发表时间：
2021-05-21
期刊：
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
影响因子：
0.6
作者：
Klimenko, Georgiy;Raichel, Benjamin;Van Buskirk, Gregory
通讯作者：
Van Buskirk, Gregory

Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency

具有最小-最大延迟的多机器人巡逻调度近似算法

DOI：
10.1007/978-3-030-66723-8_7
发表时间：
2021
期刊：
International Workshop on the Algorithmic Foundations of Robotics
影响因子：
0
作者：
Afshani, Peyman;de Berg, Mark;Buchin, Kevin;Gao, Jie;Löffler, Maarten;Nayyeri, Amir;Raichel, Benjamn;Sarkar, Rik;Wang, Haotian;Yang, Hao-Tsung
通讯作者：
Yang, Hao-Tsung

Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees

查看树的年轮：最小失真嵌入树中