ESTIMATION OF POSTINGS LIST LENGTH IN A SEARCH SYSTEM USING AN APPROXIMATION TABLE
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.
1 . A method of minimizing accesses to secondary storage when searching an inverted index for a search term, the method comprising:
obtaining by at least one computing unit 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 by the at least one computing unit at least a portion of the posting list into memory based on the predetermined size.
2 . The method of claim 1 , wherein the size is a length in bytes.
3 . The method of claim 1 , wherein if the size obtained is a predetermined minimum size or less, then the reading comprises reading all of the posting list at once.
4 . The method of claim 3 , wherein the reading comprises issuing a single read system call.
5 . The method of claim 3 , wherein the predetermined minimum size comprises a size of a main memory input buffer.
6 . The method of claim 1 , wherein if the predetermined size is greater than a predetermined minimum size, then the reading comprises performing a plurality of read operations.
7 . The method of claim 6 , wherein the predetermined minimum size comprises a size of a main memory input buffer.
8 . The method of claim 7 , wherein the performing comprises filling a largest available main memory input buffer a minimum number of times.
9 . The method of claim 1 , wherein the obtaining comprises:
partitioning all posting lists in the inverted index into a plurality of non-overlapping ranges, each range having a minimum document frequency and a maximum document frequency;
assigning a range ID to each posting list; and
using the range ID to look up the predetermined size.
10 . The method of claim 9 , wherein each successive maximum document frequency is twice that of an immediate prior one.
11 . A computer system for minimizing accesses to secondary storage when searching an inverted index for a search term, the computer system comprising:
a memory; and
a processor in communication with the memory to perform a method, the method comprising:
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.
12 . The system of claim 11 , wherein the size is a length in bytes.
13 . The system of claim 11 , wherein if the size obtained is a predetermined minimum size or less, then the reading comprises reading all of the posting list at once.
14 . The system of claim 13 , wherein the reading comprises issuing a single read system call.
15 . The system of claim 13 , wherein the predetermined minimum size comprises a size of a main memory input buffer.
16 . The system of claim 11 , wherein if the predetermined size is greater than a predetermined minimum size, then the reading comprises performing a plurality of read operations.
17 . The system of claim 16 , wherein the predetermined minimum size comprises a size of a main memory input buffer.
18 . The system of claim 17 , wherein the performing comprises filling a largest available main memory input buffer a minimum number of times.
19 . The system of claim 11 , wherein the obtaining comprises:
partitioning all posting lists in the inverted index into a plurality of non-overlapping ranges, each range having a minimum document frequency and a maximum document frequency;
assigning a range ID to each posting list; and
using the range ID to look up the predetermined size.
20 . The system of claim 19 , wherein each successive maximum document frequency is twice that of an immediate prior one.
21 . A program product for minimizing accesses to secondary storage when searching an inverted index for a search term, the program product comprising:
a storage medium readable by a processor and storing instructions for execution by the processor for performing a method, the method comprising:
obtaining by at least one computing unit 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 by the at least one computing unit at least a portion of the posting list into memory based on the predetermined size.
22 . The program product of claim 21 , wherein the size is a length in bytes.
23 . The program product of claim 21 , wherein if the size obtained is a predetermined minimum size or less, then the reading comprises reading all of the posting list at once.
24 . The program product of claim 23 , wherein the reading comprises issuing a single read system call.
25 . The program product of claim 23 , wherein the predetermined minimum size comprises a size of a main memory input buffer.
26 . The program product of claim 21 , wherein if the predetermined size is greater than a predetermined minimum size, then the reading comprises performing a plurality of read operations.
27 . The program product of claim 26 , wherein the predetermined minimum size comprises a size of a main memory input buffer.
28 . The program product of claim 27 , wherein the performing comprises filling a largest available main memory input buffer a minimum number of times.
29 . The program product of claim 21 , wherein the obtaining comprises:
partitioning all posting lists in the inverted index into a plurality of non-overlapping ranges, each range having a minimum document frequency and a maximum document frequency;
assigning a range ID to each posting list; and
using the range ID to look up the predetermined size.
30 . The program product of claim 29 , wherein each successive maximum document frequency is twice that of an immediate prior one.
31 . A data structure for use in minimizing accesses to data stored in secondary storage when searching an inverted index for a search term, the data structure comprising:
a posting list length approximation table, comprising a hash table, the hash table comprising:
a plurality of range IDs, each range ID corresponding to a subset of posting lists of predetermined similar size and representing a non-overlapping range of document frequencies; and
a posting list length approximation for each range ID.
32 . The data structure of claim 31 , wherein the posting list length approximation is a length in bytes.
33 . The data structure of claim 32 , wherein the posting list length approximation comprises a mean length and a standard deviation length.