Querying sensor data stored as binary decision diagrams

• US 8,930,394 B2
• Filed: 08/17/2010
• Issued: 01/06/2015
• Est. Priority Date: 08/17/2010
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Stergiou, Stergios, Jain, Jawahar
• Primary Examiner(s): SYED, FARHAN M
• Application Number:
  US12/857,603
• Publication Number:
  US 20120047160A1
• Time in Patent Office: 1,603 Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/9032 Query formulation
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

According to certain embodiments, a search query for a search of samples of sensor data is received. The search query indicates one or more requested values of one or more data parameters. The samples are represented by a characteristic function indicating whether a given binary representation represents a sample. A query function representing the one or more requested values is formulated. The query function and the characteristic function are used to identify one or more samples that have the one or more requested values.

Claims

1. A computer-implemented method comprising:

receiving a search query for a search of a plurality of samples of sensor measurement data taken by one or more sensors, the search query indicating one or more requested values of one or more data parameters of sensor measurement data, wherein each data value of the set of samples of the sensor data is expressed as a minterm to yield a set of minterms, each minterm within the set of minterms comprising a logical expression of one or more variables allocated to the data value of the sample of the sensor data, the plurality of samples represented by a samples binary decision diagram (BDD) indicating whether a given binary representation represents a sample of the plurality of samples, the samples BDD representing a characteristic function that is formulated by applying a logical operation to the minterms of the set of minterms to generate the samples BDD, wherein a BDD includes one or more rooted directed acyclic graphs representing a Boolean function and 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;

formulating a query BDD representing the one or more requested values of the one or more data parameters of sensor measurement data, wherein each requested value is expressed as a requested minterm to yield one or more requested minterms, the query BDD representing a query function that is formulated by applying a logical operation to the one or more requested minterms to generate the query BDD; and

generating an annotated samples BDD representing an annotated characteristic function by applying a logical AND operation to the query BDD and the samples BDD, the annotated samples BDD representing one or more samples of the sensor measurement data that have one or more of the requested values of the one or more data parameters of sensor measurement data.

2. The computer-implemented method of claim 1, a parameter of the one or more parameters representing a sensor measurement, a time, a temperature, or a location.

3. The computer-implemented method of claim 1, the formulating the query BDD further comprising:

expressing each requested value as a requested minterm to yield one or more requested minterms; and

formulating a query BDD from the one or more requested minterms.

4. The computer-implemented method of claim 1, further comprising:

determining the number of samples that have the one or more requested values.

5. The computer-implemented method of claim 1, the sensor measurement data comprising medical measurement data taken by one or more medical sensors.

16. The computer-implemented method of claim 1, further comprising:

accessing a set of samples of sensor data recording a plurality of sensor measurements taken by one or more sensors.

17. The computer-implemented method of claim 16, further comprising:

representing each data value of the set of samples of the sensor data as a minterm to yield a set of minterms, each minterm within the set of minterms comprising a logical expression of one or more variables allocated to the data value of the sample of the sensor data.

18. The computer-implemented method of claim 17, further comprising:

generating a samples binary decision diagram (BDD) from the set of samples by applying a logical operation to the minterms of the set of minterms to generate the samples BDD, the samples BDD indicating whether a given sample is a member of the set of samples.

6. 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 search query for a search of a plurality of samples of sensor measurement data taken by one or more sensors, the search query indicating one or more requested values of one or more data parameters of sensor measurement data, wherein each data value of the set of samples of the sensor data is expressed as a minterm to yield a set of minterms, each minterm within the set of minterms comprising a logical expression of one or more variables allocated to the data value of the sample of the sensor data, the plurality of samples represented by a samples binary decision diagram (BDD) indicating whether a given binary representation represents a sample of the plurality of samples, the samples BDD representing a characteristic function that is formulated by applying a logical operation to the minterms of the set of minterms to generate the samples BDD, wherein a BDD includes one or more rooted directed acyclic graphs representing a Boolean function and 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;

formulate a query BDD representing the one or more requested values of the one or more data parameters of sensor measurement data, wherein each requested value is expressed as a requested minterm to yield one or more requested minterms, the query BDD representing a query function that is formulated by applying a logical operation to the one or more requested minterms to generate the query BDD; and

generate an annotated samples BDD representing an annotated characteristic function by applying a logical AND operation to the query BDD and the samples BDD, the annotated samples BDD representing one or more samples of the sensor measurement data that have one or more of the requested values of the one or more data parameters of sensor measurement data.

7. The apparatus of claim 6, a parameter of the one or more parameters representing a sensor measurement, a time, a temperature, or a location.

8. The apparatus of claim 6, the formulating the query BDD further comprising:

expressing each requested value as a requested minterm to yield one or more requested minterms; and

formulating a query BDD from the one or more requested minterms.

9. The apparatus of claim 6, the one or more processors further configured to:

determine the number of samples that have the one or more requested values.

10. The apparatus of claim 6, the sensor measurement data comprising medical measurement data taken by one or more medical sensors.

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

receive a search query for a search of a plurality of samples of sensor measurement data taken by one or more sensors, the search query indicating one or more requested values of one or more data parameters of sensor measurement data, wherein each data value of the set of samples of the sensor data is expressed as a minterm to yield a set of minterms, each minterm within the set of minterms comprising a logical expression of one or more variables allocated to the data value of the sample of the sensor data, the plurality of samples represented by a samples binary decision diagram (BDD) indicating whether a given binary representation represents a sample of the plurality of samples, the samples BDD representing a characteristic function that is formulated by applying a logical operation to the minterms of the set of minterms to generate the samples BDD, wherein a BDD includes one or more rooted directed acyclic graphs representing a Boolean function and 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;

formulate a query BDD representing the one or more requested values of the one or more data parameters of sensor measurement data, wherein each requested value is expressed as a requested minterm to yield one or more requested minterms, the query BDD representing a query function that is formulated by applying a logical operation to the one or more requested minterms to generate the query BDD; and

generate an annotated samples BDD representing an annotated characteristic function by applying a logical AND operation to the query BDD and the samples BDD, the annotated samples BDD representing one or more samples of the sensor measurement data that have one or more of the requested values of the one or more data parameters of sensor measurement data.

12. The media of claim 11, a parameter of the one or more parameters representing a sensor measurement, a time, a temperature, or a location.

13. The media of claim 11, the formulating the query BDD further comprising:

expressing each requested value as a requested minterm to yield one or more requested minterms; and

formulating a query BDD from the one or more requested minterms.

14. The media of claim 11, the code further configured to:

determine the number of samples that have the one or more requested values.

15. The media of claim 11, the sensor measurement data comprising medical measurement data taken by one or more medical sensors.