COMBINED-MODEL DATA COMPRESSION

• US 20130282639A1
• Filed: 06/20/2013
• Published: 10/24/2013
• Est. Priority Date: 04/13/2010
• Status: Active Grant

• Current Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Potkonjak, Miodrag
• Granted Patent: US 8,868,476 B2
• Time in Patent Office: Days
• US Class Current: 706/46
• 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, the method comprising:

receiving data comprising indications of a signal;

deriving, using at least a first prediction model and a second prediction model, a combined prediction model by operating the first prediction model on a first subset of the data and operating the second prediction model on a second subset of the data, wherein the first subset of data contains data also in the second subset of the data;

predicting a future value for the signal using the combined prediction model;

applying a function configured to determine a distinction between the predicted future value for the signal and an actual value for the signal; and

compressing the data based at least in part on the determined distinction.

2. The method of claim 1, further comprising:

pre-processing the received data to increase its suitability for compression or prediction of other samples, the pre-processing using resampling, requantization, time shifting, transformations, smoothing or other signal processing or statistical techniques.

3. The method of claim 2, further comprising:

measuring an effectiveness of pre-processing using an entropy of a probability mass function corresponding to the pre-processed data.

4. The method of claim 1 wherein the deriving includes executing parametric statistical processing of a probability mass function.

5. The method of claim 1 wherein the deriving includes executing non-parametric statistical processing of a probability mass function.

6. The method of claim 1 wherein the function is applied using a maximum likelihood expectation procedure.

7. The method of claim 1 wherein the future value is a first future value and at least one of the deriving or the predicting is performed a second time to produce a second future value different from the first future value.

8. The method of claim 1 wherein the first subset contains at least half of the data in the second subset.

9. The method of claim 1 wherein the first subset contains at least some data that is different from the data in the second subset.

10. The method of claim 1 wherein the combined prediction model is derived using a set of models comprising at least the first prediction model and the second prediction, and wherein deriving the combined prediction model comprises:

applying a first ordering of the set of models to the signal to obtain a first predicted future value;

applying a second ordering of the set of models to the signal to obtain a second predicted future value;

determining a first effectiveness of the first ordering based at least in part on the first predicted future value;

determining a second effectiveness of the second ordering based at least in part on the second predicted future value;

determining whether the first effectiveness is greater than the second effectiveness;

in response to determining that the first effectiveness is greater than the second effectiveness, selecting the first ordering as the order in which the set of models will be applied; and

in response to determining that the first effectiveness is not greater than the second effectiveness, selecting the second ordering as the order in which the set of models will be applied.

11. A computer-readable storage medium storing instructions that, when executed by a computing device, cause the computing device to perform operations for compressing data, the operations comprising:

shifting or re-sampling one or more signals corresponding to data received from one or more sources;

formulating a combined prediction model based at least in part on two different models, each model operating on at least two subsets of the received data, wherein at least one subset of the at least two subsets contains data in at least one other subset of the at least two subsets;

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

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

compressing the received data using at least a value calculated by the function.

12. The computer-readable storage medium of claim 11, the operations further comprising:

using a probability mass function or joint probability mass function to determine a suitability of the one or more signals for compression.

13. The computer-readable storage medium of claim 12 wherein parametric statistical models are used to analyze the suitability of the shifted or re-sampled one or more signals.

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 11 wherein the compressing the received data comprises ordering compression of samples of each of the one or more signals based on a model uncertainty measure for that sample.

16. The computer-readable storage medium of claim 11, the operations further comprising:

applying a first ordering of the two different models to the one or more shifted or re-sampled signals to obtain a first predicted future value;

applying a second ordering, different from the first ordering, of the two different models to the one or more shifted or re-sampled signals to obtain a second predicted future value;

comparing an effectiveness of the first ordering to an effectiveness of the second ordering at least in part by weighing an accuracy of the first predicted future value against an accuracy of the second predicted future value; and

selecting an ordering for applying models to signals based at least in part on results of the comparing.

17. The computer-readable storage medium of claim 11, the operations further comprising:

determining data values, from two or more of the one or more signals, synchronously.

18. The computer-readable storage medium of claim 11 wherein the at least one subset that contains data in the at least one other subset contains at least half the data in the at least one other subset.

19. The computer-readable storage medium of claim 11 wherein the at least one subset that contains data in the at least one other subset contains at least some data not in the at least one other subset.

20. The computer-readable storage medium of claim 11 wherein at least some of the operations of shifting, formulating, predicting and implementing are applied iteratively to compress the received data.

21. A system, including one or more processors and memory, for compressing data, the system comprising:

means for receiving data comprising one or more signals;

means for creating a prediction model using at least two different models;

means for selecting a subset of the models for sample prediction;

means for determining an order in which the selected subset of models will be applied to the data;

means for formulating future values at least in part by applying the selected subset of models in the determined order;

means for applying a function that has as parameters at least (1) the predicted future values for the data and (2) measured values corresponding to the predicted future values for the data; and

means for compressing the data based at least in part on values calculated by the function.

22. The system of claim 21 wherein the selected subset of models comprises at least a first model and a second model different from the first model, and wherein the first model is applied to a portion of the data that overlaps at least half of the data the second model is applied to.

23. The system of claim 21 wherein the means for determining the order in which the selected subset of models will be applied comprises:

means for applying a first ordering of the selected subset of models to the one or more signals to obtain a first predicted future value;

means for applying a second ordering of the selected subset of models to the one or more signals to obtain a second predicted future value;

means for determining a first effectiveness of the first ordering based at least in part on the first predicted future value;

means for determining a second effectiveness of the second ordering based at least in part on the second predicted future value;

means for determining whether the first effectiveness is greater than the second effectiveness;

means for, in response to determining that the first effectiveness is greater than the second effectiveness, selecting the first ordering as the order in which the selected subset of models will be applied; and

means for, in response to determining that the first effectiveness is not greater than the second effectiveness, selecting the second ordering as the order in which the selected subset of models will be applied.

24. The system of claim 21 wherein the selected subset of models comprises at least a first model and a second model different from the first model, and wherein the first model operates on a portion of the data that includes some data not in the data operated on by the second model.