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)<f(y) $$ 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?


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$.

  • $\begingroup$ 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? $\endgroup$ Jun 9, 2022 at 6:36
  • $\begingroup$ @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. $\endgroup$ Jun 15, 2022 at 15:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.