Efficient Approaches to Summarize Sparse & Dynamic Datasets

总结稀疏性的有效方法

• 批准号: 0223022
• 负责人: Amr El Abbadi
• 金额: --
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0223022&HistoricalAwards=false
• 关键词: Efficient; Approaches; Summarize; Sparse; &amp

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.

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