ESTIMATION OF POSTINGS LIST LENGTH IN A SEARCH SYSTEM USING AN APPROXIMATION TABLE

• US 20110040761A1
• Filed: 08/11/2010
• Published: 02/17/2011
• Est. Priority Date: 08/12/2009
• Status: Abandoned Application

• Current Assignee: GlobalSpec, Inc. (S&P Global Inc.)
• Original Assignee: GlobalSpec, Inc. (S&P Global Inc.)
• Inventors: Dalton, Jeff J., Flatland, Steinar
• Application Number:
  US12/854,726
• Publication Number:
  US 20110040761A1
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/319 Inverted lists

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.

Claims

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.