Range queries in binary decision diagrams

• US 8,781,995 B2
• Filed: 09/23/2011
• Issued: 07/15/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): COUGHLAN, PETER D
• Application Number:
  US13/243,158
• Publication Number:
  US 20130080470A1
• Time in Patent Office: 1,026 Days
• US Class Current: 706/62
• CPC Class Codes: G06N 5/00 Computing arrangements using knowledge-based models
• 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

Abstract

In particular embodiments, a method includes receiving a query for data in data sets that are within a specified range, constructing a first binary decision diagram (BDD) representing the specified range, and constructing a third BDD representing the data in the specified range by performing an AND operation between the first BDD and a second BDD representing the data sets.

Claims

1. A method comprising:

by one or more computing devices,

receiving a query for data from one or more data sets of sensor data from one or more sensors, the query being for data that are within a range of a sensor output range, wherein the one or more data sets are represented by a first binary decision diagram (BDD), wherein the first BDD has m layers corresponding, respectively, to m variables;

constructing a second BDD representing the range, wherein the second BDD has n layers corresponding, respectively, to n of the m variables, where in m≧

n, wherein the range has a lower bound and an upper bound, and wherein constructing the second BDD comprises;

constructing a fourth BDD representing a first range from the lower bound of the range to a maximum value from the one or more data sets of sensor data from the one or more sensors;

constructing a fifth BDD representing a second range from the upper bound of the range plus one to the maximum value from the one or more data sets of sensor data from the one or more sensors;

negating the fifth BDD by applying a NOT operation to the fifth BDD; and

constructing the second BDD by performing an AND operation between the fourth BDD and the negated fifth BDD; and

constructing a third BDD representing the data within the range by performing an AND operation between the first BDD and the second BDD.

2. The method of claim 1, wherein the second BDD evaluates to 1 for all values within the range and evaluates to 0 for all values outside the range.

3. The method of claim 1, wherein:

in the first BDD, the top n of the m layers correspond, respectively, to the n of the m variables in the second BDD.

4. The method of claim 1, wherein:

the method further comprising reordering the first BDD so that the top n of the m layers of the first BDD correspond, respectively, to the n of the m variables in the second BDD.

5. The method of claim 1, wherein:

the first BDD has k nodes corresponding to the m variables, each of the m layers having one or more of the k nodes;

the range corresponds to n of the m variables, where m≧

n; and

in the first BDD, j of the k nodes corresponding to the n of the m variables in the range are at the top n of the m layers.

6. The method of claim 1, further comprising displaying the data represented by the third BDD.

7. The method of claim 1, further comprising indicating whether the third BDD is empty.

8. The method of claim 1, wherein the sensor data are time specific.

9. The method of claim 8, wherein the range is a time range.

10. The method of claim 8, wherein

the first BDD has m variables;

i of the m variables correspond to time data associated with the sensor data, where m>

i; and

j of the m variables correspond to sensor data, where m>

j.

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

12. The method of claim 1, wherein:

the second BDD represents a range [a, b], wherein a and b are the lower bound and the upper bound, respectively;

the fourth BDD represents a range [a, max], wherein max is the maximum value from the one or more data sets; and

the fifth BDD represents a range [b+1, max].

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;

receive a query for data from one or more data sets of sensor data from one or more sensors, the query being for data that are within a range of a sensor output range, wherein the one or more data sets are represented by a first binary decision diagram (BDD) , wherein the first BDD has m layers corresponding, respectively, to m variables;

construct a second BDD representing the range, wherein the second BDD has n layers corresponding, respectively, to n of the m variables, where m≧

n, wherein the range has a lower bound and an upper bound, and wherein constructing the second BDD comprises;

constructing a fourth BDD representing a first range from the lower bound of the range to a maximum value from the one or more data sets;

constructing a fifth BDD representing a second range from the upper bound of the range plus one to the maximum value from the one or more data sets;

negating the fifth BDD by applying a NOT operation to the fifth BDD; and

constructing the second BDD by performing an AND operation between the fourth BDD and the negated fifth BDD; and

construct a third BDD representing the data within the range by performing an AND operation between the first BDD and the second BDD.

14. The apparatus of claim 13, wherein the second BDD evaluates to 1 for all values within the range and evaluates to 0 for all values outside the range.

15. The apparatus of claim 13, wherein:

in the first BDD, the top n of the m layers correspond, respectively, to the n of the m variables in the second BDD.

16. The apparatus of claim 13, wherein:

wherein the processors are further operable when executing the instructions to reorder the first BDD so that the top n of the m layers of the first BDD correspond, respectively, to the n of the m variables in the second BDD.

17. The apparatus of claim 13, wherein:

the first BDD has k nodes corresponding to the m variables, each of the m layers having one or more of the k nodes;

the range corresponds to n of the m variables, where m≧

n ; and

in the first BDD, j of the k nodes corresponding to the n of the m variables in the range are at the top n of the m layers.

18. The apparatus of claim 13, wherein the processors are further operable when executing the instructions to display the data represented by the third BDD.

19. The apparatus of claim 13, wherein the processors are further operable when executing the instructions to indicate whether the third BDD is empty.

20. The apparatus of claim 13, wherein the sensor data are time specific.

21. The apparatus of claim 20, wherein the range is a time range.

22. The apparatus of claim 20, wherein

the first BDD has m variables;

i of the m variables correspond to time data associated with the sensor data, where m>

i ; and

j of the m variables correspond to sensor data, where m>

j.

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

24. The method of claim 13, wherein:

the second BDD represents a range [a, b], wherein a and b are the lower bound and the upper bound, respectively;

the fourth BDD represents a range [a, max], wherein max is the maximum value from the one or more data sets; and

the fifth BDD represents a range [b+1, max].

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

receive a query for data from one or more data sets of sensor data from one or more sensors, the query being for data that are within a range of a sensor output range, wherein the one or more data sets are represented by a first binary decision diagram (BDD), wherein the first BDD has in layers corresponding, respectively, to m variables;

construct a second BDD representing the range, wherein the second BDD has n layers corresponding, respectively, to n of the m variables, where m≧

n , wherein the range has a lower bound and an upper bound, and wherein constructing the second BDD comprises;

constructing a fourth BDD representing a first range from the lower bound of the range to a maximum value from the one or more data sets;

constructing a fifth BDD representing a second range from the upper bound of the range plus one to the maximum value from the one or more data sets;

negating the fifth BDD by applying a NOT operation to the fifth BDD; and

constructing the second BDD by performing an AND operation between the fourth BDD and the negated fifth BDD; and

construct a third BDD representing the data within the range by performing an AND operation between the first BDD and the second BDD.

26. The media of claim 25, wherein the second BDD evaluates to 1 for all values within the range and evaluates to 0 for all values outside the range.

27. The media of claim 25, wherein:

in the first BDD, the top n of the m layers correspond, respectively, to the n of the m variables in the second BDD.

28. The media of claim 25, wherein:

wherein the software is further operable when executed to reorder the first BDD so that the top n of the m layers of the first BDD correspond, respectively, to the n of the m variables in the second BDD.

29. The media of claim 25, wherein:

the first BDD has k nodes corresponding to the m variables, each of the m layers having one or more of the k nodes;

the range corresponds to n of the m variables, where m≧

n; and

in the first BDD, j of the k nodes corresponding to the n of the m variables in the range are at the top n of the m layers.

30. The media of claim 25, wherein the software is further operable when executed to display the data represented by the third BBD.

31. The media of claim 25, wherein the software is further operable when executed to indicate whether the third BDD is empty.

32. The media of claim 25, wherein the sensor data are time specific.

33. The media of claim 32, wherein the range is a time range.

34. The media of claim 32, wherein

the first BDD has m variables;

i of the m variables correspond to time data associated with the sensor data, where m>

i ; and

j of the m variables correspond to sensor data, where m>

j.

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

36. The method of claim 25, wherein:

the second BDD represents a range [a, b ], wherein a and b are the lower bound and the upper bound, respectively;

the fourth BDD represents a range [a, max], wherein max is the maximum value from the one or more data sets; and

the fifth BDD represents a range [b+1, max].

37. A system comprising:

means for receiving a query for data from one or more data sets of sensor data from one or more sensors, the query being for data that are within a range of a sensor output range, wherein the one or more data sets are represented by a first binary decision diagram (BDD), wherein the first BDD has m layers corresponding, respectively, to m variables;

means for constructing a second BDD representing the range, wherein the second BDD has n layers corresponding, respectively, to n of the m variables, where m≧

n , wherein the range has a lower bound and an user bound, wherein means for constructing the second BDD comprises;

means for constructing a fourth BDD representing a first range from the lower bound of the range to a maximum value from the one or more data sets;

means for constructing a fifth BDD representing a second range from the upper bound of the range plus one to the maximum value from the one or more data sets;

means for negating the fifth BDD by applying a NOT operation to the fifth BDD; and

means for constructing the second BDD by performing an AND operation between the fourth BDD and the negated fifth BDD; and

means for constructing a third BDD representing the data within the range by performing an AND operation between the first BDD and the second BDD.