Parameterized lossy compression of order-independent data
Drew Colthorp, Gregory S. Wolffe · 2007
When dealing with extremely large quantities of data, it is sometimes necessary to make concessions in order to compress the data to a manageable size, a technique known as lossy compression. One example of such a concession is perfect knowledge of the order in which each data element was recorded. When sampling a random variable, it is often the case that the values measured are more important than the order in which they appear. We have designed a lossy compression scheme that capitalizes on this fact by representing the order in which a sequence of values was measured with less precision than the values themselves. That is, the compressed data is very accurate and efficiently compressed when order is disregarded. Our algorithm works by encoding the measured values as a non-decreasing sequence and their order of appearance as indices referencing contiguous subsequences or slices of the value list. By changing the criteria used to determine a slice, the recorded order may be made more or less accurate, increasing or decreasing compression ratios respectively. Moreover, values in special ranges can be treated specially; for instance, statistical outliers might be represented exactly, whereas mundane values might be recorded with less precision.