Compression of 18000 curves 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. 

 A: The simplest way to achieve 50% compression would be to use custom shorter variables. For instance, instead of encoding $f(i)$ in 8 bits, encode it in 4 bits, potentially with a common scaling factor.
Similarly, don't use 64 bits to store polynomial interpolation coefficients. 32 bits ought to be enough for anybody.
Finally, polynomials are not very good for interpolation, anyway, because they are highly variable at the ends. Better to use splines. You may get away with fewer degrees of freedom if you use splines than with polynomials, too.
You may also be interested in functional-data-analysis, which deals with entire curves as data, instead of single plots. There should be some ideas on summarizing such data. One good reference for such summaries is Hyndman & Shang, "Rainbow Plots, Bagplots, and Boxplots for Functional Data", J Comp Graph Stat, 2008. You might be able to take ideas on graphing summaries of curves and turn them into calculating numerical summaries.
A: There are several different ways you can achieve smaller sizes. Your data seems to have large runs of small changes.


*

*You could also try doing your polynomial fit, and using single float precision.

*Write the first value out using 8 bits, than encode all others using a fixed-size 4-bit delta encoding; due to size changes this unfortunately menas that you can only capture +/-7 in terms of value. A variant on this would be that if the value is +/-7, that you then encode the rest of the delta in a subsequent value. Another variant would be to write out the sign of the delta using 1 bit and then using a VInt style encoding for smaller number of bits (e.g. outputing 1 or 2 bits in each shortend-VInt).

*Encode your data as a series of sequences. There can be two forms of sequences, one would be raw, the other would write out an average value (8 bits) and delta's (3 or 4 bits depending on another 1 bit output). Then there would be an indicator of length of sequence, then the encoding of the sequence itself.


Of course, if you want to get it much smaller you can use LZ compression, Huffman / Range encoding etc.
