System and method for caching posting lists
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.
1. 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.
2. The method of claim 1 wherein the relationship is a ratio between the term frequency and the posting list size.
3. The method of claim 2 further comprising compiling a list of the calculated values, wherein the list is sorted in decreasing order of the calculated values.
4. The method of claim 3 further comprising storing a posting list corresponding to each of the plurality of query terms to the search engine cache according to the sorted list.
5. The method of claim 1 wherein the posting list size corresponds to the number of documents in the search engine's web-page collection that contain the query term.
6. The method of claim 1 wherein the term frequency is derived from a past query log.
7. A non-transitory computer-readable medium encoded with a computer-executable program, which, when executed by one or more computing devices, causes the one or more computing devices to perform:
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.
8. A non-transitory computer-readable medium as recited in claim 7 , wherein the relationship is a ratio between the term frequency and the posting list size.
9. A non-transitory computer-readable medium as recited in claim 8 , wherein the computer-executable program, when executed by the one or more computing devices, further causes the one or more computing devices to perform:
compiling a list of the calculated values, wherein the list is sorted in decreasing order of the calculated values.
10. A non-transitory computer-readable medium as recited in claim 9 , wherein the computer-executable program, when executed by the one or more computing devices, further causes the one or more computing devices to perform:
storing a posting list corresponding to each of the plurality of query terms to the search engine cache according to the sorted list.