SEGMENTING POSTINGS LIST READER

• US 20110040762A1
• 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,775
• Publication Number:
  US 20110040762A1
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/319 Inverted lists

Abstract

A size of a posting list is determined as part of searching an inverted index. The posting list is segmented for reading into a plurality of segments based on the size. For example, the segmenting may be performed if the size is larger than a predetermined size. Finally, each of the plurality of segments is read into memory.

Claims

1. A method of reading a posting list, the method comprising:

determining by a processor a size of a posting list as part of searching an inverted index;

segmenting the posting list for reading by the processor into a plurality of segments based on the size; and

reading by the processor each of the plurality of segments into memory.

2. The method of claim 1, wherein the segmenting is performed if the size is larger than a predetermined size.

3. The method of claim 2, further comprising reading by the processor all of the posting list at once if the size is the predetermined size or smaller.

4. The method of claim 1, wherein the segmenting is performed using at least one predetermined segment size.

5. The method of claim 1, wherein the segmenting is performed for at least one segment using at least one estimated segment size.

6. The method of claim 5, wherein at least one actual read size for the at least one segment is greater than or equal to at least one of the at least one estimated segment size, the method further comprising storing by the processor the at least one actual read size in a data structure for reuse.

7. The method of claim 1, wherein the posting list includes a plurality of relevance indicators for a plurality of postings in the posting list, wherein the posting list is sorted into descending order by relevance, and wherein the segmenting is performed for at least one segment using at least one relevance indicator.

8. The method of claim 7, wherein the reading comprises reading for the at least one segment until reaching a relevance indicator lower than the at least one relevance indicator, the method further comprising storing by the processor a read size for the at least one segment in a data structure for reuse.

9. The method of claim 7, wherein the plurality of relevance indicators comprises a plurality of scores.

10. A computer system for reading a posting list, the computer system comprising:

a memory; and

a processor in communication with the memory to perform a method, the method comprising;

determining a size of a posting list as part of searching an inverted index;

segmenting the posting list for reading into a plurality of segments based on the size; and

reading each of the plurality of segments into memory.

11. The system of claim 10, wherein the segmenting is performed if the size is larger than a predetermined size.

12. The system of claim 10, further comprising reading all of the posting list at once if the size is the predetermined size or smaller.

13. The system of claim 10, wherein the segmenting is performed using at least one predetermined segment size.

14. The system of claim 10, wherein the segmenting is performed for at least one segment using at least one estimated segment size.

15. The system of claim 14, wherein at least one actual read size for the at least one segment is greater than or equal to at least one of the at least one estimated segment size, the method further comprising storing the at least one actual read size in a data structure for reuse.

16. The system of claim 10, wherein the posting list includes a plurality of relevance indicators for a plurality of postings in the posting list, wherein the posting list is sorted into descending order by relevance, and wherein the segmenting is performed for at least one segment using at least one relevance indicator.

17. The system of claim 16, wherein the reading comprises reading for the at least one segment until reaching a relevance indicator lower than the at least one relevance indicator, the method further comprising storing a read size for the at least one segment in a data structure for reuse.

18. The system of claim 16, wherein the plurality of relevance indicators comprises a plurality of scores.

19. A program product for reading a posting list, 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;

determining a size of a posting list as part of searching an inverted index;

segmenting the posting list for reading into a plurality of segments based on the size; and

reading each of the plurality of segments into memory.

20. The program product of claim 19, wherein the segmenting is performed if the size is larger than a predetermined size.

21. The program product of claim 20, further comprising reading all of the posting list at once if the size is the predetermined size or smaller.

22. The program product of claim 19, wherein the segmenting is performed using at least one predetermined segment size.

23. The program product of claim 19, wherein the segmenting is performed for at least one segment using at least one estimated segment size.

24. The program product of claim 23, wherein at least one actual read size for the at least one segment is greater than or equal to at least one of the at least one estimated segment size, the method further comprising storing the at least one actual read size in a data structure for reuse.

25. The program product of claim 19, wherein the posting list includes a plurality of relevance indicators for a plurality of postings in the posting list, wherein the posting list is sorted into descending order by relevance, and wherein the segmenting is performed for at least one segment using at least one relevance indicator.

26. The program product of claim 25, wherein the reading comprises reading for the at least one segment until reaching a relevance indicator lower than the at least one relevance indicator, the method further comprising storing a read size for the at least one segment in a data structure for reuse.

27. The program product of claim 25, wherein the plurality of relevance indicators comprises a plurality of scores.