Combined-model data compression

• US 8,473,438 B2
• Filed: 04/13/2010
• Issued: 06/25/2013
• Est. Priority Date: 04/13/2010
• Status: Expired due to Fees

• Current Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Potkonjak, Miodrag
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Misir, Dave
• Application Number:
  US12/996,010
• Publication Number:
  US 20110251986A1
• Time in Patent Office: 1,169 Days
• Field of Search: None
• US Class Current: 706/21
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• 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

Abstract

Data compression technology (“the technology”) is disclosed that can employ two or more prediction models contemporaneously. The technology receives data from one or more sources; shifts or re-sample one of more corresponding signals; creates a prediction model of uncompressed samples using at least two different individual or composite models; selects a subset of the models for prediction of samples; determines an order in which signals will be compressed; formulates a combined predictions model using the selected subset of models; predicts a future value for the data using the combined compression model; defines a function that has as parameters at least the predicted future values for the data and actual values; selects a compression method for the values of the function; and compresses the data using at least the predicted value of the function.

Claims

1. A method performed by a computing device having a processor and memory for compressing data, comprising:

receiving data from one or more sources;

optionally pre-processing the data;

deriving at least two different prediction models using the data;

creating a combined prediction model of uncompressed samples, the samples created using the at least two different prediction models operating on at least two subsets of the data, wherein at least one subset contains data in at least one other subset;

predicting a value for the data using the combined prediction model;

creating a function that has as parameters at least the predicted value for the data and an actual value;

selecting a compression method for the function; and

compressing the data at least partly using values calculated by the function.

2. The method of claim 1 further comprising pre-processing the received data to increase its suitability for compression or prediction of other samples from the same or correlated sources using resampling, requantization, time shifting, transformations, smoothing or other signal processing and/or statistical techniques.

3. The method of claim 2 further comprising measuring an effectiveness of pre-processing using an entropy of a corresponding probability mass function (PMF).

4. The method of claim 1 wherein the deriving includes executing parametric or non-parametric statistical processing of a probability mass function (PMF) for pairs comprising a data measurement and a predicted value.

5. The method of claim 1 wherein the function is created using a maximum likelihood expectation (MLE) procedure.

6. The method of claim 1 wherein creating the function includes finding a difference between the predicted and the actual value.

7. The method of claim 1 wherein the selecting includes using statistical properties of the created function and statistical properties of each of a plurality of compression methods.

8. The method of claim 1 wherein at least one of the receiving, optionally pre-processing, deriving, creating the combined prediction model, and predicting is performed in at least two different ways to create two functions.

22. The method of claim 1 wherein the at least one subset which contains data in at least one other subset contains at least half the data in the at least one other subset.

9. A computer-readable storage medium storing computer-executable instructions that, when executed, perform a method for compressing data, the method comprising:

receiving data from one or more sources;

shifting or re-sampling one or more signals corresponding to the data;

creating a prediction model of uncompressed samples, the samples created using at least two different individual or composite models operating on at least two subsets of the data, wherein at least one subset contains data in at least one other subset;

selecting a subset of the models for sample prediction;

determining an order in which signals will be compressed;

formulating a combined predictions model using the selected subset of models;

predicting a future value for the data using the combined predictions model;

defining a function that has as parameters at least predicted future values for the data and actual values;

selecting a compression method for values resulting from the function; and

compressing the data using at least calculated values of the function.

10. The computer-readable storage medium of claim 9 wherein the method further comprises pre-processing the received data to increase their suitability for compression or prediction of other samples from the same or correlated sources using resampling, requantization, smoothing or other signal processing or statistical techniques.

11. The computer-readable storage medium of claim 9 wherein the method further comprises relative time shifting of the one or more signals so that the one or more signals predict more accurately.

12. The computer-readable storage medium of claim 9 wherein a probability mass function (PMF) and joint PMFs are used for analyzing suitability of the signal for compression and for prediction of the one or more signals or for prediction of other correlated signals.

13. The computer-readable storage medium of claim 12 wherein parametric and non-parametric statistical models are used to analyze suitability.

14. The computer-readable storage medium of claim 13 wherein at least one of the statistical models is one or more of classification and regression trees (CART), multivariate adaptive regression splines (MARS), or neural networks.

15. The computer-readable storage medium of claim 9 wherein the method further comprises processing a PMF and joint PMFs using smoothing, regression, or other parametric or non-parametric statistical techniques.

16. The computer-readable storage medium of claim 9 wherein a set of PMFs or joint PMFs or other indicators of suitability for compression are selected in such a way that for each of the one or more signals there is at least one path from a signal where each signal that is in the path can be compressed.

17. The computer-readable storage medium of claim 9 wherein the compressing the data comprises ordering the compression of samples of each signal in such a way that signals that have a high function of low entropy as indicated by its PMF and low joint PMF entropies for the predicted signals are processed first.

18. The computer-readable storage medium of claim 9 wherein the method further comprises attempting several different orderings and selecting the most effective ordering.

19. The computer-readable storage medium of claim 9 wherein data values are determined synchronously from two or more signal streams.

20. The computer-readable storage medium of claim 9 wherein data values are determined in a staggered manner from two or more signal streams.

23. The computer-readable storage medium of claim 9 wherein the at least one subset which contains data in at least one other subset contains at least half the data in the at least one other subset.

21. A system for compressing data comprising:

a processor and memory;

a component configured to receive data from one or more sources;

a component configured to shift or re-sample one or more signals corresponding to the data;

a component configured to create a prediction model of uncompressed samples, the samples created using at least two different individual or composite models operating on at least two subsets of the data, wherein at least one subset contains data in at least one other subset;

a component configured to select a subset of the models for sample prediction;

a component configured to determine an order in which the one or more signals will be compressed;

a component configured to formulate a combined predictions model using the selected subset of models;

a component configured to predict a future value for the data using the combined predictions model;

a component configured to define a function that has as parameters at least predicted future values for the data and actual values;

a component configured to select a compression method for values resulting from the function; and

a component configured to compress the data using at least one value calculated by the function.

24. The system of claim 21 wherein the at least one subset which contains data in at least one other subset contains at least half the data in the at least one other subset.