<p>I am looking for approaches storing strictly increasing natural-valued functions defined on a (subset of) <span class="math-container">$[0..N]$</span>:</p>
<p><span class="math-container">$$
\forall x \in X: 0 \le x \le N\\
f: X \to \mathbb N\\
\forall x,y\in X:\quad x&lt; y \Rightarrow f(x)&lt;f(y)
$$</span>
With the goal to optimize disk footprint and, preferably, with <span class="math-container">$O(1)$</span> random access time. In my particular case, these functions are almost affine or &quot;piecewise almost affine&quot;, if that's any help.</p>
<p>What would be the correct keywords that I could use to find such algorithms? Is there a book/article with an overview of existing approaches?</p>
<p><strong>edit</strong></p>
<p>There was a question in comments (now deleted) on what is &quot;almost affine&quot;. By this expression I mean that there exists an affine function <span class="math-container">$g$</span> on <span class="math-container">$X$</span> such that <span class="math-container">$$D = \sup_{x\in X} |f(x) - g(x)|$$</span> is &quot;small&quot;; we can suppose for now <span class="math-container">$D &lt; 256$</span>.</p>

CC BY-SA 4.0
2022-06-09T06:36:08.417Z
Can you clarify what you mean by "almost affine"? You mention disk footprint - how is the input f represented? Is f represented as a list of |X| values, i.e. you're looking for some compression method? Or is f represented by its "almost affine" pieces, i.e. you're looking for a searching method?
Mathias Rav
CC BY-SA 4.0
2022-06-15T15:45:59.237Z
@MathiasRav Thanks for relevant questions! 1) "Almost affine" - already answered in an edit; 2) looking for a compression method, with (in Haskell notation) "fast", preferably `O(1)`  `lookup :: Word32 -> Maybe Word64`

The input to build such a structure would be a list of pairs `(key, value)`, with ascending keys.
TZakrevskiy
<reference-request><ds.data-structures><succinct>
Data structures to store monotone functions
TZakrevskiy
# Data structures to store monotone functions

(Asked by: username_0 on 2022-06-06)

I am looking for approaches storing strictly increasing natural-valued functions defined on a (subset of) $[0..N]$:

$$
\forall x \in X: 0 \le x \le N\\
f: X \to \mathbb N\\
\forall x,y\in X:\quad x< y \Rightarrow f(x)
With the goal to optimize disk footprint and, preferably, with $O(1)$ random access time. In my particular case, these functions are almost affine or "piecewise almost affine", if that's any help.

What would be the correct keywords that I could use to find such algorithms? Is there a book/article with an overview of existing approaches?

**edit**

There was a question in comments (now deleted) on what is "almost affine". By this expression I mean that there exists an affine function $g$ on $X$ such that $$D = \sup\_{x\in X} |f(x) - g(x)|$$ is "small"; we can suppose for now $D < 256$.

**Tags:** reference-request, ds.data-structures, succinct
> **Comments:**
> **username_1**: Can you clarify what you mean by "almost affine"? You mention disk footprint - how is the input f represented? Is f represented as a list of |X| values, i.e. you're looking for some compression method? Or is f represented by its "almost affine" pieces, i.e. you're looking for a searching method?  
> **username_0**: @MathiasRav Thanks for relevant questions! 1) "Almost affine" - already answered in an edit; 2) looking for a compression method, with (in Haskell notation) "fast", preferably `O(1)`  `lookup :: Word32 -> Maybe Word64`  The input to build such a structure would be a list of pairs `(key, value)`, with ascending keys.  

---

## 0 answers

