Efficient Data Reduction and Summarization

海量数据(包括数据流)的普遍存在给数据可视化和探索性数据分析带来了相当大的挑战。大约15年前，TB级的数据集仍被认为是“荒谬的”。然而，由斯坦福线性加速中心(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.