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.

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