Efficient Indexing Using Compact Decision Diagrams

• US 20080243907A1
• Filed: 02/06/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 9,405,819 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• 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 accessing an inverted index of a searchable set of objects including key words. The inverted index includes multiple lists each corresponding to a particular key word and identifying a particular subset of the objects including the particular key word. The method includes generating a binary decision diagram (BDD) for each of one or more of the lists. The BDD corresponds to the particular key word of the list, and each decision node of the BDD represents an object in the searchable set of objects including the particular key word of the list. The method includes storing each of one or more of the lists as its BDD. Storage of the BDD facilitates more efficient storage of the inverted index.

Claims

1. A method comprising:

accessing an inverted index of a searchable set of objects comprising key words, the inverted index comprising a plurality of lists each corresponding to a particular key word and identifying a particular subset of the objects comprising the particular key word;

generating a binary decision diagram (BDD) for each of one or more of the lists, the BDD corresponding to the particular key word of the list, each decision node of the BDD representing an object in the searchable set of objects comprising the particular key word of the list; and

storing each of one or more of the lists as its BDD, storage of the BDD facilitating more efficient storage of the inverted index.

2. The method of claim 1, wherein one or more of the BDDs are zero-suppressed nano binary decision diagrams (nanoZDDs).

3. The method of claim 1, wherein one or more of the BDDs are partitioned ordered binary decision diagrams (POBDDs).

4. The method of claim 1, wherein one or more of the BDDs have customized node structures.

5. The method of claim 1, wherein the objects are web pages and a web search engine uses the stored BDDs to generate search results.

6. The method of claim 1, wherein storing a BDD comprises storing for each of its nodes only a variable ID, a 0-edge negated flag, and THEN/ELSE pointers using a minimum number of bits for a size of the BDD.

7. A method comprising:

accessing a binary decision diagram (BDD) representing a list of an inverted index of a searchable set of objects comprising key words, the list corresponding to a particular key word and identifying a particular subset of the objects comprising the particular key word, the BDD corresponding to the particular key word of the list, each decision node of the BDD representing an object in the searchable set of objects comprising the particular key word of the list; and

determining elements of the list by;

traversing the BDD depth first along one or more paths to terminal node 1 of the BDD following 0 edges of decision nodes of the BDD first; and

assigning a set of values to an array of variables for the elements of the list according to each of the paths traversed.

8. The method of claim 7, wherein determining a first element of the list comprises:

traversing the BDD depth first along a first path from a root node of the BDD to terminal node 1 of the BDD following 0 edges of decision nodes of the BDD first; and

assigning a 1 to each variable in the array corresponding to a decision node of the BDD having a 1 edge in the first path, and assigning a 0 to each variable in the array corresponding to a decision node of the BDD having a 0 edge in the first path or corresponding to a decision node excluded from the BDD.

9. The method of claim 7, further comprising using the determined elements of the list to calculate a conjunction between the list and one or more other lists of the inverted index.

10. The method of claim 7, wherein the BDD is a zero-suppressed nano binary decision diagram (nanoZDD).

11. The method of claim 7, wherein one or more of the BDDs are partitioned ordered binary decision diagrams (POBDDs).

12. The method of claim 7, wherein the objects are web pages.

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

access an inverted index of a searchable set of objects comprising key words, the inverted index comprising a plurality of lists each corresponding to a particular key word and identifying a particular subset of the objects comprising the particular key word;

generate a binary decision diagram (BDD) for each of one or more of the lists, the BDD corresponding to the particular key word of the list, each decision node of the BDD representing an object in the searchable set of objects comprising the particular key word of the list; and

store each of one or more of the lists as its BDD, storage of the BDD facilitating more efficient storage of the inverted index.

14. The computer-readable media of claim 13, wherein one or more of the BDDs are zero-suppressed nano binary decision diagrams (nanoZDDs).

15. The computer-readable media of claim 13, wherein one or more of the BDDs are partitioned ordered binary decision diagrams (POBDDs).

16. The computer-readable media of claim 13, wherein one or more of the BDDs have customized node structures.

17. The computer-readable media of claim 13, wherein the objects are web pages and a web search engine uses the stored BDDs to generate search results.

18. The computer-readable media of claim 13, wherein storing a BDD comprises storing for each of its nodes only a variable ID, a 0-edge negated flag, and THEN/ELSE pointers using a minimum number of bits for a size of the BDD.

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

access a binary decision diagram (BDD) representing a list of an inverted index of a searchable set of objects comprising key words, the list corresponding to a particular key word and identifying a particular subset of the objects comprising the particular key word, the BDD corresponding to the particular key word of the list, each decision node of the BDD representing an object in the searchable set of objects comprising the particular key word of the list; and

determine elements of the list by;

traversing the BDD depth first along one or more paths to terminal node 1 of the BDD following 0 edges of decision nodes of the BDD first; and

assigning a set of values to an array of variables for the elements of the list according to each of the paths traversed.

20. The computer-readable media of claim 19, wherein determining a first element of the list comprises:

traversing the BDD depth first along a first path from a root node of the BDD to terminal node 1 of the BDD following 0 edges of decision nodes of the BDD first; and

assigning a 1 to each variable in the array corresponding to a decision node of the BDD having a 1 edge in the first path, and assigning a 0 to each variable in the array corresponding to a decision node of the BDD having a 0 edge in the first path or corresponding to a decision node excluded from the BDD.

21. The computer-readable media of claim 19, wherein the software is further operable when executed to use the determined elements of the list to calculate a conjunction between the list and one or more other lists of the inverted index.

22. The computer-readable media of claim 19, wherein the BDD is a zero-suppressed nano binary decision diagram (nanoZDD).

23. The computer-readable media of claim 19, wherein one or more of the BDDs are partitioned ordered binary decision diagrams (POBDDs).

24. The method of claim 19, wherein the objects are web pages.

25. A system comprising:

means for accessing an inverted index of a searchable set of objects comprising key words, the inverted index comprising a plurality of lists each corresponding to a particular key word and identifying a particular subset of the objects comprising the particular key word;

means for generating a binary decision diagram (BDD) for each of one or more of the lists, the BDD corresponding to the particular key word of the list, each decision node of the BDD representing an object in the searchable set of objects comprising the particular key word of the list; and

means for storing each of one or more of the lists as its BDD, storage of the BDD facilitating more efficient storage of the inverted index.

26. A system comprising:

means for accessing a binary decision diagram (BDD) representing a list of an inverted index of a searchable set of objects comprising key words, the list corresponding to a particular key word and identifying a particular subset of the objects comprising the particular key word, the BDD corresponding to the particular key word of the list, each decision node of the BDD representing an object in the searchable set of objects comprising the particular key word of the list; and

means for determining elements of the list by;

traversing the BDD depth first along one or more paths to terminal node 1 of the BDD following 0 edges of decision nodes of the BDD first; and

assigning a set of values to an array of variables for the elements of the list according to each of the paths traversed.