Combined-model data compression

• US 8,868,476 B2
• Filed: 06/20/2013
• Issued: 10/21/2014
• 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
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Misir, Dave
• Application Number:
  US13/923,250
• Publication Number:
  US 20130282639A1
• Time in Patent Office: 488 Days
• Field of Search: 706/21, 706/46
• 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, the method comprising:

receiving data comprising indications of a signal;

creating a first subset of the data and a second subset of the data different from the first subset of the data, wherein the first subset of the data overlaps with the second subset of the data;

deriving, using at least a first prediction model and a second prediction model, a combined prediction model by operating the first prediction model on the first subset of the data, and contemporaneously operating the second prediction model on 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 sample prediction, 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 model, 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. The method of claim 1, wherein the signal represents a sequence of data items and wherein the first subset of data overlaps the second subset of data by:

the first subset of data containing both a first data item from a first point in the sequence and a third data item from a third point in the sequence; and

the second subset of data containing a second data item from a second point in the sequence;

wherein the first point in the sequence is prior to the second point in the sequence, and the second point in the sequence is prior to the third point in the sequence.

12. The method of claim 1, wherein operating the first prediction model on the first subset of the data and contemporaneously operating the second prediction model on the second subset of the data comprises:

operating the first prediction model on the first subset of the data during a particular time period consisting of time prior to predicting the future value for the signal using the combined prediction model; and

operating the second prediction model on the second subset of the data during the particular time period consisting of time prior to predicting the future value for the signal using the combined prediction model.

13. The method of claim 12, wherein the particular time period is entirely after receiving data comprising indications of a signal.

14. The method of claim 1 wherein the first subset of data overlaps the second subset of data by the first subset of data containing data also in the second subset of the data.

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

obtaining a first subset of the data;

shifting or re-sampling one or more signals that correspond to the data to obtain a second subset of the data different from the first subset of the data, wherein the first subset of the data overlaps with the second subset of the data;

formulating a combined prediction model based at least in part on a first prediction model and a second prediction model different from the first prediction model, the first prediction model operating on at least the first subset of the data and the second prediction model operating on at least the second subset of the data, wherein the first prediction model operates on the first subset of the data contemporaneously with the second prediction model operating on the second subset of the data;

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.

16. The computer-readable medium of claim 15, 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.

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

18. The computer-readable medium of claim 17, 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.

19. The computer-readable medium of claim 15, 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.

20. The computer-readable medium of claim 15, 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.

21. The computer-readable medium of claim 15, the operations further comprising:

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

22. The computer-readable medium of claim 15, 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.

23. The computer-readable medium of claim 15, 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.

24. The computer-readable medium of claim 15, wherein at least some of the operations of shifting, formulating, predicting and applying are performed iteratively to compress the received data.

25. The computer-readable medium of claim 15, wherein the data is representable as a sequence of data items and wherein the first subset of data overlaps the second subset of data by:

the first subset of data containing both a first data item from a first point in the sequence and a third data item from a third point in the sequence; and

the second subset of data containing a second data item from a second point in the sequence;

wherein the first point in the sequence is prior to the second point in the sequence, and the second point in the sequence is prior to the third point in the sequence.

26. The computer-readable medium of claim 15, wherein the first prediction model and second prediction model operate contemporaneously on the first subset of the data and the second subset of the data by:

operating the first prediction model on the first subset of the data during a particular time period consisting of time prior to predicting a future value for the received data using the combined prediction model, and

operating the second prediction model on the second subset of the data during the particular time period consisting of time prior to predicting a future value for the received data using the combined prediction model.

27. The computer-readable medium of claim 26, wherein the particular time period is entirely after obtaining a first subset of the data.

28. The computer-readable medium of claim 15, wherein the first subset of data overlaps the second subset of data by the first subset of data containing data also in the second subset of the data.

29. A system for compressing data, the system comprising:

one or more processors;

memory;

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 a first subset of the data and a second subset of the data different from the first subset of the data, wherein the first subset of the data overlaps with the second subset of the data, and wherein the order indicates that a first one of the at least two of the selected subsets of models operates on the first subset of the data contemporaneously with a second one of the at least two of the selected subsets of models operating on the second subset of the data;

means for formulating predicted 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.

30. The system of claim 29, 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 the first subset of the data, the second model is applied to the second subset of the data, and the first subset of the data overlaps at least half of the data in the second subset of the data.

31. The system of claim 29, 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.

32. The system of claim 29, 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.

33. The system of claim 29, wherein the one or more signals represent a sequence of data items, and wherein the first subset of data overlaps the second subset of data by:

the first subset of data containing both a first data item from a first point in the sequence and a third data item from a third point in the sequence; and

the second subset of data containing a second data item from a second point in the sequence;

wherein the first point in the sequence is prior to the second point in the sequence, and the second point in the sequence is prior to the third point in the sequence.

34. The system of claim 29, wherein the order indicates that at least two of the selected subsets of models operate contemporaneously on the first subset of the data and on the second subset of the data by:

operating a first prediction model, of the selected subset of models, on the first subset of the data during a particular time period consisting of time prior to formulating predicted future values; and

operating a second prediction model different from the first prediction model, of the selected subset of models, on the second subset of the data during the particular time period consisting of time prior to formulating predicted future values.

35. The system of claim 34, wherein the particular time period is entirely after selecting a subset of the models for sample prediction.

36. The system of claim 29, wherein the first subset of the data overlaps the second subset of the data by the first subset of the data containing data also in the second subset of the data.