# US 8,280,836 B2 · Converting unordered graphs to oblivious read once ordered graph representation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,836 B2
- Document ID: US8280836B2
- Status: Granted
- Kind: B2
- Application number: 12/206,514
- Filed: 2008-09-08
- Published: 2010-03-11
- Granted: 2012-10-02
- Earliest claimed: 2008-09-08
- Assignees: Fair Isaac Corporation
- Inventors: Prasun Kumar
- Web page: https://patentgrep.com/patent/US8280836B2

## CPC

- G06N 5/02: Knowledge representation; Symbolic representation
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Data characterizing a desired variable order and an unordered graph can be received so that all paths in the unordered graph can be enumerated and a first path in the unordered graph can be leveled according to the desired variable order in a first oblivious read once decision graph. For each additional path other than the first path, the additional path is leveled in the desired order, nodes of the additional path are added to the first oblivious read once decision graph, and a union operation is performed on the first oblivious read once decision graph to union graph roots on the first oblivious read once decision graph. Thereafter, generation of a second oblivious read once decision graph can be initiated after completing processing of the first path and each additional path. Related apparatus, systems, techniques and articles are also described.

## Claims

### Claim 1

An article comprising a tangible machine-readable storage medium embodying instructions that when performed by one or more machines result in operations comprising:
receiving data characterizing a desired variable order and an unordered graph;
enumerating all paths in the unordered graph;
leveling, in an oblivious read once decision graph, a first path in the unordered graph according to the desired variable order; and
for each additional path in the unordered graph other than the first path, leveling the additional path in the desired order, adding nodes of the additional path to the oblivious read once decision graph, and performing a union operation on the oblivious read once decision graph to union graph roots on the oblivious read once decision graph.

### Claim 2 (depends on 1)

An article as in claim 1, wherein each additional path added to the first oblivious read once decision graph is in a conjunctive normal form.

### Claim 3 (depends on 1)

An article as in claim 1, wherein the first path is leveled in an empty oblivious read once decision graph.

### Claim 4 (depends on 1)

An article as in claim 1, wherein the storage medium further embodies instructions that when performed by one or more machines result in operations comprising:
for each additional path, iterating each node in bottom up order to determine if same node already exists in the oblivious read once decision graph.

### Claim 5 (depends on 4)

An article as in claim 4, wherein the storage medium further embodies instructions that when performed by one or more machines result in operations comprising:
adding a new node to the oblivious read once decision graph if is determined that such node does not already exist.

### Claim 6 (depends on 4)

An article as in claim 4, wherein two nodes are considered same if corresponding node conditions and sub-graph below the two nodes are identical.

### Claim 7 (depends on 6)

An article as in claim 6, wherein hashing techniques are used to identify isomorphic sub-graphs.

### Claim 8 (depends on 1)

An article as in claim 1, wherein adding nodes for each additional path results in two root nodes in the oblivious read once decision graph, and wherein the union operation merges two root nodes and child nodes reachable from the root nodes such that there is only one root node in the oblivious read once decision graph and the child conditions of a parent are not overlapping.

### Claim 9 (depends on 8)

An article as in claim 8, wherein the merging is performed such that any two nodes having the same subgraph are replaced with a new node with a condition that is union of the conditions of the replaced nodes.

### Claim 10 (depends on 1)

An article as in claim 1, wherein the paths are enumerated by a depth first traversal.

### Claim 11

A computer-implemented method comprising:
receiving data characterizing a desired variable order and an unordered graph;
enumerating all paths in the unordered graph;
leveling, in an oblivious read once decision graph, a first path in the unordered graph according to the desired variable order; and
for each additional path in the unordered graph other than the first path, leveling the additional path in the desired order, adding nodes of the additional path to the oblivious read once decision graph, and performing a union operation on the oblivious read once decision graph to union graph roots on the oblivious read once decision graph.

### Claim 12 (depends on 11)

A method as in claim 11, wherein each additional path added to the first oblivious read once decision graph is in a conjunctive normal form.

### Claim 13 (depends on 11)

A method as in claim 11, wherein the first path is leveled in an empty oblivious read once decision graph.

### Claim 14 (depends on 11)

A method as in claim 11 further comprising:
for each additional path, iterating each node in bottom up order to determine if same node already exists in the oblivious read once decision graph.

### Claim 15 (depends on 14)

A method as in claim 14 further comprising:
adding a new node to the oblivious read once decision graph if is determined that such node does not already exist.

### Claim 16 (depends on 14)

A method as in claim 14, wherein two nodes are considered same if corresponding node conditions and sub-graph below the two nodes are identical.

### Claim 17 (depends on 16)

A method as in claim 16, wherein hashing techniques are used to identify isomorphic sub-graphs.

### Claim 18 (depends on 11)

A method as in claim 11, wherein adding nodes for each additional path results in two root nodes in the oblivious read once decision graph, and wherein the union operation merges two root nodes and child nodes reachable from the root nodes such that there is only one root node in the oblivious read once decision graph and the child conditions of a parent are not overlapping.

### Claim 19 (depends on 18)

A method as in claim 18, wherein the merging is performed such that any two nodes having the same subgraph are replaced with a new node with a condition that is union of the conditions of the replaced nodes.

### Claim 20 (depends on 11)

A method as in claim 11, wherein the paths are enumerated by a depth first traversal.

### Claim 21

An article comprising a non-transitory machine-readable storage medium embodying instructions that when performed by one or more machines result in operations comprising:
receiving data characterizing a desired variable order and an unordered graph;
enumerating all paths in the unordered graph; and
recursively leveling, for an oblivious read once decision graph, each enumerated path according to the desired variable order.

### Claim 22 (depends on 21)

An article as in claim 21, wherein the storage medium further embodies instructions that when performed by one or more machines result in operations comprising:
combining root nodes of the oblivious read once decision graph.
