: In this paper, we study the problem of storing and searching in datasets of variable-length strings, a core primitive in key-value stores, (graph) DBs, and search engines. However, enabling such search capabilities in ORAM scenarios, where data are stored on an honest-but-curious server, remains challenging. We address this problem by proposing a practical design that combines Ring ORAM (Ren et al., 2015) to hide access patterns to outsourced data, with a Patricia trie (Ferragina and Grossi, 1999; Ferragina et al., 2025) for space-efficient search over variable-length strings. The resulting scheme supports search over variable-length string datasets in an ORAM scenario, while retaining efficient storage and access both on the client and the server. We evaluated our scheme on datasets having size up to 273 GB, showing that it supports complex string queries, with only 2 Ring ORAM accesses on the server, incurring a client-server communication cost below 3 MiB, a client memory footprint of at most 200 MB, and negligible client computation time per query. Although we assume bounded-length strings, the bound is high enough to handle most practical use cases.
Mariagiovanna Rotundo, Giuseppe Persiano, P. Ferragina· International Conference on...· 0 citations
: Oblivious RAM (ORAM) is a general-purpose storage technique that hides memory access patterns, protecting data, queries, and results from untrusted honest-but-curious servers. While traditional ORAM supports only basic reads and writes, recent works have addressed the problem of enabling richer queries by designing oblivious versions of simple data structures (e.g., maps, sets, queues). In this paper, we take a distinct step by introducing two building blocks that make it easy to construct many advanced oblivious and compressed data structures efficiently and securely. Our approach builds on recent results showing that most (compressed) data structures can be implemented using two fundamental primitives: Rank and Select, which count and locate symbol occurrences within a sequence. We present the first oblivious implementations of Rank and Select that require only a single ORAM access per operation, use O(1) client-side space, and add negligible client computation overhead. Thanks to their simplicity and efficiency, our oblivious Rank and Select provide a foundation for building a wide range of other oblivious compressed data structures, enabling privacy-preserving (compressed) data storage, indexing, and search in the cloud.
Mariagiovanna Rotundo, P. Ferragina· International Conference on...· 0 citations
It is argued that replacing autoregressive LLMs with DLMs within the same compression framework could overcome the throughput bottleneck caused by their one-symbol-per-step limitation, and the newly proposed DLM-based framework advances the state of the art in lossless text compression.
We study the problem of lossless compression of source code, motivated by the storage demands of large-scale software archives, such as Software Heritage (https://www.softwareheritage.org/). General-purpose compressors (e.g., zstd, bzip2) offer a good trade-off between compression ratio and speed, but fail to exploit all special regularities inherent in source code. Recent approaches leverage Large Language Models (LLMs) within Shannon's symbol-ranking framework, relying on a scheme in which the predicted rank can grow arbitrarily. While effective at reducing space, this setting incurs significant throughput degradation, and leaves open the question whether it is necessary to explicitly encode all ranks. In this work, we introduce LLM-based compressors deploying two novel symbol-ranking variants that bound predictions to the top-$T$ ranks ($T=1$ or $63$), with out-of-threshold symbols stored as exceptions and compressed jointly with the rank stream via general-purpose compressors. We conduct the first large-scale evaluation of LLM-based source code compression across 30 LLMs, including general-domain, code-specialized, and quantized models. Our $T$-bounded approach outperforms prior LLM-based compressors both in compression ratio (up to 37% relative improvement) and compression throughput (40% faster). Compared to general-purpose compressors (e.g., zstd, bzip2), we obtain up to 82% relative compression gain but at a lower speed, thus offering a new trade-off point in the compression-speed spectrum. We also show that these gains are stronger on source code than on natural language, suggesting an interesting indication, namely that source code exposes regularities captured by LLMs but missed by general-purpose exact-match-based compressors. We conclude by commenting on open problems that offer theoretical and practical avenues of research.
Angelo Nardone, P. Ferragina· arXiv.org· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
