Enhanced data compression for sparse multidimensional ordered series data

• US 9,859,917 B2
• Filed: 02/13/2017
• Issued: 01/02/2018
• Est. Priority Date: 10/07/2014
• Status: Active Grant

• Current Assignee: Protein Metrics LLC
• Original Assignee: Protein Metrics Inc. (Insightful Science LLC)
• Inventors: Kletter, Doron
• Primary Examiner(s): NGUYEN, LINH V
• Application Number:
  US15/431,381
• Publication Number:
  US 20170155403A1
• Time in Patent Office: 323 Days
• Field of Search: 341 51, 341 65, 341 67, 341 87, 341106, 341107
• CPC Class Codes: H03M 7/24 Conversion to or from floating-point codes
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

Disclosed are methods and systems for significantly compressing sparse multidimensional ordered series data comprised of indexed data sets, wherein each data set comprises an index, a first variable and a second variable. The methods and systems are particularly suited for compression of data recorded in double precision floating point format.

Claims

1. A computer-implemented method of compressing a sparse multidimensional ordered series of data, the method comprising:

a) receiving the sparse multidimensional ordered series data, wherein the data comprise indexed data sets, each indexed data set comprising an index (n), a first variable (x_n), and a second variable (y_n), wherein the first variable and second variable are paired observations;

b) defining a predictor that calculates each first variable (x_n) as a function of the index (n);

c) assigning an amplitude code word to each y_n;

d) calculating a hop offset value (Δ

_n) for each y_n;

e) assigning a hop code word to each Δ

_n based on the value of the Δ

_n; and

f) generating a compressed output, said compressed output comprising;

i) a decoder legend comprising;

a description of the predictor;

a reverse amplitude code word dictionary associated with y_n; and

a reverse hop code word dictionary associated with Δ

_n; and

ii) code word data comprising an amplitude code word and a hop code word for each y_n and each Δ

_n.

2. The method of claim 1, wherein the data comprise indexed data sets of mass spectrometry data.

3. The method of claim 1, wherein the data comprises indexed data sets of sensor data collected from one or more:

camera, velocity detector, accelerometer, location positioning system, radiation detector, x-ray detector.

4. The method of claim 1, wherein the data comprises indexed data sets of astronomy data, biology data or chemical data.

5. The method of claim 1, wherein the sparse multidimensional ordered series data is in double precision floating point format.

6. The method of claim 1, wherein the predictor is a global predictor function.

7. The method of claim 6, wherein the global predictor is an n^th order polynomial function.

8. The method of claim 7, wherein the function is g(n)=a₀+a₁*n+a₂*n²+a₃*n³.

9. The method of claim 1, wherein the predictor is a piecewise predictor.

10. The method of claim 1, wherein the predictor is a local predictor.

11. The method of claim 1, wherein the predictor further comprises an error correction mechanism.

12. The method of claim 1, wherein assigning an amplitude code word to each y_n comprises:

i) generating a hash table for amplitude values;

ii) looking up each of the second variable (y_n) value in turn,

wherein if the y_n value is not previously seen, then the y_n value is added to a list of amplitude values and an associated frequency occurrence is set to one, and

wherein if the y_n is already present on the list of amplitude values, then the associated frequency occurrence is incremented by one;

iii) sorting the list of amplitude values by their associated frequency occurrence;

iv) assigning a unique amplitude code word to each unique amplitude value in the list of amplitude values, wherein the shortest code words are assigned to the most frequently occurring amplitude values.

13. The method of claim 12, wherein any second variable (y_n) value less than or equal to a baseline threshold is skipped.

14. The method of claim 1, wherein the sparse multidimensional ordered series data describe a non-uniform multi-modal distribution of hop Δ

_n ranges, where certain hop ranges that are frequently and considerably more likely to occur are interspaced with other hop ranges that are much less likely to occur.

15. The method of claim 14, wherein the hop offset values are comprised of a discrete set of observable amplitude ranges interspaced with intervals of amplitude ranges that are not observed in the data.

16. The method of claim 1, wherein calculating a hop offset value (Δ

_n) for each y_n comprises;

i) identifying an initial hop offset value (Δ

₀) and entering the Δ

₀ into a previous register as a previous peak location;

ii) feeding each index (n) into the previous register subtracting the previous peak location from the index (n) to calculate the hop offset value (Δ

_n) and then replacing the previous peak location with the index (n);

iii) repeating step ii) for each index (n) in the sparse multidimensional ordered series data.

17. The method of claim 1, wherein calculating a hop offset value (Δ

_n) for each y_n comprises;

i) identifying an initial hop offset value (Δ

₀) and entering the Δ

₀ into a previous register as a previous peak location;

ii) feeding each first variable (x_n) value into the previous register subtracting the previous peak location from the first variable (x_n) value to calculate the hop offset value (Δ

_n) and then replacing the previous peak location with the first variable (x_n) value;

iii) repeating step ii) for each first variable (x_n) value in the sparse multidimensional ordered series data.

18. The method of claim 1, wherein assigning a hop code word to each Δ

_n based on the value and frequency of the Δ

_n comprises;

i) generating a hash table for hop offset values;

ii) looking up each hop offset value (Δ

_n) value in turn,

wherein if the Δ

_n value is not previously seen, then the Δ

_n value is added to a list of hop values and an associated frequency occurrence is set to one, and

wherein if the Δ

_n is already present on the list of hop values, then the associated frequency occurrence is incremented by one;

iii) sorting the list of hop values by their associated frequency occurrence;

iv) assigning a unique hop code word to each unique hop value in the list of hop values, wherein the shortest code words are assigned to the most frequently occurring hop values.

19. A non-transitory computer readable medium having instructions for compressing a sparse multidimensional ordered series of data stored therein, which, when executed by a processor, cause the processor to:

receive the sparse multidimensional ordered series data, wherein the data comprise indexed data sets, each indexed data set comprising an index (n), a first variable (x_n) and a second variable (y_n), wherein the first variable and second variable are paired observations;

define a predictor that calculates each first variable (x_n) as a function of the index (n);

assign an amplitude code word to each y_n;

calculate a hop offset value (Δ

_n) for each y_n; and

generate a compressed output, said compressed output comprising;

a decoder legend comprising;

a description of the predictor;

a reverse amplitude code word dictionary associated with y_n; and

a reverse hop code word dictionary associated with Δ

_n; and

code word data comprising an amplitude code word and a hop code word for each y_n and each Δ

_n.