Comparing boolean functions representing sensor data

• US 8,583,718 B2
• Filed: 08/17/2010
• Issued: 11/12/2013
• Est. Priority Date: 08/17/2010
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Stergiou, Stergios, Jain, Jawahar
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US12/857,628
• Publication Number:
  US 20120047191A1
• Time in Patent Office: 1,183 Days
• Field of Search: None
• US Class Current: 708/400
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

According to certain embodiments, a first Boolean function and a second Boolean function are received. The first Boolean function represents a first data set, and the second Boolean function represents a second data set. The first Boolean function and the second Boolean function are transformed to a first arithmetic function and a second arithmetic function, respectively. A first hash code and a second hash code are calculated from the first arithmetic function and the second arithmetic function, respectively. If the first hash code equals the second hash code, the first Boolean function and the second Boolean function are designated as equivalent; otherwise, the first Boolean function and the second Boolean function are designated as not equivalent.

Claims

1. A method by one or more processors associated with one or more computing devices, one or more of the processors including a memory, the method comprising:

receiving, by one or more of the processors, a first Boolean function and a second Boolean function, the first Boolean function representing a first data set, the second Boolean function representing a second data set;

transforming, by one or more of the processors, the first Boolean function and the second Boolean function to a first arithmetic function and a second arithmetic function, respectively;

calculating, by one or more of the processors, a first hash code and a second hash code from the first arithmetic function and the second arithmetic function, respectively;

if the first hash code equals the second hash code, designating, by one or more of the processors, the first Boolean function and the second Boolean function as equivalent; and

otherwise, designating, by one or more of the processors, the first Boolean function and the second Boolean function as not equivalent.

2. The method of claim 1, the transforming further comprising:

transforming X AND Y of the first Boolean function to X×

Y of the first arithmetic function.

3. The method of claim 1, the transforming further comprising:

transforming X OR Y of the first Boolean function to X+Y−

X×

Y of the first arithmetic function.

4. The method of claim 1, the transforming further comprising:

transforming NOT(X) of the first Boolean function to 1−

X of the first arithmetic function.

5. The method of claim 1, the transforming further comprising:

transforming an idempotence property of the first Boolean function to X×

X=X of the first arithmetic function.

6. The method of claim 1, the calculating the first hash code further comprising:

calculating a third hash code of a third Boolean function;

calculating a fourth hash code of a fourth Boolean function, the first Boolean function comprising a Boolean combination of the third Boolean function and the fourth Boolean function; and

calculating the first hash code from an arithmetic combination of the third hash code and the fourth hash code.

7. The method of claim 1, the first data set recording a plurality of measurements taken by one or more sensors.

8. The method of claim 1, wherein the first and second Boolean functions are represented by a first binary decision diagram (BDD) and second BDD, respectively.

9. The method of claim 8, wherein the first and second BDD each comprises one or more rooted directed acyclic graphs representing the first and second Boolean functions, respectively.

10. The method of claim 9, wherein the first and second BDD each comprise a plurality of nodes and a plurality of edges connecting the nodes thereby forming a plurality of paths, each path in the BDD representing a set of variable assignments setting the represented Boolean function to either 1 or 0.

11. An apparatus comprising:

a memory configured to store a first Boolean function and a second Boolean function, the first Boolean function representing a first data set, the second Boolean function representing a second data set; and

one or more processors configured to;

transform the first Boolean function and the second Boolean function to a first arithmetic function and a second arithmetic function, respectively;

calculate a first hash code and a second hash code from the first arithmetic function and the second arithmetic function, respectively;

if the first hash code equals the second hash code, designate the first Boolean function and the second Boolean function as equivalent; and

otherwise, designating the first Boolean function and the second Boolean function as not equivalent.

12. The apparatus of claim 11, the transforming further comprising:

transforming X AND Y of the first Boolean function to X×

Y of the first arithmetic function.

13. The apparatus of claim 11, the transforming further comprising:

transforming X OR Y of the first Boolean function to X+Y−

X×

Y of the first arithmetic function.

14. The apparatus of claim 11, the transforming further comprising:

transforming NOT(X) of the first Boolean function to 1−

X of the first arithmetic function.

15. The apparatus of claim 11, the transforming further comprising:

transforming an idempotence property of the first Boolean function to X×

X=X of the first arithmetic function.

16. The apparatus of claim 11, the calculating the first hash code further comprising:

calculating a third hash code of a third Boolean function;

calculating a fourth hash code of a fourth Boolean function, the first Boolean function comprising a Boolean combination of the third Boolean function and the fourth Boolean function; and

calculating the first hash code from an arithmetic combination of the third hash code and the fourth hash code.

17. The apparatus of claim 11, the first data set recording a plurality of measurements taken by one or more sensors.

18. One or more non-transitory computer-readable media storing code, when executed by one or more processors, configured to:

receive a first Boolean function and a second Boolean function, the first Boolean function representing a first data set, the second Boolean function representing a second data set; and

transform the first Boolean function and the second Boolean function to a first arithmetic function and a second arithmetic function, respectively;

calculate a first hash code and a second hash code from the first arithmetic function and the second arithmetic function, respectively;

if the first hash code equals the second hash code, designate the first Boolean function and the second Boolean function as equivalent; and

otherwise, designating the first Boolean function and the second Boolean function as not equivalent.

19. The media of claim 18, the transforming further comprising:

transforming X AND Y of the first Boolean function to X×

Y of the first arithmetic function.

20. The media of claim 18, the transforming further comprising:

transforming X OR Y of the first Boolean function to X+Y−

X×

Y of the first arithmetic function.

21. The media of claim 18, the transforming further comprising:

transforming NOT(X) of the first Boolean function to 1−

X of the first arithmetic function.

22. The media of claim 18, the transforming further comprising:

transforming an idempotence property of the first Boolean function to X×

X=X of the first arithmetic function.

23. The media of claim 18, the calculating the first hash code further comprising:

calculating a third hash code of a third Boolean function;

calculating a fourth hash code of a fourth Boolean function, the first Boolean function comprising a Boolean combination of the third Boolean function and the fourth Boolean function; and

calculating the first hash code from an arithmetic combination of the third hash code and the fourth hash code.

24. The media of claim 18, the first data set recording a plurality of measurements taken by one or more sensors.