Compression threshold analysis of binary decision diagrams

• US 8,838,523 B2
• Filed: 09/23/2011
• Issued: 09/16/2014
• Est. Priority Date: 09/23/2011
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Stergiou, Stergios, Jain, Jawahar
• Primary Examiner(s): Chen, Alan
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US13/242,095
• Publication Number:
  US 20130080382A1
• Time in Patent Office: 1,089 Days
• Field of Search: 706/59
• US Class Current: 706/59
• CPC Class Codes: G16H 40/67 for remote operation
• CPC Class Codes: G16H 50/20 for computer-aided diagnosis, e.g. based on medical expert systems
• CPC Class Codes: G16H 50/30 for calculating health indices; for individual health risk assessment
• CPC Class Codes: G16H 50/50 for simulation or modelling of medical disorders
• CPC Class Codes: G16H 50/70 for mining of medical data, e.g. analysing previous cases of other patients

Abstract

In particular embodiments, a method includes receiving data sets, constructing a first binary decision diagram (BDD) representing the data sets, iteratively adding data from the data sets to the first BDD until a compression rate of the first BDD reaches a threshold compression rate, constructing a second BDD representing data from the data sets received after the compression rate of the first BDD equals a threshold compression rate, and iteratively adding data from the data sets to the second BDD.

Claims

1. A method comprising:

by one or more computing devices,

constructing a binary decision diagram (BDD) for representing one or more sets of data, wherein the BDD comprises one or more nodes, and each of the one or more nodes is encoded using n bits;

while each of the one or more nodes is encoded using n bits, iteratively;

adding data from the one or more sets of data to the BDD;

compressing the BDD; and

determining a compression rate of the BDD; and

if the compression rate of the BDD drops below a first threshold, then encoding each of the one or more nodes of the BDD using n+d bits, wherein d≧

1.

2. The method of claim 1, wherein:

the BDD comprises one or more 0 edges and one or more 1 edges;

each of the one or more 0 edges and one or more 1 edges is encoded using k bits; and

the first threshold is when a number of nodes in the BDD is less than or equal to 2^k−

1.

3. The method of claim 1, wherein n=6 and d=1.

4. The method of claim 1, further comprising:

while each of the one or more nodes is encoded using n+d bits, iteratively;

adding data from the one or more sets of data to the BDD;

compressing the BDD; and

determining the compression rate of the BDD; and

if the compression rate of the BDD drops below a second threshold, then encoding each of the one or more nodes of the BDD using n+2d bits.

5. The method of claim 1, further comprising optimizing and storing the BDD.

6. The method of claim 1, wherein the one or more sets of data are sensor data from one or more sensors.

7. The method of claim 6, wherein at least one of the one or more sensors is affixed to a person'"'"'s body.

8. An apparatus comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to;

construct a binary decision diagram (BDD) for representing one or more sets of data, wherein the BDD comprises one or more nodes, and each of the one or more nodes is encoded using n bits;

while each of the one or more nodes is encoded using n bits, iteratively;

add data from the one or more sets of data to the BDD;

compress the BDD; and

determine a compression rate of the BDD; and

if the compression rate of the BDD drops below a first threshold, then encode each of the one or more nodes of the BDD using n+d bits, wherein d≧

1.

9. The apparatus of claim 8, wherein:

the BDD comprises one or more 0 edges and one or more 1 edges;

each of the one or more 0 edges and one or more 1 edges is encoded using k bits; and

the first threshold is when a number of nodes in the BDD is less than or equal to 2^k−

1.

10. The apparatus of claim 8, wherein n=6 and d=1.

11. The apparatus of claim 8, wherein the processors are further operable when executing the instructions to:

while each of the one or more nodes is encoded using n+d bits, iteratively;

add data from the one or more sets of data to the BDD;

compress the BDD; and

determine the compression rate of the BDD; and

if the compression rate of the BDD drops below a second threshold, then encode each of the one or more nodes of the BDD using n+2d bits.

12. The apparatus of claim 8, wherein the processors are further operable when executing the instructions to optimize and storing the BDD.

13. The apparatus of claim 8, wherein the one or more sets of data are sensor data from one or more sensors.

14. The apparatus of claim 13, wherein at least one of the one or more sensors is affixed to a person'"'"'s body.

15. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

construct a binary decision diagram (BDD) for representing one or more sets of data, wherein the BDD comprises one or more nodes, and each of the one or more nodes is encoded using n bits;

while each of the one or more nodes is encoded using n bits, iteratively;

add data from the one or more sets of data to the BDD;

compress the BDD; and

determine a compression rate of the BDD; and

if the compression rate of the BDD drops below a first threshold, then encode each of the one or more nodes of the BDD using n+d bits, wherein d≧

1.

16. The media of claim 15, wherein:

the BDD comprises one or more 0 edges and one or more 1 edges;

each of the one or more 0 edges and one or more 1 edges is encoded using k bits; and

the first threshold is when a number of nodes in the BDD is less than or equal to 2^k−

1.

17. The media of claim 15, wherein n=6 and d=1.

18. The media of claim 15, wherein the software is further operable when executed to:

while each of the one or more nodes is encoded using n+d bits, iteratively;

add data from the one or more sets of data to the BDD;

compress the BDD; and

determine the compression rate of the BDD; and

if the compression rate of the BDD drops below a second threshold, then encode each of the one or more nodes of the BDD using n+2d bits.

19. The media of claim 15, wherein the software is further operable when executed to optimize and storing the BDD.

20. The media of claim 15, wherein the one or more sets of data are sensor data from one or more sensors.

21. The media of claim 20, wherein at least one of the one or more sensors is affixed to a person'"'"'s body.

22. A system comprising:

means for constructing a binary decision diagram (BDD) for representing one or more sets of data, wherein the BDD comprises one or more nodes, and each of the one or more nodes is encoded using n bits;

while each of the one or more nodes is encoded using n bits, means for iteratively;

adding data from the one or more sets of data to the BDD;

compressing the BDD; and

determining a compression rate of the BDD; and

if the compression rate of the BDD drops below a first threshold, then means for encoding each of the one or more nodes of the BDD using n+d bits, wherein d≧

1.