OnPair: Short Strings Compression for Fast Random Access

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.