Caching Query Results with Binary Decision Diagrams (BDDs)
First Claim
1. A method comprising:
- constructing, by one or more computer systems, a plurality of first binary decision diagrams (BDDs), each of the first BDDs representing a different one of a plurality of words, each of the words having a unique word identifier (ID), each first BDD being constructed based on the word ID of the word represented by the first BDD;
constructing, by the one or more computer systems, a plurality of second BDDs, each of the second BDDs representing a different one of a plurality of search queries, each of the search queries comprising one or more of the words, each second BDD being constructed by performing an AND operation on the first BDDs representing the words in the search query represented by the second BDD;
constructing, by the one or more computer systems, a plurality of third BDDs, each of the third BDDs representing a different one of a plurality of web pages, each of the web pages having a unique page ID, each of the third BDDs being constructed based on the page ID of the web page represented by the third BDD;
constructing, by the one or more computer systems, a plurality of fourth BDDs, each of the fourth BDDs representing a different one of a plurality of search results generated in response to the search queries, each of the search results comprising one or more of the web pages, each fourth BDD being constructed by performing an OR operation on the third BDDs representing the web pages in the search result represented by the fourth BDD;
constructing, by the one or more computer systems, a plurality of fifth BDDs, each of the fifth BDDs representing a different one of a plurality of search tuples, each of the search tuples comprising a different one of the search queries and a different one of the search results corresponding to the search query, each fifth BDD being constructed by performing an AND operation on the second BDD representing the search query and the fourth BDD representing the search result that the search tuple represented by the fifth BDD comprises; and
constructing, by the one or more computer systems, a sixth BDD by performing an OR operation on the fifth BDDs, the sixth BDD representing the search queries and the search results.
1 Assignment
0 Petitions
Accused Products
Abstract
Construct a plurality of first binary decision diagrams (BDDs), each representing a different one of a plurality of words. Construct a plurality of second BDDs, each representing a different one of a plurality of search queries, each of the search queries comprising one or more of the words. Construct a plurality of third BDDs, each representing a different one of a plurality of web pages. Construct a plurality of fourth BDDs, each representing a different one of a plurality of search results, each search result comprising one or more web pages. Construct a plurality of fifth BDDs each representing a different one of a plurality of search tuples, each of the search tuples comprising a different one of the search queries and a different one of the search results. Construct a sixth BDD representing the search queries and the search results.
-
Citations
65 Claims
-
1. A method comprising:
-
constructing, by one or more computer systems, a plurality of first binary decision diagrams (BDDs), each of the first BDDs representing a different one of a plurality of words, each of the words having a unique word identifier (ID), each first BDD being constructed based on the word ID of the word represented by the first BDD; constructing, by the one or more computer systems, a plurality of second BDDs, each of the second BDDs representing a different one of a plurality of search queries, each of the search queries comprising one or more of the words, each second BDD being constructed by performing an AND operation on the first BDDs representing the words in the search query represented by the second BDD; constructing, by the one or more computer systems, a plurality of third BDDs, each of the third BDDs representing a different one of a plurality of web pages, each of the web pages having a unique page ID, each of the third BDDs being constructed based on the page ID of the web page represented by the third BDD; constructing, by the one or more computer systems, a plurality of fourth BDDs, each of the fourth BDDs representing a different one of a plurality of search results generated in response to the search queries, each of the search results comprising one or more of the web pages, each fourth BDD being constructed by performing an OR operation on the third BDDs representing the web pages in the search result represented by the fourth BDD; constructing, by the one or more computer systems, a plurality of fifth BDDs, each of the fifth BDDs representing a different one of a plurality of search tuples, each of the search tuples comprising a different one of the search queries and a different one of the search results corresponding to the search query, each fifth BDD being constructed by performing an AND operation on the second BDD representing the search query and the fourth BDD representing the search result that the search tuple represented by the fifth BDD comprises; and constructing, by the one or more computer systems, a sixth BDD by performing an OR operation on the fifth BDDs, the sixth BDD representing the search queries and the search results. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A method comprising:
-
assigning, by one or more computer systems, a plurality of word identifiers (IDs), each of the word IDs being assigned to a different one of a plurality of words, each of the words appearing at least once in a plurality of search queries, each of the search queries comprising one or more of the words; assigning, by the one or more computer systems, a plurality of page IDs, each of the page IDs being assigned to a different one of a plurality of web pages, each of the web pages being included at least once in a plurality of search results generated in response to the search queries, each of the search results comprising one or more of the web pages; obtaining, by the one or more computer systems, a plurality of query IDs, each of the query IDs identifying a different one of the search queries, each of the query IDs being obtained by combining the word IDs identifying the words comprised in the search query identified by the query ID; and constructing, by the one or more computer systems, a BDD representing the search queries and the search results, the BDD comprising; a binary 0 terminal node; a binary 1 terminal node; and a plurality of paths, each path comprising a plurality of decision nodes and leading to either the 0 terminal node or the 1 terminal node, each decision node represents a binary digit in one of the query IDs or one of the page IDs in binary format, and for each of the paths that leads to the 1 terminal node, a web page represented by first one or more of the decision nodes on the path is included in a search result for a search query represented by second one or more of the decision nodes on the path. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21)
-
-
22. One or more computer-readable storage media embodying software for execution by one or more computer systems and being operable when executed to:
-
construct a plurality of first binary decision diagrams (BDDs), each of the first BDDs representing a different one of a plurality of words, each of the words having a unique word identifier (ID), each first BDD being constructed based on the word ID of the word represented by the first BDD; construct a plurality of second BDDs, each of the second BDDs representing a different one of a plurality of search queries, each of the search queries comprising one or more of the words, each second BDD being constructed by performing an AND operation on the first BDDs representing the words in the search query represented by the second BDD; construct a plurality of third BDDs, each of the third BDDs representing a different one of a plurality of web pages, each of the web pages having a unique page ID, each of the third BDDs being constructed based on the page ID of the web page represented by the third BDD; construct a plurality of fourth BDDs, each of the fourth BDDs representing a different one of a plurality of search results generated in response to the search queries, each of the search results comprising one or more of the web pages, each fourth BDD being constructed by performing an OR operation on the third BDDs representing the web pages in the search result represented by the fourth BDD; construct a plurality of fifth BDDs, each of the fifth BDDs representing a different one of a plurality of search tuples, each of the search tuples comprising a different one of the search queries and a different one of the search results corresponding to the search query, each fifth BDD being constructed by performing an AND operation on the second BDD representing the search query and the fourth BDD representing the search result that the search tuple represented by the fifth BDD comprises; and constructing a sixth BDD by performing an OR operation on the fifth BDDs, the sixth BDD representing the search queries and the search results. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. One or more computer-readable storage media embodying software operable when executed by one or more computer systems to:
-
assign a plurality of word identifiers (IDs), each of the word IDs being assigned to a different one of a plurality of words, each of the words appearing at least once in a plurality of search queries, each of the search queries comprising one or more of the words; assign a plurality of page IDs, each of the page IDs being assigned to a different one of a plurality of web pages, each of the web pages being included at least once in a plurality of search results generated in response to the search queries, each of the search results comprising one or more of the web pages; obtain a plurality of query IDs, each of the query IDs identifying a different one of the search queries, each of the query IDs being obtained by combining the word IDs identifying the words comprised in the search query identified by the query ID; and construct a BDD representing the search queries and the search results, the BDD comprising; a binary 0 terminal node; a binary 1 terminal node; and a plurality of paths, each path comprising a plurality of decision nodes and leading to either the 0 terminal node or the 1 terminal node, each decision node represents a binary digit in one of the query IDs or one of the page IDs in binary format, and for each of the paths that leads to the 1 terminal node, a web page represented by first one or more of the decision nodes on the path is included in a search result for a search query represented by second one or more of the decision nodes on the path. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42)
-
-
43. A system comprising:
-
a memory comprising instructions executable by one or more processors; and one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to; construct a plurality of first binary decision diagrams (BDDs), each of the first BDDs representing a different one of a plurality of words, each of the words having a unique word identifier (ID), each first BDD being constructed based on the word ID of the word represented by the first BDD; construct a plurality of second BDDs, each of the second BDDs representing a different one of a plurality of search queries, each of the search queries comprising one or more of the words, each second BDD being constructed by performing an AND operation on the first BDDs representing the words in the search query represented by the second BDD; construct a plurality of third BDDs, each of the third BDDs representing a different one of a plurality of web pages, each of the web pages having a unique page ID, each of the third BDDs being constructed based on the page ID of the web page represented by the third BDD; construct a plurality of fourth BDDs, each of the fourth BDDs representing a different one of a plurality of search results generated in response to the search queries, each of the search results comprising one or more of the web pages, each fourth BDD being constructed by performing an OR operation on the third BDDs representing the web pages in the search result represented by the fourth BDD; construct a plurality of fifth BDDs, each of the fifth BDDs representing a different one of a plurality of search tuples, each of the search tuples comprising a different one of the search queries and a different one of the search results corresponding to the search query, each fifth BDD being constructed by performing an AND operation on the second BDD representing the search query and the fourth BDD representing the search result that the search tuple represented by the fifth BDD comprises; and constructing a sixth BDD by performing an OR operation on the fifth BDDs, the sixth BDD representing the search queries and the search results. - View Dependent Claims (44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55)
-
-
56. A system comprising:
-
a memory comprising instructions executable by one or more processors; and one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to; assign a plurality of word identifiers (IDs), each of the word IDs being assigned to a different one of a plurality of words, each of the words appearing at least once in a plurality of search queries, each of the search queries comprising one or more of the words; assign a plurality of page IDs, each of the page IDs being assigned to a different one of a plurality of web pages, each of the web pages being included at least once in a plurality of search results generated in response to the search queries, each of the search results comprising one or more of the web pages; obtain a plurality of query IDs, each of the query IDs identifying a different one of the search queries, each of the query IDs being obtained by combining the word IDs identifying the words comprised in the search query identified by the query ID; and construct a BDD representing the search queries and the search results, the BDD comprising; a binary 0 terminal node; a binary 1 terminal node; and a plurality of paths, each path comprising a plurality of decision nodes and leading to either the 0 terminal node or the 1 terminal node, each decision node represents a binary digit in one of the query IDs or one of the page IDs in binary format, and for each of the paths that leads to the 1 terminal node, a web page represented by first one or more of the decision nodes on the path is included in a search result for a search query represented by second one or more of the decision nodes on the path. - View Dependent Claims (57, 58, 59, 60, 61, 62, 63)
-
-
64. A system comprising:
-
means for constructing a plurality of first binary decision diagrams (BDDs), each of the first BDDs representing a different one of a plurality of words, each of the words having a unique word identifier (ID), each first BDD being constructed based on the word ID of the word represented by the first BDD; means for constructing a plurality of second BDDs, each of the second BDDs representing a different one of a plurality of search queries, each of the search queries comprising one or more of the words, each second BDD being constructed by performing an AND operation on the first BDDs representing the words in the search query represented by the second BDD; means for constructing a plurality of third BDDs, each of the third BDDs representing a different one of a plurality of web pages, each of the web pages having a unique page ID, each of the third BDDs being constructed based on the page ID of the web page represented by the third BDD; means for constructing a plurality of fourth BDDs, each of the fourth BDDs representing a different one of a plurality of search results generated in response to the search queries, each of the search results comprising one or more of the web pages, each fourth BDD being constructed by performing an OR operation on the third BDDs representing the web pages in the search result represented by the fourth BDD; means for constructing a plurality of fifth BDDs, each of the fifth BDDs representing a different one of a plurality of search tuples, each of the search tuples comprising a different one of the search queries and a different one of the search results corresponding to the search query, each fifth BDD being constructed by performing an AND operation on the second BDD representing the search query and the fourth BDD representing the search result that the search tuple represented by the fifth BDD comprises; and means for constructing a sixth BDD by performing an OR operation on the fifth BDDs, the sixth BDD representing the search queries and the search results.
-
-
65. A system comprising:
-
means for assigning a plurality of word identifiers (IDs), each of the word IDs being assigned to a different one of a plurality of words, each of the words appearing at least once in a plurality of search queries, each of the search queries comprising one or more of the words; means for assigning a plurality of page IDs, each of the page IDs being assigned to a different one of a plurality of web pages, each of the web pages being included at least once in a plurality of search results generated in response to the search queries, each of the search results comprising one or more of the web pages; means for obtaining a plurality of query IDs, each of the query IDs identifying a different one of the search queries, each of the query IDs being obtained by combining the word IDs identifying the words comprised in the search query identified by the query ID; and means for constructing a BDD representing the search queries and the search results, the BDD comprising; a binary 0 terminal node; a binary 1 terminal node; and a plurality of paths, each path comprising a plurality of decision nodes and leading to either the 0 terminal node or the 1 terminal node, each decision node represents a binary digit in one of the query IDs or one of the page IDs in binary format, and for each of the paths that leads to the 1 terminal node, a web page represented by first one or more of the decision nodes on the path is included in a search result for a search query represented by second one or more of the decision nodes on the path.
-
Specification