III: Small: Compression-Aware Algorithms for Massive Datasets

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

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