OnPair: Short Strings Compression for Fast Random Access
Francesco Gargiulo, Rossano Venturini · 2025
Read OnPair: Short Strings Compression for Fast Random Access by Francesco Gargiulo, Rossano Venturini (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-02280.txt.
Introduction
Databases in memory need short strings squeezed hard yet readable one at a time, and a 2025 arXiv paper by Francesco Gargiulo and Rossano Venturini offers a compressor built for that niche. Their method, OnPair, grows a dictionary by merging the most common neighbor pairs in one pass over a sample.
A capped variant keeps entries at sixteen bytes, which speeds up matching. Because each string is compressed on its own, any single value can be read without unpacking a block. On real datasets the pair matched the squeeze of the standard learned method while running faster and using less memory. The authors aim it at in memory stores.
Catalog record
| CREATOR | Francesco Gargiulo, Rossano Venturini |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-02280
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
OnPair: Short Strings Compression for Fast Random Access Francesco Gargiulo, Rossano Venturini Abstract . We present OnPair , a dictionary-based compression algorithm designed to meet the needs of in-memory database systems that require both high compression and fast random access. Existing methods either achieve strong compression ratios at significant computational and memory cost (e.g., BPE ) or prioritize speed at the expense of compression quality (e.g., FSST ). OnPair bridges this gap by employing a cache-friendly dictionary construction technique that incrementally merges frequent adjacent substrings in a single sequential pass over a data sample. This enables fast, memory-efficient training without tracking global pair positions, as required by traditional BPE . We also introduce OnPair16 , a variant that limits dictionary entries to 16 bytes, enabling faster parsing via optimized longest prefix matching. Both variants compress strings independently, supporting fine-grained random access without block-level overhead. Experiments on real-world datasets show that OnPair and OnPair16 achieve compression ratios comparable to BPE while significantly improving compression speed and memory usage. 1. Introduction Main memory database systems are essential in data-intensive applications where low-latency access and high throughput are crucial (see ( Faerber et al. 2017 ) and references therein). Systems like SAP HANA ( Färber et al. 2012 ) , HyPer ( Kemper and Neumann 2011 ) , and MonetDB ( Idreos et al. 2012 ) eliminate traditional disk I/O bottlenecks by retaining data in DRAM, significantly accelerating query processing. However, a critical bottleneck remains: the rapid growth in data volumes continues to outpace improvements in DRAM capacity and cost-efficiency. As a result, storing large datasets entirely in memory without incurring significant hardware costs becomes increasingly infeasible. Data compression emerges as a natural remedy to this problem, with the dual goals of reducing memory footprint and preserving—or ideally accelerating—query performance. In database systems, compression techniques can be applied at varying granularities, ranging from fine-grained approaches (individual fields) to coarser-grained methods (records, columns, or entire blocks). However, not all compression strategies are equally suited for in-memory workloads, especially when fast random access to individual data entries is needed. Compression schemes can be broadly classified into two types: • Lightweight compression algorithms ( Abadi et al. 2006 ; Damme et al. 2017 ) are typically designed to prioritize decompression speed and direct operability on compressed data, trading off higher compression ratios for faster execution. Examples include frame-of-reference , delta encoding , domain encoding , run-length encoding , and null suppression . These methods are particularly effective in columnar storage layouts, where data locality allows for more aggressive optimizations. • Heavyweight compression algorithms, such as LZ77-based methods (like gzip ( Deutsch 1996 ) and Zstandard ( Collet and Kucherawy 2018 ) ), operate at coarser levels. These achieve higher compression ratios by leveraging redundancy across larger data segments. However, they are oblivious to the structure of the underlying data, meaning that it is not possible to interpret (and thus operate on) the compressed bytes. For string data specifically, domain encoding is widely used: it replaces variable-length strings with fixed-size identifiers that reference a dictionary. If the number of unique strings is small, this may yield substantial space savings. Compression can be further improved by using compressed dictionaries, and order-preserving dictionaries even support the direct execution of range queries without decompressing the actual data ( Liu et al. 2019 ; Binnig et al. 2009 ) . While domain encoding is highly effective, it is only applicable when the number of distinct values in a column is relatively small. In many practical scenarios, however, string columns contain a large number of unique entries, each of which may be short and infrequently repeated. In such cases, conventional domain encoding becomes ineffective. Similarly, general-purpose compression algorithms based on LZ77 are often unsuitable, as they require larger input sizes to discover redundancy and achieve meaningful compression. These approaches are not optimized for handling numerous small strings independently, which is common in real-world workloads. To address these limitations, Fast Static Symbol Table ( FSST ) ( Boncz et al. 2020 ) was introduced as a field-level string compression scheme designed for high-speed encoding and efficient random access. FSST employs an external dictionary to encode each string independently, substituting frequent substrings (up to 8 bytes in length) with compact single-byte tokens. However, FSST ’s dictionary construction process is heavily biased toward speed, which limits its ability to discover and exploit longer or more complex patterns in the data—ultimately resulting in lower compression levels. On the other hand, Byte-Pair Encoding ( BPE ) ( Gage 1994 ) achieves high compression ratios by iteratively merging the most frequent adjacent symbol pairs in the dataset. This results in dictionaries that effectively capture long and recurring patterns, making BPE highly effective at compressing string data. Like FSST , BPE is also naturally suited for scenarios that require fast random access, as each string can be compressed independently. However, despite its compression effectiveness, BPE is often impractical for large-scale string compression due to its substantial computational and memory overhead. Building the dictionary requires repeatedly scanning and updating global frequency statistics, which involves frequent, non-local accesses to token positions across the dataset—an operation that is not cache-friendly. In addition, the algorithm must explicitly track the positions of all token pairs in order to apply replacements efficiently, which incurs significant memory usage. In this paper, we present OnPair and its optimized variant OnPair16 , two compression algorithms specifically designed to combine strong compression ratios with fast, fine-grained random access. The main innovations of this work are: • A scalable, cache-friendly dictionary construction algorithm . Unlike traditional BPE , which relies on costly (both in time and memory) global frequency statistics, OnPair incrementally merges frequent adjacent token pairs during a single sequential pass over a data sample, enabling a fast and memory-efficient dictionary population. • An optimized longest prefix matching algorithm . The fixed token length in OnPair16 enables several implementation-level optimizations—including bitwise comparisons, inlined suffixes, and efficient bucket indexing—that improve compression performance. • A cache-aware design for high decompression speed . The dictionary is compact enough to fit in the L2 cache and decoding is a predictable, SIMD-friendly process. Our experiments show that OnPair and OnPair16 match the compression effectiveness of BPE while being significantly faster and more memory-efficient to train. This makes them especially well-suited for large-scale, in-memory workloads where traditional BPE becomes impractical. OnPair16 , in particular, offers an attractive speed-quality trade-off: it retains nearly the same compression ratio as OnPair , but benefits from hardware-friendly design choices that accelerate both compression and decompression. 2. Related Work In this section, we discuss the primary approaches to the problem, distinguishing between block-based solutions that group strings together and methods that allow independent decompression of strings. Each approach is analyzed in terms of its benefits and drawbacks, particularly for use cases requiring fast random access to individual strings. 2.1. Block-Based Solutions General-purpose compressors like gzip ( Deutsch 1996 ) , LZ4 ( Collet 2011 ) , and Zstandard ( Collet and Kucherawy 2018 ) combine ideas from LZ77 compression ( Ziv and Lempel 1977 ) with entropy coding techniques, typically utilizing variants of Huffman coding ( Huffman 1952 ) or Asymmetric Numeral Systems ( Duda 2014 ) . LZ77 is