Computing over Compressed Graph-Structured Data

该项目旨在通过将我们开发的最优压缩树数据结构扩展到某些类型的图来将压缩数据的计算引入海量图结构数据集。知识图或社交网络等图结构的数据集的重要性和大小都在增长；与此同时，计算越来越多地推向存储容量有限的移动设备。许多应用程序生成较大但部分重复且可预测的数据集，这使得它们是可压缩的；但在移动设备上，只有当数据可以直接以适合设备内存的压缩表示形式进行查询时，数据才有用。目前用于计算压缩数据的方法还不能很好地适用于这种情况。为了能够对压缩的图结构数据进行查询，我们需要回答三个研究问题。我们需要知道图结构数据的内在信息含量，以便我们可以决定数据集是否可以被充分压缩到本地内存中。2.我们需要知道如何有效地压缩图结构数据，以便在移动设备上经济地传输和存储图结构数据。3.我们需要知道如何在压缩表示上回答查询，以便在查询图结构的数据集时能够有效地利用其可压缩性。该项目将结合信息论、数据压缩和简洁数据结构的方法，实施三个工作包1。我们将提出随机源和经验熵的新概念，以逼近图结构数据的内在信息量。2.为了有效地压缩图结构的数据，我们将基于概率上下文无关文法(PCFGs)和概率多上下文无关文法(PMCFGs)开发新的压缩方法。3.我们将把我们的简洁树数据结构工具应用和扩展到新类型的图和RNA结构数据，以便能够直接在压缩的图结构数据上进行计算。我们将使用工作包的结果来创建空间高效的数据结构的通用工具箱，以简化使用海量图形结构数据集的应用程序的开发。

The project aims to bring computation over compressed data to massive graph-structured datasets by extending optimally-compressed tree data structures we developed to certain classes of graphs. Graph-structured datasets such as knowledge graphs or social networks are growing in importance and size; at the same time, computation is increasingly pushed to mobile devices with limited memory capacity. Many applications yield large, but partially repetitive and predictable datasets, which makes them compressible; but on mobile devices, data is only useful when it can be queried directly in a compressed representation that fits into the device memory. Current methods for computing over compressed data do not yet work well for this scenario.In order to enable queries on compressed graph-structured data we need to answer three research questions.1. We need to know the intrinsic information content of graph-structured data so that we can decide whether a dataset can be sufficiently compressed to fit into local memory. 2. We need to know how to effectively compress graph-structured data, so that we can economically transmit and store graph-structured data on mobile devices. 3. We need to know how to answer queries on a compressed representation, so that we can make effective use of its compressibility while querying over a graph-structured dataset. This project will combine methods from information theory, data compression, and succinct data structures, to carry out three work packages.1. We will propose new notions of random sources and empirical entropy in order to approximate the intrinsic information content of graph-structured data. 2. We will develop new compression methods based on probabilistic context-free grammars (PCFGs) and probabilistic multiple context-free grammars (PMCFGs) in order to effectively compress graph-structured data. 3. We will apply and extend our tools for succinct tree data structures to new types of graphs and RNA structure data in order to enable computing directly over compressed graph-structured data. We will use the outcomes of the work packages to create a versatile toolbox of space-efficient data structures to ease the development of applications working with massive graph-structured datasets.