Efficient Approaches to Summarize Sparse & Dynamic Datasets

在线分析处理工具越来越多地用于各种应用，从商业应用，地球科学应用到数字图书馆。这样的应用程序需要处理稀疏和非常大的数据集。此外，这种数据以仅附加的方式更新。在这项提案中，新的总结和聚合技术正在开发的高维数据集是稀疏的，并在仅附加的方式更新。这些技术本质上是多分辨率的，并且利用了磁盘可以顺序读取存储的信息的效率。冰山立方体，这已被证明是特别有益的稀疏数据立方体，也正在有效地计算和具体化。这种稀疏数据立方体使用范围表示，并且通过维护关于前k和后k元素的信息来导出近似值。多维数据不仅在存储和检索方面提出了重大挑战，而且分析这些数据成为一个基本问题。本研究的重点是开发高效的表示非常高维的数据，稀疏和动态的问题。有效的表示将使快速分析高维数据，特别是在上下文中的空间和时间数据，高分辨率图像和时间序列。该研究是及时的，很可能对大型高维数据集的高效分析工具的开发产生深远的影响。研究结果将有助于工业和科学界迫切需要的下一代在线分析处理工具的设计和开发。目前，由于大型数据集空间连接的复杂性，地球科学家经常需要缩小地球科学计算模型。类似地，分析师避免使用高维数据集的数据立方体。所产生的工具和算法将是朝着缓解其中许多问题迈出的一步。PI经常与当地高科技行业的成员进行互动，为解决与高维数据的可扩展管理相关的问题提供必要的指导。研究结果将直接有助于这些努力。该研究还将作为研究生高级培训的工具，开发的软件将用于研究生和本科教育。

On Line Analytical Processing tools are increasingly being used in diverse applications that range from business applications, earth science applications, to digital libraries. Such applications need to deal with sparse and very large data sets. Furthermore, such data is updated in append-only manner. In this proposal novel summarization and aggregation techniques are being developed for high-dimensional datasets which are sparse and are updated in append-only manner. These techniques are multi-resolution in nature, and exploit the efficiency with which disks can read sequentially stored information. Iceberg CUBES, which have proved to be particularly beneficial for sparse data cubes, are also being efficiently computed and materialized. Such sparse data cubes are represented using ranges, and approximations are derived by maintaining information regarding top-k and bottom-k elements. Multidimensional data poses significant challenges not only in terms of storage and retrieval but analyzing such data becomes a fundamental problem. The focus of this research is on the issue of developing efficient representations for very high-dimensional data that are both sparse and dynamic. Efficient representations will enable fast analysis of high-dimensional data specially in the context of spatial and temporal data, high resolution images, and time sequences. The research is timely and is likely to have a profound impact on the development of efficient analysis tools for large high-dimensional datasets. The research results will contribute towards the design and development of next generation of on-line analytical processing tools sorely needed both in industrial as well as scientific communities. Currently, earth scientists often need to scale down earth-science computational models due to the complexity of spatial joins for large datasets. Similarly, datacubes for high dimensional datasets are avoided by analysts. The tools and algorithms produced will be a step towards alleviating many of these problems. The PIs frequently interact with members of the local high-tech industry to provide necessary guidance for solving problems related to the scalable management of high dimensional data. The research results will directly contribute to such efforts. The research will also serve as a vehicle for the advanced training of graduate students and the software developed will be used in both graduate and undergraduate education.