×

Caching query results with binary decision diagrams (BDDs)

  • US 8,468,142 B2
  • Filed: 08/04/2009
  • Issued: 06/18/2013
  • Est. Priority Date: 08/06/2008
  • Status: Active Grant
First Claim
Patent Images

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, wherein the plurality of search queries comprise a plurality of cached searched queries that have been previously submitted to a search engine;

    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; 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 all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×