Efficient Data Reduction and Summarization

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

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.