AF: Large: Collaborative Research: Compact Representations and Efficient Algorithms for Distributed Geometric Data

AF:大型:协作研究:分布式几何数据的紧凑表示和高效算法

基本信息

  • 批准号:
    1012042
  • 负责人:
  • 金额:
    $ 43.3万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2010
  • 资助国家:
    美国
  • 起止时间:
    2010-09-01 至 2014-08-31
  • 项目状态:
    已结题

项目摘要

Across many fields of science, engineering, and business, massive data sets are being generated at unprecedented rate by high-bandwidth sensors and cameras, large-scale simulations, or web-enabled large scale data collection. Much of this data has a geometric character, either directly or indirectly. For example, second generation LiDARs can map the earth's surface at 15-20 cm resolution; the Large Synoptic Telescope is set to produce about 30 terabytes of data each night; thirteen hours of video are uploaded to YouTube every minute; Facebook manages over 40 billion photos requiring more than one petabyte of data.These data sets provide tremendous opportunities to enable novel capabilities that were unimaginable a few years ago. Capitalizing on these opportunities, however, and transforming these massive amounts of heterogeneous data into useful information for vastly different types of applications and users requires solving challenging algorithmic problems. An effective way of addressing this challenge is by designing efficient methods for producing informative yet succinct summaries of such geometric data sets. These summaries must work at multiple scales, and allow a wide variety of queries to be answered approximately but efficiently. The goal of this project is to study the theoretical underpinnings of compact representations and efficient algorithms for organizing, summarizing, cross-correlating, interlinking, and querying large distributed geometric data sets.This project will design methods for computing summaries of many kinds of flavors, all with provable properties. Summaries can be combinatorial and metric (core sets and kernels), algebraic (linear sketches), topological (persistence diagrams), feature-based, and structural (encoding self-similarities in the data). The properties they aim to capture extend from low-level metric attributes, such as the diameter or width of a point set, to higher-level attributes revealing the internal structure of the data, as in the detection of symmetries and repeated patterns. This processing must be done in the presence of uncertainty in data coming from sensors, and optimize multiple performance measures, including communication cost for data distributed across multiple locations in a network. Another key aspect of this project is that it aims to understand not individual data sets in isolation but rather the inter-relationships and correspondences among different data sets, and to do so by communicating only summary information, without even having all the data in one place. This work touches upon many topics in theoretical computer science and applied mathematics including low-distortion embeddings, compressive sensing, transportation metrics, spectral graph theory or harmonic analysis, machine learning, and computational topology.
在科学、工程和商业的许多领域,高带宽传感器和摄像头、大规模模拟或基于Web的大规模数据收集正在以前所未有的速度生成海量数据集。这些数据中有很大一部分直接或间接地具有几何特征。例如,第二代激光雷达可以15-20厘米的分辨率绘制地球表面的地图;大型天气望远镜每晚将产生约30 TB的数据;每分钟13个小时的视频被上传到YouTube;Facebook管理着400多亿张照片,需要超过1PB的数据。这些数据集提供了巨大的机会,使新的能力在几年前是无法想象的。然而,要利用这些机会,并将这些海量的异类数据转换为适用于非常不同类型的应用程序和用户的有用信息,需要解决具有挑战性的算法问题。解决这一挑战的一个有效方法是设计有效的方法来产生这样的几何数据集的信息丰富而简洁的摘要。这些摘要必须在多个范围内工作,并允许以近似但高效的方式回答各种问题。这个项目的目标是研究紧凑表示和高效算法的理论基础,用于组织、汇总、交叉关联、链接和查询大型分布式几何数据集。该项目将设计各种类型的摘要的计算方法,所有这些都具有可证明的性质。摘要可以是组合和度量(核心集和内核)、代数(线性示意图)、拓扑(持久性图)、基于特征和结构(编码数据中的自相似性)。它们旨在捕获的属性从低级度量属性(如点集的直径或宽度)扩展到揭示数据内部结构的高级属性,如对称性和重复模式的检测。这种处理必须在来自传感器的数据存在不确定性的情况下进行,并优化多个性能指标,包括分布在网络中多个位置的数据的通信成本。该项目的另一个关键方面是,它的目标不是孤立地了解单个数据集,而是了解不同数据集之间的相互关系和对应关系,并通过只传达摘要信息来做到这一点,而不是甚至将所有数据集中在一个地方。这项工作涉及理论计算机科学和应用数学的许多主题,包括低失真嵌入、压缩传感、传输度量、谱图理论或调和分析、机器学习和计算拓扑学。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Piotr Indyk其他文献

Differentially Private Approximate Near Neighbor Counting in High Dimensions
高维差分隐私近似近邻计数
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Alexandr Andoni;Piotr Indyk;S. Mahabadi;Shyam Narayanan
  • 通讯作者:
    Shyam Narayanan
Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
三元组、终端对比嵌入的尺寸精度权衡
  • DOI:
    10.48550/arxiv.2312.13490
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Vaggos Chatziafratis;Piotr Indyk
  • 通讯作者:
    Piotr Indyk

Piotr Indyk的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Piotr Indyk', 18)}}的其他基金

Travel: SODA 2024 Conference Student and Postdoc Travel Support
旅行:SODA 2024 会议学生和博士后旅行支持
  • 批准号:
    2343779
  • 财政年份:
    2023
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Standard Grant
Conference: SODA 2023 Conference Student and Postdoc Travel Support
会议:SODA 2023 会议学生和博士后旅行支持
  • 批准号:
    2232958
  • 财政年份:
    2022
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Standard Grant
Foundations of Data Science Institute
数据科学研究所基础
  • 批准号:
    2022448
  • 财政年份:
    2020
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Small: Fine-Grained Complexity of Approximate Problems
协作研究:AF:小:近似问题的细粒度复杂性
  • 批准号:
    2006798
  • 财政年份:
    2020
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Standard Grant
TRIPODS: Institute for Foundations of Data Science (IFDS)
TRIPODS:数据科学研究所 (IFDS)
  • 批准号:
    1740751
  • 财政年份:
    2017
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
AitF: FULL: Sparse Fourier Transform: From Theory to Practice
AitF:FULL:稀疏傅里叶变换:从理论到实践
  • 批准号:
    1535851
  • 财政年份:
    2015
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Standard Grant
BIGDATA: F: DKA: Collaborative Research: Structured Nearest Neighbor Search in High Dimensions
BIGDATA:F:DKA:协作研究:高维结构化最近邻搜索
  • 批准号:
    1447476
  • 财政年份:
    2015
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Standard Grant
Fast Approximate Algorithms for Wireless Sensor Networks
无线传感器网络的快速近似算法
  • 批准号:
    0728645
  • 财政年份:
    2007
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Standard Grant
CAREER: Approximate Algorithms for High-dimensional Geometric Problems
职业:高维几何问题的近似算法
  • 批准号:
    0133849
  • 财政年份:
    2002
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant

相似国自然基金

水稻穗粒数调控关键因子LARGE6的分子遗传网络解析
  • 批准号:
  • 批准年份:
    2022
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
量子自旋液体中拓扑拟粒子的性质:量子蒙特卡罗和新的large-N理论
  • 批准号:
  • 批准年份:
    2020
  • 资助金额:
    62 万元
  • 项目类别:
    面上项目
甘蓝型油菜Large Grain基因调控粒重的分子机制研究
  • 批准号:
    31972875
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
Large PB/PB小鼠 视网膜新生血管模型的研究
  • 批准号:
    30971650
  • 批准年份:
    2009
  • 资助金额:
    8.0 万元
  • 项目类别:
    面上项目
基因discs large在果蝇卵母细胞的后端定位及其体轴极性形成中的作用机制
  • 批准号:
    30800648
  • 批准年份:
    2008
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
LARGE基因对口腔癌细胞中α-DG糖基化及表达的分子调控
  • 批准号:
    30772435
  • 批准年份:
    2007
  • 资助金额:
    29.0 万元
  • 项目类别:
    面上项目

相似海外基金

Collaborative Research: AF: Medium: Foundations of Anonymous Communication in Large-Scale Networks
合作研究:AF:媒介:大规模网络中匿名通信的基础
  • 批准号:
    2312241
  • 财政年份:
    2023
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Anonymous Communication in Large-Scale Networks
合作研究:AF:媒介:大规模网络中匿名通信的基础
  • 批准号:
    2312242
  • 财政年份:
    2023
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Anonymous Communication in Large-Scale Networks
合作研究:AF:媒介:大规模网络中匿名通信的基础
  • 批准号:
    2312243
  • 财政年份:
    2023
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Nonconvex Methods and Models for Learning: Towards Algorithms with Provable and Interpretable Guarantees
AF:大型:协作研究:非凸学习方法和模型:走向具有可证明和可解释保证的算法
  • 批准号:
    1704656
  • 财政年份:
    2017
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Nonconvex Methods and Models for Learning: Toward Algorithms with Provable and Interpretable Guarantees
AF:大型:协作研究:非凸学习方法和模型:具有可证明和可解释保证的算法
  • 批准号:
    1704860
  • 财政年份:
    2017
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Algebraic Proof Systems, Convexity, and Algorithms
AF:大型:协作研究:代数证明系统、凸性和算法
  • 批准号:
    1565235
  • 财政年份:
    2016
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Algebraic Proof Systems, Convexity, and Algorithms
AF:大型:协作研究:代数证明系统、凸性和算法
  • 批准号:
    1565264
  • 财政年份:
    2016
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
AF: Medium: Collaborative research: Advanced algorithms and high-performance software for large scale eigenvalue problems
AF:中:协作研究:大规模特征值问题的先进算法和高性能软件
  • 批准号:
    1505970
  • 财政年份:
    2015
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Reliable Quantum Communication and Computation in the Presence of Noise
AF:大型:协作研究:噪声存在下的可靠量子通信和计算
  • 批准号:
    1629809
  • 财政年份:
    2015
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
AF: Medium: Collaborative research: Advanced algorithms and high-performance software for large scale eigenvalue problems
AF:中:协作研究:大规模特征值问题的先进算法和高性能软件
  • 批准号:
    1510010
  • 财政年份:
    2015
  • 资助金额:
    $ 43.3万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了