Estimation of postings list length in a search system using an approximation table

Abstract

The present invention provides a method of minimizing accesses to secondary storage when searching an inverted index for a search term. The method comprises automatically obtaining a predetermined size of a posting list for the search term, the predetermined size based on document frequency for the search term, wherein the posting list is stored in secondary storage, and reading at least a portion of the posting list into memory based on the predetermined size. Corresponding computer system and program products are also provided.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS[0001]This application claims priority under 35 U.S.C. §119 to the following U.S. Provisional Applications, which are herein incorporated by reference in their entirety:[0002]Provisional Patent Application Ser. No. 61 / 233,411, by Flatland et al., entitled “ESTIMATION OF POSTINGS LIST LENGTH IN A SEARCH SYSTEM USING AN APPROXIMATION TABLE,” filed on Aug. 12, 2009; and[0003]Provisional Patent Application No. 61 / 233,420, by Flatland et al., entitled “EFFICIENT BUFFERED READING WITH A PLUG IN FOR INPUT BUFFER SIZE DETERMINATION,” filed on Aug. 12, 2009;[0004]Provisional Patent Application Ser. No. 61 / 233,427, by Flatland et al., entitled “SEGMENTING POSTINGS LIST READER,” filed on Aug. 12, 2009.[0005]This application contains subject matter which is related to the subject matter of the following applications, each of which is assigned to the same assignee as this application and filed on the same day as this application. Each of the below listed ap...

AI Technical Summary

Benefits of technology

[0019]The present invention provides, in a first aspect, a method of minimizing accesses to secondary storage when searching an inverted index for a search term. The method comprises automatically obtaining a predetermined size of a posting list for the search term, the predetermined size based on document frequency for the search term, wherein the posting list is stored in secondary storage, and reading at least a portion of the posting list into memory based on the predetermined size.

[0020]The present invention provides, in a second aspect, a computer system for minimizing accesses to secondary storage when searching an inverted index for a search term. The computer system comprises a memory, and a processor in communication with the memory to perform a method. The method comprises automatically obtaining a predetermined size of a posting list for the search term based on document frequency for the search term, wherein the posting list is stored in secondary storage, and reading at least a portion of the posting list into memory based on the predetermined size.

[0021]The present invention provides, in a third aspect, a program product for minimizing accesses to secondary storage when searching an inverted index for a search term. The program product comprises a storage medium readable by a processor and storing instructions for execution by the processor for performing a method. The method comprises automatically obtaining a predetermined size of a posting list for the search term based on document frequency for the search term, the posting list being stored in secondary storage, and reading at least a portion of the posting list into memory based on the size approximated.

Problems solved by technology

A large inverted index may not fit into a computer's main memory, requiring secondary storage, typically disk storage, to help store the posting file, lexicon, or both.

Each separate access to disk may incur seek time on the order of several milliseconds if it is necessary to move the hard drive's read heads, which is very expensive in terms of runtime performance compared to accessing main memory.

Images