Computing over Compressed Graph-Structured Data

压缩图结构数据的计算

• 批准号: EP/X039447/1
• 负责人: Sebastian Wild
• 金额: $ 52.92万
• 依托单位: University of Liverpool
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX039447%2F1
• 关键词: Computing; over; Compressed; Graph; Structured

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.

该项目旨在通过将开发到某些图形类别的最佳压缩树数据结构扩展到大量的图形结构数据集中。图形结构的数据集（例如知识图或社交网络）的重要性和规模正在增长；同时，越来越多地将计算推向具有有限内存容量的移动设备。许多应用程序产生了大型但部分重复且可预测的数据集，这使其可压缩；但是，在移动设备上，只有在可以直接在适合设备内存的压缩表示中查询数据时才有用。当前用于压缩数据计算的方法在这种情况下还不能很好地工作。为了对压缩的图形结构数据进行查询，我们需要回答三个研究问题1。我们需要了解图形结构化数据的内在信息内容，以便我们可以决定是否可以充分压缩数据集以适合本地内存。 2。我们需要知道如何有效地压缩图形结构化数据，以便我们可以在移动设备上经济传输和存储图形结构化数据。 3。我们需要知道如何在压缩表示形式上回答查询，以便在通过图形结构的数据集查询时，可以有效利用其可压缩性。该项目将结合信息理论，数据压缩和简洁数据结构的方法，以执行三个工作包。1。我们将提出新的随机来源和经验熵的概念，以近似图形结构化数据的内在信息内容。 2。我们将基于概率无上下文语法（PCFG）和概率多个无上下文的语法（PMCFG）开发新的压缩方法，以有效地压缩图形结构化数据。 3。我们将应用并扩展我们的工具将简洁的树数据结构用于新类型的图形和RNA结构数据，以直接通过压缩的图形结构数据启用计算。我们将使用工作包的结果来创建一个多功能工具箱的空间有效数据结构，以简化使用大量的图形结构数据集的应用程序的开发。