AutoCSF: Provably Space-Efficient Indexing of Skewed Key-Value Workloads via Filter-Augmented Compressed Static Functions

David Torres Ramos, Vihan Lakshman, Chen Luo, Todd Treangen, Benjamin Coleman · 2026

Read AutoCSF: Provably Space-Efficient Indexing of Skewed Key-Value Workloads via Filter-Augmented Compressed Static Functions by David Torres Ramos, Vihan Lakshman, Chen Luo, Todd Treangen, Benjamin Coleman (2026) 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-2603-24882.txt.

Introduction

Torres Ramos and co-authors introduce AutoCSF, a space-efficient indexing method for skewed workloads. Billions of entries dominated by one frequent value arise in genomics k-mer tables and beyond. Compressed static functions with pre-filters help, but prior designs rely on heuristics without guarantees. AutoCSF derives a rigorous criterion for when filter augmentation pays off. Its framework pairs compressed functions with membership structures beyond the classic Bloom filter. Theoretical guarantees bound the total space, and the open-source code saves space while keeping query latency low.

Catalog record

CREATORDavid Torres Ramos, Vihan Lakshman, Chen Luo, Todd Treangen, Benjamin Coleman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54641
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.24882

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

AutoCSF: Provably Space-Efficient Indexing of Skewed Key-Value Workloads via Filter-Augmented Compressed Static Functions David Torres Ramos, Vihan Lakshman, Chen Luo, Todd Treangen, Benjamin Coleman Abstract . We study the problem of building space-efficient, in-memory indexes for massive key-value datasets with highly skewed value distributions. This challenge arises in many data-intensive domains and is particularly acute in computational genomics, where k k -mer count tables can contain billions of entries dominated by a single frequent value. While recent work has proposed to address this problem by augmenting compressed static functions (CSFs) with pre-filters, existing approaches rely on complex heuristics and lack formal guarantees. In this paper, we introduce a principled algorithm, called AutoCSF, for combining CSFs with pre-filtering to provably handle skewed distributions with near-optimal space usage. We improve upon prior CSF pre-filtering constructions by (1) deriving a mathematically rigorous decision criterion for when filter augmentation is beneficial; (2) presenting a general algorithmic framework for integrating CSFs with modern set membership data structures beyond the classic Bloom filter; and (3) establishing theoretical guarantees on the overall space usage of the resulting indexes. Our open-source implementation of AutoCSF demonstrates space savings over baseline methods while maintaining low query latency. 1. Introduction Key-value stores are indispensable components of modern data infrastructure. As data volumes continue to balloon in size, there is increasingly a need to design new data structures for key-value lookups with small memory footprints while still enabling fast queries. When the set of key-value pairs is fixed (or changing infrequently), succinct retrieval data structures have emerged as a state-of-the-art class of techniques for indexing data with minimal space overhead. These retrieval structures offer the guarantee of returning the correct value when queried with any key in the index, but may return arbitrary outputs for any key not in the set. Amongst these succinct retrieval methods, compressed static functions (CSFs) achieve space usage proportional to the empirical entropy of the value set. Thus, when the list of values in the index is highly repetitive, CSFs can achieve significantly improved compression rates compared to distribution-agnostic methods, typically within a constant factor of the information-theoretic lower bound. However, one limitation of CSFs is that, by construction, the index must use a lower bound of at least 1 bit per key. Consequently, if the value distribution is highly skewed, namely when a single value is associated with the majority of the keys, CSFs fall short of achieving optimal compression rates. This barrier is especially prominent in computational genomics where long read k -mer count tables, which map keys of k -length nucleotide substrings to their frequency of occurrence in a given genome, often exhibit extreme skew with over 90% of k -mers having a value of 1. This challenge was previously identified in the literature by 27 who proposed a new index called a Bloom-enhanced Compressed Static Function (BCSF) which augments a CSF with a Bloom filter to handle the dominating value. In particular, a BCSF index first inserts all keys not associated with the dominating value into a Bloom filter. Additionally, since Bloom filters admit false positives, the BCSF index will insert the false positive keys associated with the dominating value into the CSF. At query time, given a key k , a BCSF first checks if k is in the Bloom filter. If the filter returns false, then we can conclude that the associated value must be the dominating entity and simply return that value. If the filter returns true, we query the CSF and return the output. This construction guarantees correctness while eliminating the need to index the dominating value directly. Inspired in part by this work, 13 also leverage this idea of filter augmentation to develop a learned CSF index that allows for improved compression via machine learning. Despite the effectiveness of filter-augmented CSFs, as demonstrated in these prior works in the literature, these data structure compositions introduce additional complexity. In particular, it is not completely clear which key-value distributions might benefit from filter-augmented CSFs or how to set the false positive rate of the filter to minimize the overall space usage. Unlike standalone approximate set membership data structures, which maintain a monotonic relationship between the false positive rate and the size of the resulting filter, the relationship between the false positive rate and the overall index size in filter-augmented CSFs is complex to model. As an illustrative example, increasing the false positive rate of a filter might allow more values to pass through to the CSF, causing the value frequency distribution to be more closely-aligned to powers of 2 and thus more highly compressible by Huffman codes. While the work of ( 27 ) present a set of criteria for making these parameter choices in a BCSF, they are heuristic-driven as opposed to mathematically principled and, as we will demonstrate in this paper, can be misleading and result in suboptimal decisions. Motivated by these shortcomings, we ask the following research questions: (1) Can we develop a mathematically principled decision criterion to determine when a set of key-value pairs would benefit from filter-augmentation to save space versus simply using only a CSF? (2) Given a filter-augmented CSF, can we design an efficient algorithm for determining the optimal parameters for the pre-filter that minimizes the total space usage of the index? (3) Can we design a general framework for Questions (1) and (2) that can be applied to all set membership data structures in the literature, as opposed to just the classical Bloom filter? In this paper, we affirmatively answer all three of these research questions through a single algorithm, which we call AutoCSF. The key insight behind AutoCSF is that while modeling the exact memory cost of a filter-augmented CSF appears to be intractable – or at least unwieldy to analyze – we can derive analytically clean upper and lower bounds on the difference in space usage between a CSF and filter-augmented CSF. In other words, instead of attempting to develop separate cost models for the space usage of a CSF and filter-augmented CSF, we bound the difference in bits per key between the two data structures without ever having to explicitly construct either index . This observation drives the development of our AutoCSF algorithm, which first determines if filter-augmentation is beneficial and then, if a filter is helpful, provides near-optimal settings for the filter parameters. The AutoCSF framework can be applied to any approximate set membership data structure with a known relationship between the memory usage and false positive rate, allowing our results to easily extend to the large number of membership filters that have been developed over the last 50 years ( 3 ; 21 ; 1 ; 24 ; 9 ; 23 ; 22 ; 29 ; 17 ; 11 ; 20 ; 8 ; 25 ) . We implement AutoCSF in practice and verify that our theoretical results align closely with empirical results (i.e. the bounds are tight), thus providing a principled algorithm to effectively compose CSFs with prefilters. In summary, we make the following contributions • We demonstrate that the existing state-of-the-art heuristic-based decision criterion for filter-augmented CSFs (BCSF) can actively degrade performance, recommending filter configurations that increase space usage by up to 1 bit per

Read the complete text