×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×