I have over $18000$ curves that I need to compress to save $\geq 50\%$ of space. Each curve is described by points $f(1), f(2), ..., f(96)$, each $f(x)$ is 8-bit long. The curves in compressed form should have an equal length in bits, so that they can be indexed in $O(1)$ time a cache memory I want to store them in, although this criterion can be dropped if need be (but it still needs to be fast enough). The compression does not need to be lossless, but it should preserve the shape of curve reasonably well.
My first idea was to use polynomial curve fitting, but having to describe each curve by a number of coefficients (between 7 and 9 to achieve good approximations) is not very effective, since each coefficient is a float roughly 64 bits long.
Then I tried to cluster them using the k-means algorithm for some choices of $k \in [5, 300]$, but since the curves are mostly of a noisy shape, it did not yield good clustering.
I am interested in ways to compress the curves to less than half of their original space size with reasonably good preservation of their shape.
Here is a sample of ~50 curves from the set.