US 7,890,488 B2 · System and method for caching posting lists

Abstract

A method of caching posting lists to a search engine cache calculates the ratios between the frequencies of the query terms in a past query log and the sizes of the posting lists for each term, and uses these ratios to determine which posting lists should be cached by sorting the ratios in decreasing order and storing to the cache those posting lists corresponding to the highest ratio values. Further, a method of finding an optimal allocation between two parts of a search engine cache evaluates a past query stream based on a relationship between various properties of the stream and the total size of the cache, and uses this information to determine the respective sizes of both parts of the cache.

Claims10

Dependent claims

A method comprising:

determining, for each term of a plurality of query terms, a term frequency based on a number of queries that contain the term in a query log;
determining, for each of the plurality of query terms, a posting list size;
and
calculating, for each of the plurality of query terms, a value corresponding to a relationship between the term frequency and the posting list size;
for a particular term of the plurality of query terms, determining to store the posting list for the particular term in a cache of a search engine based on the value for the particular term;
wherein the method is performed by one or more computing devices.

3 more elements

Dependencies are inferred from the claim text.

System and method for caching posting lists

Life of this patent

System and method for caching posting lists

Life of this patent

Abstract

Claims10