Annotating environmental data represented by characteristic functions

• US 9,002,781 B2
• Filed: 08/17/2010
• Issued: 04/07/2015
• Est. Priority Date: 08/17/2010
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Stergiou, Stergios, Jain, Jawahar, Kimura, Yasunori
• Primary Examiner(s): HICKS, MICHAEL J
• Application Number:
  US12/857,768
• Publication Number:
  US 20120047137A1
• Time in Patent Office: 1,694 Days
• US Class Current: 707/603
• CPC Class Codes: A61B 5/022 by applying pressure to close blood vessels, e.g. against the skin; Ophthalmodynamometers
• CPC Class Codes: A61B 5/14551 for measuring blood gases
• CPC Class Codes: A61B 5/318 Heart-related electrical modalities, e.g. electrocardiography [ECG]
• CPC Class Codes: G06F 16/212 with details for data modelling support
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24558 Binary matching operations
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G16H 10/40 for data related to laboratory analysis, e.g. patient specimen analysis
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass

Abstract

According to certain embodiments, a set of samples of sensor data is accessed. The set of samples records environmental measurements taken by one or more environmental sensors. A characteristic function is generated from the set of samples. The characteristic function indicates whether a given sample is a member of the set of samples. One or more samples of the set of samples that are associated with a given environmental annotation are identified according to the characteristic function.

Claims

1. A method comprising, by one or more processors associated with one or more computing devices:

accessing, by one or more of the processors, a set of samples of sensor data recording a plurality of environmental measurements taken by one or more environmental sensors;

representing, by the at least one computer processor, 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, wherein a minterm is a logical expression of n variables that employs only a complement operator and a conjunction operator;

generating, by one or more of the processors, a first binary decision diagram from the set of samples by applying a logical OR operation to the minterms of the set of minterms to generate the first binary decision diagram by generating a characteristic function ƒ

₁({right arrow over (x)};

{right arrow over (s)}¹;

{right arrow over (s)}²) that is the logical OR of all minterms in the set of minterms, the first binary decision diagram indicating whether a given sample is a member of the set of samples, wherein a binary decision diagram 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 binary decision diagram representing a set of variable assignments setting the represented Boolean function to either 1 or 0, the first binary decision diagram corresponding to a first hash code;

identifying, by one or more of the processors, one or more samples of the set of samples that are associated with a given environmental annotation according to the first binary decision diagram; and

determining whether the environmental measurements associated with the set of samples are valid by;

if the first hash code equals a second hash code, designating the environmental measurements as valid, the second has code being calculated from an arithmetic function generated by transforming the first binary decision diagram according to one or more identity rules; and

otherwise, designating the environmental measurements as invalid.

2. The method of claim 1, the identifying the one or more samples comprising:

receiving a model binary decision diagram, the model binary decision diagram representing a set of model samples annotated with one or more environmental annotations; and

identifying the one or more samples using the model binary decision diagram and the first binary decision diagram.

3. The method of claim 1, the identifying the one or more samples comprising:

annotating the first binary decision diagram using a model binary decision diagram to yield an annotated binary decision diagram, the model binary decision diagram representing a set of model samples annotated with one or more environmental annotations; and

querying the annotated binary decision diagram to identify the one or more samples.

4. The method of claim 1, the identifying the one or more samples comprising:

annotating the binary decision diagram using a model binary decision diagram to yield an annotated binary decision diagram, the model binary decision diagram representing a set of model samples annotated with one or more environmental annotations, the annotated binary decision diagram representing the set of samples annotated with the one or more environmental annotations; and

querying the annotated binary decision diagram to identify the one or more samples.

5. The method of claim 1, the identifying the one or more samples comprising:

determining an annotated binary decision diagram for the first binary decision diagram, the annotated binary decision diagram representing the set of samples annotated with one or more environmental annotations;

formulating a query binary decision diagram representing the given environmental annotation; and

combining the query binary decision diagram and the annotated binary decision diagram by applying a logical AND operation to identify the one or more samples.

6. The method of claim 1, the one or more environmental annotations comprising one or more of the following:

a normal annotation and an abnormal annotation.

7. The method of claim 1, wherein one or more of the following logical operations is applied to the first binary decision diagram:

a logical AND operation, a logical OR operation, a logical XOR operation, or a logical NOT operation.

8. The method of claim 1, wherein the given environmental annotation is a particular categorization of the environmental sensor data.

9. The method of claim 1, further comprising:

receiving a search query for a search of a plurality of environmental measurements taken by the one or more environmental sensors, the search query indicating one or more requested values of one or more environmental data parameters, the plurality of samples represented by the first binary decision diagram indicating whether a given binary representation represents a sample of the plurality of samples;

formulating a query binary decision diagram representing the one or more requested values; and

using the query binary decision diagram and the first binary decision diagram to identify one or more samples of the sensor measurement data that have the one or more requested values by applying a logical AND operation to the query BDD and the first binary decision diagram.

10. The method of claim 1, further comprising:

accessing the first hash code corresponding to the first binary decision diagram, wherein the first binary decision diagram and the first hash code are transmitted from one or more of the environmental sensors to one or more of the computing devices;

transforming the first binary decision diagram to the arithmetic function according to the one or more identity rules; and

calculating the second hash code from the arithmetic function.

11. The method of claim 1, wherein the first binary decision diagram is a reduced ordered binary decision diagram, wherein isomorphic subgraphs are not present in the first binary decision diagram, and wherein an order of the variables from a root node of the first binary decision diagram to a terminal node are the same for all paths in the first binary decision diagram.

12. 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 set of samples of sensor data recording a plurality of environmental measurements taken by one or more environmental sensors;

represent 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, wherein a minterm is a logical expression of n variables that employs only a complement operator and a conjunction operator;

generate a first binary decision diagram from the set of samples by applying a logical OR operation to the minterms of the set of minterms to generate the first binary decision diagram by generating a characteristic function ƒ

₁({right arrow over (x)};

{right arrow over (s)}¹;

{right arrow over (s)}²) that is the logical OR of all minterms in the set of minterm, the first binary decision diagram indicating whether a given sample is a member of the set of samples, wherein a binary decision diagram 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 binary decision diagram representing a set of variable assignments setting the represented Boolean function to either 1 or 0, the first binary decision diagram corresponding to a first hash code;

identify one or more samples of the set of samples that are associated with a given environmental annotation according to the first binary decision diagram; and

determine whether the environmental measurements associated with the set of samples are valid by;

if the first hash code equals a second hash code, designate the environmental measurements as valid, the second has code being calculated from an arithmetic function generated by transforming the first binary decision diagram according to one or more identity rules; and

otherwise, designate the environmental measurements as invalid.

13. The apparatus of claim 12, the identifying the one or more samples comprising:

receiving a model binary decision diagram, the model binary decision diagram representing a set of model samples annotated with one or more environmental annotations; and

identifying the one or more samples using the model binary decision diagram and the first binary decision diagram.

14. The apparatus of claim 12, the identifying the one or more samples comprising:

annotating the first binary decision diagram using a model binary decision diagram to yield an annotated binary decision diagram, the model binary decision diagram representing a set of model samples annotated with one or more environmental annotations; and

querying the annotated binary decision diagram to identify the one or more samples.

15. The apparatus of claim 12, the identifying the one or more samples comprising:

annotating the binary decision diagram using a model binary decision diagram to yield an annotated binary decision diagram, the model binary decision diagram representing a set of model samples annotated with one or more environmental annotations, the annotated binary decision diagram representing the set of samples annotated with the one or more environmental annotations; and

querying the annotated binary decision diagram to identify the one or more samples.

16. The apparatus of claim 12, the identifying the one or more samples comprising:

determining an annotated binary decision diagram for the first binary decision diagram, the annotated binary decision diagram representing the set of samples annotated with one or more environmental annotations;

formulating a query binary decision diagram representing the given environmental annotation; and

combining the query binary decision diagram and the annotated binary decision diagram by applying a logical AND operation to identify the one or more samples.

17. The apparatus of claim 12, the one or more environmental annotations comprising one or more of the following:

a normal annotation and an abnormal annotation.

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

access a set of samples of sensor data recording a plurality of environmental measurements taken by one or more environmental sensors;

represent 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, wherein a minterm is a logical expression of n variables that employs only a complement operator and a conjunction operator;

generate a first binary decision diagram from the set of samples by applying a logical OR operation to the minterms of the set of minterms to generate the first binary decision diagram by generating a characteristic function ƒ

₁({right arrow over (x)};

{right arrow over (s)}¹;

{right arrow over (s)}²) that is the logical OR of all minterms in the set of minterms, the first binary decision diagram indicating whether a given sample is a member of the set of samples, wherein a binary decision diagram 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 binary decision diagram representing a set of variable assignments setting the represented Boolean function to either 1 or 0, the first binary decision diagram corresponding to a first hash code;

identify one or more samples of the set of samples that are associated with a given environmental annotation according to the first binary decision diagram; and

determine whether the environmental measurements associated with the set of samples are valid by;

if the first hash code equals a second hash code, designate the environmental measurements as valid, the second has code being calculated from an arithmetic function generated by transforming the first binary decision diagram according to one or more identity rules; and

otherwise, designate the environmental measurements as invalid.

19. The media of claim 18, the identifying the one or more samples comprising:

receiving a model binary decision diagram, the model binary decision diagram representing a set of model samples annotated with one or more environmental annotations; and

identifying the one or more samples using the model binary decision diagram and the first binary decision diagram.

20. The media of claim 18, the identifying the one or more samples comprising:

annotating the first binary decision diagram using a model binary decision diagram to yield an annotated binary decision diagram, the model binary decision diagram representing a set of model samples annotated with one or more environmental annotations; and

querying the annotated binary decision diagram to identify the one or more samples.

21. The media of claim 18, the identifying the one or more samples comprising:

annotating the binary decision diagram using a model binary decision diagram to yield an annotated binary decision diagram, the model binary decision diagram representing a set of model samples annotated with one or more environmental annotations, the annotated binary decision diagram representing the set of samples annotated with the one or more environmental annotations; and

querying the annotated binary decision diagram to identify the one or more samples.

22. The media of claim 18, the identifying the one or more samples comprising:

determining an annotated binary decision diagram for the first binary decision diagram, the annotated binary decision diagram representing the set of samples annotated with one or more environmental annotations;

formulating a query binary decision diagram representing the given environmental annotation; and

combining the query binary decision diagram and the annotated binary decision diagram by applying a logical AND operation to identify the one or more samples.

23. The media of claim 18, the one or more environmental annotations comprising one or more of the following:

a normal annotation and an abnormal annotation.