{"ID":2847668,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.27588","arxiv_id":"2510.27588","title":"Learned Static Function Data Structures","abstract":"We consider the task of constructing a data structure for associating a static set of keys with values, while allowing arbitrary output values for queries involving keys outside the set. Compared to hash tables, these so-called static function data structures do not need to store the key set and thus use significantly less memory. Several techniques are known, with compressed static functions approaching the zero-order empirical entropy of the value sequence. In this paper, we introduce learned static functions, which use machine learning to capture correlations between keys and values. For each key, a model predicts a probability distribution over the values, from which we derive a key-specific prefix code to compactly encode the true value. The resulting codeword is stored in a classic static function data structure. This design allows learned static functions to break the zero-order entropy barrier while still supporting point queries. Our experiments show substantial space savings: up to one order of magnitude on real data, and up to three orders of magnitude on synthetic data.","short_abstract":"We consider the task of constructing a data structure for associating a static set of keys with values, while allowing arbitrary output values for queries involving keys outside the set. Compared to hash tables, these so-called static function data structures do not need to store the key set and thus use significantly...","url_abs":"https://arxiv.org/abs/2510.27588","url_pdf":"https://arxiv.org/pdf/2510.27588v3","authors":"[\"Stefan Hermann\",\"Hans-Peter Lehmann\",\"Giorgio Vinciguerra\",\"Stefan Walzer\"]","published":"2025-10-31T16:09:53Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DB\",\"cs.LG\"]","methods":"[]","has_code":false}