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

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

• 批准号: 1012042
• 负责人: Piotr Indyk
• 金额: $ 43.3万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1012042&HistoricalAwards=false
• 关键词: AF; Large; Collaborative; Research; Compact

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.

在科学、工程和商业的许多领域，高带宽传感器和摄像头、大规模模拟或基于网络的大规模数据收集正在以前所未有的速度生成大量数据集。 这些数据大部分都直接或间接地具有几何特征。 例如，第二代激光雷达可以以15-20厘米的分辨率绘制地球表面地图；大型综合望远镜每晚将产生约 30 TB 的数据；每分钟有 13 个小时的视频上传到 YouTube； Facebook 管理着超过 400 亿张照片，需要超过 1 PB 的数据。这些数据集为实现几年前难以想象的新颖功能提供了巨大的机会。 然而，利用这些机会并将这些大量异构数据转换为对不同类型的应用程序和用户有用的信息需要解决具有挑战性的算法问题。 解决这一挑战的有效方法是设计有效的方法来生成此类几何数据集的信息丰富且简洁的摘要。 这些摘要必须适用于多种规模，并允许近似但有效地回答各种查询。 该项目的目标是研究紧凑表示的理论基础和用于组织、总结、互相关、互连和查询大型分布式几何数据集的高效算法。该项目将设计计算多种风格的摘要的方法，全部具有可证明的属性。 摘要可以是组合和度量（核心集和内核）、代数（线性草图）、拓扑（持久性图）、基于特征和结构（编码数据中的自相似性）。 他们旨在捕获的属性从低级度量属性（例如点集的直径或宽度）扩展到揭示数据内部结构的高级属性（例如对称性和重复模式的检测）。 这种处理必须在来自传感器的数据存在不确定性的情况下完成，并优化多种性能指标，包括分布在网络中多个位置的数据的通信成本。 该项目的另一个关键方面是，它的目的不是理解孤立的单个数据集，而是理解不同数据集之间的相互关系和对应关系，并且通过仅传达摘要信息来实现这一点，甚至不需要将所有数据放在一个地方。这项工作涉及理论计算机科学和应用数学的许多主题，包括低失真嵌入、压缩感知、传输度量、谱图理论或谐波分析、机器学习和计算拓扑。