Efficient Data Reduction and Summarization

高效的数据缩减和汇总

• 批准号: 0808864
• 负责人: Ping Li
• 金额: $ 25万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2014-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0808864&HistoricalAwards=false
• 关键词: Efficient; Data; Reduction; Summarization

The ubiquitous phenomenon of massive data (including data streams) imposes considerable challenges in data visualization and exploratory data analysis. About 15 years ago, terabyte datasets were still considered `ridiculous.' However, modern datasets managed by Stanford Linear Acceleration Center (SLAC), NASA, NSA, etc. have reached the perabyte scale or larger. Corporations such as Amazon, Wal-Mart, Ebay, and search engine firms are also major generators and users of massive data. The general theme of data reduction and summarization has become an active and highly inter-disciplinary area of research. This project proposes to develop various approximation techniques, which generate a "fingerprint" or "sketch" of the massive data by transforming the original data. These `sketches' are reasonably small (hence easy to store) and can provide approximate answers which are usually good enough for practical purposes. This proposal concerns the fundamental problems of processing/transforming massive (possibly dynamic) data. In particular, it focuses on (A) developing systematic fundamental tools for effective data reduction and efficient data summarization; (B) applying these tools to improve numerical analysis, visualization, and exploratory data analysis. Two lines of theoretically sound techniques for data reduction and summarization will be developed and further improved: (1) the method of stable random projections (SRP), effective in heavy-tailed data; (2) the method of Conditional Random Sampling (CRS), mainly for sparse data. Concrete applications of SRP and CRS will be investigated. Widely-used basic numerical algorithms can be rewritten by taking advantage of SRP or CRS. Popular methods/tools for exploratory data analysis will also benefit considerably from the development of data reduction techniques.

海量数据（包括数据流）无处不在的现象给数据可视化和探索性数据分析带来了相当大的挑战。大约15年前，tb级的数据集还被认为是“荒谬的”。然而，由斯坦福线性加速中心（SLAC）、NASA、NSA等管理的现代数据集已经达到了兆位字节或更大的规模。亚马逊（Amazon）、沃尔玛（Wal-Mart）、Ebay和搜索引擎公司等公司也是海量数据的主要产生者和用户。数据简化和总结的总体主题已经成为一个活跃的和高度跨学科的研究领域。本项目拟开发各种近似技术，通过对原始数据的变换，生成海量数据的“指纹”或“草图”。这些“草图”相当小（因此易于存储），并且可以提供大致的答案，通常足以用于实际目的。这个建议涉及处理/转换大量（可能是动态的）数据的基本问题。特别是，它侧重于(A)开发系统的基本工具，用于有效的数据简化和高效的数据总结；(B)应用这些工具来改进数值分析、可视化和探索性数据分析。将发展和进一步改进两种理论上合理的数据简化和总结技术：(1)稳定随机预测（SRP）方法，在重尾数据中有效；(2)条件随机抽样（CRS）方法，主要针对稀疏数据。将研究SRP和CRS的具体应用。广泛使用的基本数值算法可以利用SRP或CRS进行重写。探索性数据分析的流行方法/工具也将大大受益于数据约简技术的发展。