SEMANTIC COMPRESSION

• US 20120265738A1
• Filed: 04/13/2010
• Published: 10/18/2012
• 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: Beckmann, Nathan, Potkonjak, Miodrag
• Granted Patent: US 9,858,393 B2
• Time in Patent Office: Days
• US Class Current: 707/693
• CPC Class Codes: G16H 50/20 for computer-aided diagnosis, e.g. based on medical expert systems
• CPC Class Codes: G16H 50/70 for mining of medical data, e.g. analysing previous cases of other patients
• CPC Class Codes: G16H 50/80 for detecting, monitoring or modelling epidemics or pandemics, e.g. flu
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass
• 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

Technology for semantic compression is disclosed. In various embodiments, the technology receives data that represents one or more physical attributes sensed by one or more sensors; employs at least one pattern or statistical feature to identify a first region and a second region in the received data; computes a first utility and a first relevant feature for the first region, and a second utility and a second relevant feature for the second region; and identifies based on at least the first utility and the second utility a first compression method to apply to the first region and a second compression method to apply to the second region wherein the first and the second compression methods have different compression rates, different feature preservation characteristics, or both.

Claims

1. A method performed by a computing device for compressing data, comprising:

receiving data that represents one or more physical attributes sensed by one or more sensors;

identifying a first region and a second region in the received data by employing at least one pattern or statistical feature;

computing a first utility and a first relevant feature for the first region, and a second utility and a second relevant feature for the second region; and

identifying based on at least the first utility and the second utility a first compression method to apply to the first region and a second compression method to apply to the second region wherein the first and the second compression methods have different compression rates or different feature preservation characteristics.

2. The method of claim 1 wherein identifying the first and second regions comprises:

characterizing a utility of different signal segments;

identifying a unique combination of features in each segment; and

deriving one or more algorithms for automatic feature identification using a pattern matching technique. statistical technique, or both a pattern matching technique and a statistical technique.

3. The method of claim 2 wherein the characterizing comprises analyzing one or more sets of diagnosis results.

4. The method of claim 2 wherein an identification of the unique combination is received.

5. The method of claim 2 wherein at least one of the analyzing or the deriving comprises employing one or more dynamic programming pattern matching or statistical techniques.

6. The method of claim 2 wherein the identifying comprises employing a statistical technique.

7. The method of claim 2 wherein the deriving comprises employing a combinatorial or numerical pattern matching technique.

8. The method of claim 2 further comprising repeating the characterizing, identifying, and deriving until a resulting model does not pass a learn and test criterion.

9. The method of claim 2 further comprising repeating the characterizing, identifying, and deriving until a resulting model does not pass a resubstitution test.

10. The method of claim 9 wherein the resubstitution test is a jackknife resubstitution test.

11. The method of claim 1 wherein at least one of the first and the second compression methods is selected by comparing at least one of the different compression rates or different feature preservation characteristics after applying the compression methods to two or more sets of data.

12. The method of claim 11 further comprising building a statistical model based on the application of the compression methods to the two or more sets of data and employing the statistical model to select the compression methods.

13. The method of claim 1 wherein the data is preprocessed using one or more signal processing techniques.

14. The method of claim 13 wherein the signal processing technique is at least one of a linear transformation or a difference-based technique.

15. The method of claim 1 wherein the first utility is higher than the second utility and the first compression method is lossless and the second compression method is lossy.

16. The method of claim 1 further comprising iteratively identifying additional regions in the data until a stopping criterion is satisfied.

17. The method of claim 16 wherein the stopping criterion is at least one of a running time of the overall procedure or a lack of compression rate improvement.

18. The method of claim 1 wherein identifying a compression method for each segment comprises applying a dynamic programming technique.

19. The method of claim 1 further comprising:

receiving data from one or more signals corresponding to one or more sensors;

selecting one or more signals for semantic compression;

partitioning the selected signals into one or more regions; and

selecting a compression method for each region.

20. The method of claim 1 wherein the identifying of a compression method for the first region is controlled by specifying the first utility using a joint utility function wherein the joint utility function indicates a relative utility of the first region if the second utility of the second region has a particular value.

21. The method of claim 20 wherein the first region relates to a first signal from a first sensor and the second region relates to a second region from a second sensor.

22. The method of claim 20 wherein the utility and the joint utility functions are defined using probability density functions.

23. The method of claim 22 wherein utilities are combined using maximum likelihood expectation (MLE), minimal mean-square expected error (MSEE), or multiple explanation variable statistical models.

24. The method of claim 1 further comprising receiving an iteratively updated patient diagnosis wherein the first utility is computed based on a previous patient diagnosis and the second utility is computed based on a current patient diagnosis.

25. The method of claim 1 further comprising receiving external data and modifying the updated patient diagnosis based on the external data.

26. The method of claim 25 wherein the external data is at least one of a geolocation, physical time, or a recent activity of the patient.

27. The method of claim 25 wherein the external data is a statistical or a numerical quantification of a current or recent epidemic.

28. A computer-readable storage medium storing computer-executable instructions that, when executed, cause a computing system to perform a method for compressing data, comprising:

receiving data that represents one or more physical attributes sensed by one or more sensors;

identifying a first region and a second region in the received data by employing at least one pattern or statistical feature;

computing a first utility and a first relevant feature for the first region, and a second utility and a second relevant feature for the second region; and

identifying based on at least the first utility and the second utility a first compression method to apply to the first region and a second compression method to apply to the second region wherein the first and the second compression methods have different compression rates or different feature preservation characteristics.

29. A system for compressing data, comprising:

a component configured to receive data that represents one or more physical attributes sensed by one or more sensors;

a component configured employ at least one pattern or statistical feature to identify a first region and a second region in the received data;

a component configured to compute a first utility and a first relevant feature for the first region, and a second utility and a second relevant feature for the second region; and

a component configured to identify based on at least the first utility and the second utility a first compression method to apply to the first region and a second compression method to apply to the second region wherein the first and the second compression methods have different compression rates or different feature preservation characteristics.