Learned Static Function Data Structures
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
SurGBSA: Learning Representations From Molecular Dynamics Simulations
Self-supervised pretraining from static structures of drug-like compounds and proteins enable powerful learned feature representations. Learned features demonstrate state of the art performance on a range of predictive t…
Representation LearningIncremental learning of environment interactive structures from trajectories of individuals
This work proposes a novel method for estimating the influence that unknown static objects might have over mobile agents. Since the motion of agents can be affected by the presence of fixed objects, it is possible use th…
Incremental LearningPositionA coarse-to-fine approach for dynamic-to-static image translation
Dynamic-to-static image translation aims to convert the dynamic scene into static so that dynamic elements are eliminated from the image. Recent works typically see the problem as an image-to-image translation task, and …
Image InpaintingImage-to-Image TranslationTranslationVisual Place RecognitionEfficiently Evolving Swarm Behaviors Using Grammatical Evolution With PPA-style Behavior Trees
Evolving swarm behaviors with artificial agents is computationally expensive and challenging. Because reward structures are often sparse in swarm problems, only a few simulations among hundreds evolve successful swarm be…
Evolutionary AlgorithmsIncremental Learning for Heterogeneous Structure Segmentation in Brain Tumor MRI
Deep learning (DL) models for segmenting various anatomical structures have achieved great success via a static DL model that is trained in a single source domain. Yet, the static DL model is likely to perform poorly in …
Brain Tumor SegmentationIncremental LearningPseudo LabelSegmentation+1