CAREER: Sketching Algorithms for Massive Data

职业：海量数据的草图算法

• 批准号: 1350670
• 负责人: Jelani Nelson
• 金额: $ 51.28万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-05-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1350670&HistoricalAwards=false
• 关键词: CAREER; Sketching; Algorithms; Massive; Data

A sketch of a massive dataset is some compression of it which still allows for answering, sometimes only approximately, some pre-specified types of queries about the data. For many query types of interest, it turns out that sketches exist that provide exponentially smaller compressions. This feature has made sketching methods pervasive in coping with recent trends in data explosion to reduce both communication bandwidth and required storage capacity. Sketching has also been applied to obtain algorithmic speedup for certain high-dimensional problems such as nearest neighbor search, clustering, and low-rank approximation for large matrices, as well as to enable more efficient signal acquisition in a field that has come to be known as compressed sensing. This research plans to further the state of knowledge concerning three intertwined subtopics of sketching: streaming, dimensionality reduction, and compressed sensing.A fundamental question the PI will investigate is whether one can design sketches that are moderately "universal", in that the same sketch can be used to answer many different types of queries. Dimensionality reduction has been successfully used to circumvent the so-called "curse of dimensionality" in many problems, where the best known algorithms have running times that scale poorly with dimension. This research plans to study the tradeoffs between approximation quality, number of vectors in the data set, and target dimension, and to close gaps between known upper and lower bounds. Compressed sensing has found applications in a diverse range of areas, such as magnetic resonance imaging and photography. This research plans to investigate more efficient compressed sensing schemes for providing various types of approximate recovery guarantees.

大型数据集的草图是对其进行的一些压缩，这些压缩仍然允许回答（有时只是大约）一些预先指定的有关数据的查询类型。对于许多感兴趣的查询类型，事实证明存在提供指数级较小压缩的草图。这一特征使得草图绘制方法在应对最近的数据爆炸趋势中变得普遍，以减少通信带宽和所需的存储容量。草图也被应用于某些高维问题的算法加速，例如最近邻搜索，聚类和大型矩阵的低秩近似，以及在被称为压缩感知的领域中实现更有效的信号采集。本研究计划进一步了解草图的三个相互交织的子主题：流，降维和压缩感知。PI将研究的一个基本问题是，是否可以设计出适度的“通用”草图，即同一草图可以用于回答许多不同类型的查询。在许多问题中，维度约简已经成功地用于规避所谓的“维度灾难”，其中最著名的算法的运行时间随维度的缩放很差。这项研究计划研究近似质量，数据集中的向量数量和目标维度之间的权衡，并缩小已知上限和下限之间的差距。 压缩感知已经在各种领域中找到了应用，例如磁共振成像和摄影。本研究计划研究更有效的压缩感知方案，提供各种类型的近似恢复保证。