III: Small: Compression-Aware Algorithms for Massive Datasets

III：小型：海量数据集的压缩感知算法

• 批准号: 1117684
• 负责人: Gabriel Robins
• 金额: $ 50万
• 依托单位: University of Virginia Main Campus
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117684&HistoricalAwards=false
• 关键词: III; Small; Compression; Aware; Algorithms

As many application domains continue to generate data at exponentially increasing rates, much of the data that is gathered is stored in a compressed format. However, very few classic data processing algorithms have been updated to handle compressed data. This project aims to address this gap by developing (i) algorithms for massive data sets that can directly operate on compressed data; and (ii) compression schemes that are aware of the algorithms that would operate on the data. In many settings, algorithms that manipulate very large composite objects while interacting only with their succinct descriptions can substantially reduce the time and memory requirements relative to their counterparts that have to work with uncompressed representations of the same data. These performance gains are realized by leveraging highly repetitive or parametrically specified input structures, to enable algorithms to manipulate very large composite objects while interacting only with their compressed descriptions. Anticipated results of the project include new geometric algorithms that solve problems such as convex hull, Voronoi diagrams, nearest points and earth-mover distances when the inputs are in compressed format; new graph algorithms that compute minimum spanning trees, shortest paths, and network flows on compressed input graphs; and new compression-aware data structures that support efficient storing, querying and processing of compressed data. All the algorithmic contributions will be validated with experiments on real and synthetic massive data sets. The resulting algorithms are likely to find application in many different domains including networks, genomics, databases, computer graphics, artificial intelligence, geographic information systems, integrated circuit design, and computer-aided engineering. Broader Impacts: Compression-aware data processing algorithms and algorithm-aware data compression schemes have applications across a wide range of tasks that involve processing of massive data sets consisting of large data objects (e.g., images, sequences, graphs). The formulations, algorithms, codes, and theories that will be developed and disseminated by this project are likely to contribute to the development of efficient and practical algorithms and data structures that could impact the way in which organizations collect, store, process, such data. The project offers enhanced research based training opportunities for students in an area of considerable theoretical as well as practical significance. Additional information about the project can be found at: http://www.cs.virginia.edu/robins

由于许多应用程序域继续以指数级增长的速度生成数据，因此收集的大部分数据都以压缩格式存储。然而，很少有经典的数据处理算法被更新来处理压缩数据。该项目旨在通过开发(i)可以直接操作压缩数据的大规模数据集算法来解决这一差距；以及（ii）压缩方案，该方案知道将对数据进行操作的算法。在许多情况下，与必须处理相同数据的未压缩表示的对应算法相比，操作非常大的复合对象而仅与它们的简洁描述交互的算法可以大大减少时间和内存需求。这些性能提升是通过利用高度重复或参数化指定的输入结构来实现的，使算法能够操作非常大的复合对象，同时只与它们的压缩描述进行交互。该项目的预期结果包括：当输入是压缩格式时，新的几何算法可以解决诸如凸壳、Voronoi图、最近点和推土机距离等问题；在压缩输入图上计算最小生成树、最短路径和网络流的新图算法；新的压缩感知数据结构支持高效存储、查询和处理压缩数据。所有算法的贡献将在真实和合成的海量数据集上进行实验验证。由此产生的算法可能会在许多不同的领域得到应用，包括网络、基因组学、数据库、计算机图形学、人工智能、地理信息系统、集成电路设计和计算机辅助工程。更广泛的影响：压缩感知数据处理算法和算法感知数据压缩方案在涉及处理由大型数据对象（例如，图像，序列，图形）组成的大量数据集的广泛任务中具有应用。该项目将开发和传播的公式、算法、代码和理论可能有助于开发有效和实用的算法和数据结构，这些算法和数据结构可能影响组织收集、存储和处理此类数据的方式。该项目为学生在一个具有重要理论和实践意义的领域提供了增强的基于研究的培训机会。有关该项目的更多信息可以在http://www.cs.virginia.edu/robins上找到