Recipient organisationPhilipps University of Marburg
Funding£177K
PeriodJun 2025 — Feb 2027
In plain English
AI plain-English summary
Your phone or smartwatch can't run many powerful apps because the data they need—like massive knowledge graphs or social networks—simply won't fit into the device's limited memory. This project tackles that bottleneck. Graph-structured datasets—think of the connections between genes, proteins, or people—are growing explosively, but mobile devices have tight memory constraints. Current compression methods let you store data, but not query it directly while compressed. You have to decompress first, which defeats the purpose. The researchers aim to change that by extending their earlier work on optimally compressed tree data structures to graphs. If successful, this work would let a mobile device answer queries on a compressed graph without ever unpacking it. That could make genome analysis, navigation, or social network searches possible on a phone rather than requiring a server. The project is fundamental computer science—it combines information theory, data compression, and succinct data structures to understand the intrinsic information content of graphs. There is no immediate consumer product, but similar foundational work on compressed data structures has already enabled everything from search engines to DNA sequence aligners.
View original technical description
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.
Plain English summaries and category classifications on this site are generated by AI and may not perfectly reflect the original research.
Is something wrong? Let us know