Compact Decision Diagrams

• US 20080243746A1
• Filed: 02/07/2008
• Published: 10/02/2008
• Est. Priority Date: 02/07/2007
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Stergiou, Stergios, Jain, Jawahar
• Granted Patent: US 8,041,665 B2
• Time in Patent Office: Days
• US Class Current: 706/46
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

In one embodiment, a method includes determining an initial projected size of a BDD representing data for storage. The projected size corresponds to an initial projected number of decision nodes composing the BDD. The method includes determining an initial node structure for the decision nodes of the BDD according to the initial projected size of the BDD. The initial node structure includes for each decision node a variable identifier (ID), a 1-edge pointer, and a 0-edge pointer each represented by a minimum number of bits accommodating the initial projected number of decision nodes composing the BDD.

Claims

1. A method comprising:

determining an initial projected size of a BDD representing data for storage, the projected size corresponding to an initial projected number of decision nodes composing the BDD;

determining an initial node structure for the decision nodes of the BDD according to the initial projected size of the BDD, the initial node structure comprising for each decision node a variable identifier (ID), a 1-edge pointer, and a 0-edge pointer each represented by a minimum number of bits accommodating the initial projected number of decision nodes composing the BDD;

constructing the BDD according to the initial node structure; and

if during construction the BDD exceeds the initial projected size;

stopping construction of the BDD according to the initial data structure;

determining an updated projected size of the BDD to accommodate the BDD, the updated projected size of the BDD corresponding to an updated projected number of decision nodes composing the BDD;

determining an updated node structure for the decision nodes of the BDD according to the updated projected size of the BDD, the updated node structure comprising for each decision node a variable identifier (ID), a 1-edge pointer, and a 0-edge pointer each represented by a minimum number of bits accommodating the updated projected number of decision nodes composing the BDD; and

reconstructing the BDD according to the updated node structure.

2. The method of claim 1, further comprising further reconstructing the BDD according to a further updated node structure every time the BDD exceeds projected size during reconstruction.

3. The method of claim 1, wherein the BDD is a zero-suppressed binary decision diagram (ZDD).

4. The method of claim 1, wherein the BDD is a partitioned ordered binary decision diagram (POBDD).

5. The method of claim 1, wherein the BDD represents a list of an inverted index for storage.

6. The method claim 5, wherein the list corresponds to a particular key word and identifies a particular subset of a searchable set of web pages.

7. The method of claim 1, wherein:

the initial projected size of a BDD comprises d variables; and

the initial node structure comprises for each decision node a variable ID represented by ┌

log(d)┐

bits.

8. The method of claim 1, wherein the initial node structure comprises for each decision node a variable ID represented by five bits.

9. The method of claim 1, wherein:

the initial projected number of decision nodes composing the BDD is n; and

the initial node structure comprises for each decision node a 1-edge pointer and a 0-edge pointer each represented by ┌

log(n)┐

bits.

10. The method of claim 1, wherein:

a 1-edge pointer correlates a location specified by the 1-edge pointer to both a value of the 1-edge pointer and a position of the decision node of the 1-edge pointer; and

a 0-edge pointer correlates a location specified by the 0-edge pointer to both a value of the 0-edge pointer and a position of the decision node of the 0 edge pointer.

11. The method of claim 1, wherein

the initial projected size of a BDD comprises d variables;

the initial projected number of decision nodes composing the BDD is n; and

the initial node structure uses 2(┌

log(d)┐

)+┌

log(n)┐

bits of memory to store the BDD.

13. The computer-readable media of claim 11, wherein the software is further operable to further reconstruct the BDD according to a further updated node structure every time the BDD exceeds projected size during reconstruction.

14. The computer-readable media of claim 11, wherein the BDD is a zero-suppressed binary decision diagram (ZDD).

15. The computer-readable media of claim 11, wherein the BDD is a partitioned ordered binary decision diagram (POBDD).

16. The computer-readable media of claim 11, wherein the BDD represents a list of an inverted index for storage.

17. The computer-readable media of claim 15, wherein the list corresponds to a particular key word and identifies a particular subset of a searchable set of web pages.

18. The method of claim 1, wherein:

the initial projected size of a BDD comprises d variables; and

the initial node structure comprises for each decision node a variable ID represented by ┌

log(d)┐

bits.

19. The computer-readable media of claim 11, wherein the initial node structure comprises for each decision node a variable ID represented by five bits.

20. The computer-readable media of claim 11, wherein:

the initial projected number of decision nodes composing the BDD is n; and

the initial node structure comprises for each decision node a 1-edge pointer and a 0-edge pointer each represented by ┌

log(n)┐

bits.

21. The computer-readable media of claim 11, wherein:

a 1-edge pointer correlates a location specified by the 1-edge pointer to both a value of the 1-edge pointer and a position of the decision node of the 1-edge pointer; and

a 0-edge pointer correlates a location specified by the 0-edge pointer to both a value of the 0-edge pointer and a position of the decision node of the 0 edge pointer.

22. The computer-readable media of claim 11, wherein

the initial projected size of a BDD comprises d variables;

the initial projected number of decision nodes composing the BDD is n; and

the initial node structure uses 2(┌

log(d)┐

)+┌

log(n)┐

bits of memory to store the BDD.

12. One or more computer-readable media encoding software operable when executed to:

determine an initial projected size of a BDD representing data for storage, the projected size corresponding to an initial projected number of decision nodes composing the BDD;

determine an initial node structure for the decision nodes of the BDD according to the initial projected size of the BDD, the initial node structure comprising for each decision node a variable identifier (ID), a 1-edge pointer, and a 0-edge pointer each represented by a minimum number of bits accommodating the initial projected number of decision nodes composing the BDD;

construct the BDD according to the initial node structure; and

if during construction the BDD exceeds the initial projected size;

stop construction of the BDD according to the initial data structure;

determine an updated projected size of the BDD to accommodate the BDD, the updated projected size of the BDD corresponding to an updated projected number of decision nodes composing the BDD;

determine an updated node structure for the decision nodes of the BDD according to the updated projected size of the BDD, the updated node structure comprising for each decision node a variable identifier (ID), a 1-edge pointer, and a 0-edge pointer each represented by a minimum number of bits accommodating the updated projected number of decision nodes composing the BDD; and

reconstruct the BDD according to the updated node structure.

23. A system comprising:

means for determining an initial projected size of a BDD representing data for storage, the projected size corresponding to an initial projected number of decision nodes composing the BDD;

means for determining an initial node structure for the decision nodes of the BDD according to the initial projected size of the BDD, the initial node structure comprising for each decision node a variable identifier (ID), a 1-edge pointer, and a 0-edge pointer each represented by a minimum number of bits accommodating the initial projected number of decision nodes composing the BDD;

means for constructing the BDD according to the initial node structure; and

means for, if during construction the BDD exceeds the initial projected size;

stopping construction of the BDD according to the initial data structure;

determining an updated projected size of the BDD to accommodate the BDD, the updated projected size of the BDD corresponding to an updated projected number of decision nodes composing the BDD;

determining an updated node structure for the decision nodes of the BDD according to the updated projected size of the BDD, the updated node structure comprising for each decision node a variable identifier (ID), a 1-edge pointer, and a 0-edge pointer each represented by a minimum number of bits accommodating the updated projected number of decision nodes composing the BDD; and

reconstructing the BDD according to the updated node structure.