Combining medical binary decision diagrams to determine data correlations

• US 8,909,592 B2
• Filed: 09/23/2011
• Issued: 12/09/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): Chaki, Kakali
• Assistant Examiner(s): Tran, Mai T
• Application Number:
  US13/241,872
• Publication Number:
  US 20130080381A1
• Time in Patent Office: 1,173 Days
• Field of Search: None
• 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
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass

Abstract

In particular embodiments, a method includes accessing a first binary decision diagram (BDD) representing a data stream from a first sensor and a second BDD representing a data stream from a second sensor, determining whether the first sensor data and the second sensor data correlate by: constructing a third BDD by performing an OR operation between the first and second BDDs, determining sizes of the first, second, and third BDDs, and comparing the third size to the sum of the first size and the second size; where the degree that the first sensor data and the second sensor data correlate is indicated by the amount that the third size is less than the sum of the first size and the second size.

Claims

1. A method comprising:

by one or more computing devices, accessing a first binary decision diagram (BDD) representing a first sensor data from a first sensor and a second BDD representing a second sensor data from a second sensor; and

determining whether the first sensor data and the second sensor data correlate by;

constructing a third BDD by performing an OR operation between the first BDD and the second BDD;

determining a first size of the first BDD, a second size of the second BDD, and a third size of the third BDD; and

comparing the third size to a sum of the first size and the second size;

wherein a degree that the first sensor data and the second sensor data correlate is indicated by an amount that the third size is less than the sum of the first size and the second size.

2. The method of claim 1, further comprising:

if the third size is less than the sum of the first size and the second size, then storing the third BDD and deleting the first BDD and the second BDD; and

if the third size is greater than the sum of the first size and the second size, then storing the first BDD and the second BDD and deleting the third BDD.

3. The method of claim 1, further comprising optimizing the sizes of the first BDD, the second BDD, and the third BDD.

4. The method of claim 1, wherein at least one of the first sensor or the second sensor is affixed to a person'"'"'s body.

5. The method of claim 1, further comprising:

accessing a fourth BDD representing third sensor data from a third sensor;

constructing a fifth BDD by performing an OR operation between the third BDD and the fourth BDD;

determining a fourth size of the fourth BDD and a fifth size of the fifth BDD;

if the fifth size is less than the sum of the third size and the fourth size, then storing the fifth BDD and deleting the third BDD and the fourth BDD; and

if the fifth size is greater than the sum of the third size and the fourth size, then storing the third BDD and the fourth BDD and deleting the fifth BDD.

6. The method of claim 1, further comprising if the first sensor data and the second sensor data correlate, then storing the third BDD and deleting the first BDD and the second BDD.

7. The method of claim 1, further comprising:

accessing a fourth BDD representing third sensor data from a third sensor; and

determining whether the first sensor data, the second sensor data, and the third sensor data correlate, comprising;

constructing a fifth BDD by performing an OR operation between the third BDD and the fourth BDD;

determining a fourth size of the fourth BDD and a fifth size of the fifth BDD; and

if the fifth size is less than a sum of the first size, the second size, and the fourth size, then indicating that the first sensor data, the second sensor data, and the third sensor data correlate.

8. The method of claim 7, further comprising if the fifth size is less than the sum of the first size, the second size, and the fourth size, then determining a degree that the first sensor data, the second sensor data, and the third sensor data correlate by comparing the fifth size to the sum of the first size, the second size, and the third size, wherein the degree that the first sensor data, the second sensor data and, the third sensor data correlate is indicated by an amount that the fifth size is less than the sum of the first size, the second size, and the third size.

9. The method of claim 1, further comprising if the third size is less than the sum of the first size and the second size, then storing the third BDD and deleting the first BDD and the second BDD.

10. The method of claim 1 wherein the first BDD comprises one or more rooted directed acyclic graphs representing a Boolean function, the binary decision diagram comprising a plurality of nodes and a plurality of edges connecting the nodes thereby forming a plurality of paths, each path in the first BDD representing a set of variable assignments setting the represented Boolean function.

11. The method of claim 1 wherein the sizes of the first, second, and third BDDs are measured in bits.

12. The method of claim 1 wherein the sizes of the first, second, and third BDDs are measured in the number of nodes.

13. 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;

access a first binary decision diagram (BDD) representing a first sensor data from a first sensor and a second BDD representing a second sensor data from a second sensor; and

determine whether the first sensor data and the second sensor data correlate by;

construct a third BDD by performing an OR operation between the first BDD and the second BDD;

determine a first size of the first BDD, a second size of the second BDD, and a third size of the third BDD; and

compare the third size to a sum of the first size and the second size;

wherein a degree that the first sensor data and the second sensor data correlate is indicated by an amount that the third size is less than the sum of the first size and the second size.

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

if the third size is less than the sum of the first size and the second size, then store the third BDD and delete the first BDD and the second BDD; and

if the third size is greater than the sum of the first size and the second size, then store the first BDD and the second BDD and delete the third BDD.

15. The apparatus of claim 13, wherein the processors are further operable when executing the instructions to optimize the sizes of the first BDD, the second BDD, and the third BDD.

16. The apparatus of claim 13, wherein at least one of the first sensor or the second sensor is affixed to a person'"'"'s body.

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

access a fourth BDD representing third sensor data from a third sensor;

construct a fifth BDD by performing an OR operation between the third BDD and the fourth BDD;

determine a fourth size of the fourth BDD and a fifth size of the fifth BDD;

if the fifth size is less than the sum of the third size and the fourth size, then store the fifth BDD and delete the third BDD and the fourth BDD; and

if the fifth size is greater than the sum of the third size and the fourth size, then store the third BDD and the fourth BDD and delete the fifth BDD.

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

access a first binary decision diagram (BDD) representing a first sensor data from a first sensor and a second BDD representing a second sensor data from a second sensor; and

determine whether the first sensor data and the second sensor data correlate by;

construct a third BDD by performing an OR operation between the first BDD and the second BDD;

determine a first size of the first BDD, a second size of the second BDD, and a third size of the third BDD; and

compare the third size to a sum of the first size and the second size;

wherein a degree that the first sensor data and the second sensor data correlate is indicated by an amount that the third size is less than the sum of the first size and the second size.

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

if the third size is less than the sum of the first size and the second size, then store the third BDD and delete the first BDD and the second BDD; and

if the third size is greater than the sum of the first size and the second size, then store the first BDD and the second BDD and delete the third BDD.

20. The media of claim 18, wherein the software is further operable when executed to optimize the sizes of the first BDD, the second BDD, and the third BDD.

21. The media of claim 18, wherein at least one of the first sensor or the second sensor is affixed to a person'"'"'s body.

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

access a fourth BDD representing third sensor data from a third sensor;

construct a fifth BDD by performing an OR operation between the third BDD and the fourth BDD;

determine a fourth size of the fourth BDD and a fifth size of the fifth BDD;

if the fifth size is less than the sum of the third size and the fourth size, then store the fifth BDD and delete the third BDD and the fourth BDD; and

if the fifth size is greater than the sum of the third size and the fourth size, then store the third BDD and the fourth BDD and delete the fifth BDD.

23. A system comprising:

means for accessing a first binary decision diagram (BDD) representing a first sensor data from a first sensor and a second BDD representing a second sensor data from a second sensor; and

means for determining whether the first sensor data and the second sensor data correlate by;

means for constructing a third BDD by performing an OR operation between the first BDD and the second BDD;

means for determining a first size of the first BDD, a second size of the second BDD, and a third size of the third BDD; and

means for comparing the third size to a sum of the first size and the second size;

wherein a degree that the first sensor data and the second sensor data correlate is indicated by an amount that the third size is less than the sum of the first size and the second size.

24. A method comprising:

by one or more computing devices, accessing a first binary decision diagram (BDD) representing first sensor data from a first sensor, a second BDD representing second sensor data from a second sensor, and a third BDD representing third sensor data from a third sensor; and

determining whether the first sensor data, the second sensor data, and the third sensor data correlate by;

constructing a fourth BDD by performing an OR operation between the first BDD and the second BDD;

constructing a fifth BDD by performing an OR operation between the first BDD and the third BDD;

constructing a sixth BDD by performing an OR operation between the second BDD and the third BDD;

constructing a seventh BDD by performing an OR operation between the first BDD, the second BDD, and the third BDD;

determining

a first size of the first BDD,

a second size of the second BDD,

a third size of the third BDD,

a fourth size of the fourth BDD,

a fifth size of the fifth BDD,

a sixth size of the sixth BDD,

a seventh size of the seventh BDD,

a sum of the first size and the sixth size,

a sum of the second size and the fifth size,

a sum of third size and the fourth size, and

a sum of the first size, the second size, and the third size; and

comparing the sizes and selecting a smallest size from a group consisting of;

the seventh size;

the sum of the first size and the sixth size,

the sum of the second size and the fifth size,

the sum of third size and the fourth size, and

the sum of the first size, the second size, and the third size;

whether a degree to which the first sensor data, the second sensor data, and the third sensor data are correlated is indicated by an amount that the smallest of the seventh size, the sum of the first size and the sixth size, the sum of the second size and the fifth size, or the sum of the third size and the fourth size, is less than the sum of the first size, the second size, and the third size.

25. The method of claim 24, wherein at least one of the first sensor, the second sensor, or the third sensor is affixed to a person'"'"'s body.