Efficient indexing using compact decision diagrams

Patent metadata

Field	Value
Publication number	US-9405819-B2
Application number	US-2689708-A
Country	US
Kind code	B2
Filing date	Feb 6, 2008
Priority date	Feb 7, 2007
Publication date	Aug 2, 2016
Grant date	Aug 2, 2016

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.

First claim

What is claimed is:

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, wherein storing a BDD comprises storing for each of its nodes only a variable ID of the node that uniquely labels the node, a 0-edge negated flag, and THEN/ELSE pointers using a minimum number of bits for a size of the BDD.

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. 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;
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; and
using the determined elements of the list to calculate a conjunction between the list and one or more other lists of the inverted index.

7. The method of claim 6 , 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.

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

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

10. The method of claim 6 , wherein the objects are web pages.

11. One or more non-transitory 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, wherein storing a BDD comprises storing for each of its nodes only a variable ID of the node that uniquely labels the node, a 0-edge negated flag, and THEN/ELSE pointers using a minimum number of bits for a size of the BDD.

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

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

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

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

16. One or more non-transitory 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;
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; and

use the determined elements of the list to calculate a conjunction between the list and one or more other lists of the inverted index.

17. The computer-readable media of claim 16 , 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.

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

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

20. The computer-readable media of claim 16 , wherein the objects are web pages.

21. 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, wherein storing a BDD comprises storing for each of its nodes only a variable ID of the node that uniquely labels the node, a 0-edge neg

Assignees

• Stergiou Stergios
• Jain Jawahar
• Fujitsu Ltd

Inventors

• Stergiou Stergios
• Jain Jawahar

Classifications

• G06N5/01 Primary

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F16/31 Primary

  Indexing; Data structures therefor; Storage structures · CPC title

• G06N5/003

  Physics · mapped topic

• G06F17/30613 Primary

  Physics · mapped topic