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结构数据，以便能够直接在压缩的图结构数据上进行计算。我们将使用工作包的成果来创建一个多功能的节省空间的数据结构工具箱，以简化处理大量图形结构数据集的应用程序的开发。