Method, system, and program for searching documents for ranges of numeric values

• US 20060074962A1
• Filed: 09/24/2004
• Published: 04/06/2006
• Est. Priority Date: 09/24/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fontoura, Marcus Felipe, Lempel, Ronny, Zien, Jason Yeong, Qi, Runping
• Granted Patent: US 7,461,064 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Provided are a method, system, and program for searching documents for ranges of numeric values. Document identifiers for documents are accessed, wherein the documents include at least one value that is a member of a set of values. A number of posting lists are generated. Each posting list is associated with a range of consecutive values within the set of values and includes document identifiers for documents having values within the range of consecutive values associated with the posting list. Each document identifier is associated with one value in the set of values included in the document identified by the document identifier. The generated posting lists are stored.

Claims

1. A method, comprising:

accessing document identifiers for documents, wherein the documents include at least one value that is a member of a set of values;

generating a number of posting lists, wherein each posting list is associated with a range of consecutive values within the set of values and includes document identifiers for documents having values within the range of consecutive values associated with the posting list, and wherein each document identifier is associated with one value in the set of values included in the document identified by the document identifier; and

storing the generated posting lists.

2. The method of claim 1, further comprising:

sorting the document identifier and value pairs in each posting list by the document identifiers.

3. The method of claim 1, wherein each posting list includes a number of values determined by dividing the number of values in the set of values by the number of posting lists.

4. The method of claim 1, further comprising:

receiving a query on a query range of values within the set of values;

determining a minimum number of posting lists associated with consecutive values that together include the query range of values;

merging the determined posting lists to form a merged posting list including document identifiers of documents including values within the query range; and

returning the document identifiers in the merged posting list.

5. The method of claim 4, wherein determining the minimum number of posting lists comprises determining a minimum number of posting lists including values outside of the query range of values that are filtered before merging the posting lists.

6. The method of claim 4, further comprising:

filtering at least one of the determined posting lists including values outside of the query range of values to remove values not within the query range of values to form at least one filtered posting list only including values within the query range of values, wherein merging the determined posting lists comprising merging the at least one filtered posting list and determined posting lists that are not subject to filtering.

7. The method of claim 6, wherein the merging operation comprises an OR merge operation.

8. A method, comprising:

accessing document identifiers for documents including at least one value that is a member of a set of values;

generating a number of posting lists associated with a first level, wherein each posting list is associated with a range of consecutive values within the set of values and includes document identifiers for documents having values within the range of consecutive values associated with the posting list, and wherein each document identifier is associated with one value in the set of values included in the document identified by the document identifier; and

performing at least one iteration of generating posting lists for an additional level, wherein each posting list generated for the additional level is formed by merging at least two posting lists associated with a previous level, wherein each generated posting list at one additional level is associated with consecutive values in the set of values, and wherein a new additional level and posting lists associated therewith are generated with each iteration.

9. The method of claim 8, wherein the number of posting lists generated for the first level is a function of a number of the values in the set of values and a maximum number of records to filter in posting lists at the first level.

10. The method of claim 9, wherein the function comprises dividing the number of values in the set of values by two times the maximum number of records to filter.

11. The method of claim 8, wherein each posting list generated for one additional level is formed by merging a fixed number of posting lists associated with the previous level.

12. The method of claim 11, wherein the fixed number of posting lists is a function of the number of posting lists generated for the first level and a number of levels for which posting lists are generated.

14. The method of claim 8, further comprising:

receiving a query on a query range of values within the set of values;

determining a minimum number of posting lists associated with one or more levels having consecutive values that include the query range of values;

merging the determined posting lists to form a merged posting list including document identifiers of documents including values within the query range; and

returning the document identifiers in the merged posting list.

15. The method of claim 14, wherein determining the minimum number of posting lists comprises determining a minimum number of posting lists including values outside of the query range of values that are filtered before merging the posting lists.

16. The method of claim 8, further comprising:

filtering at least one of the determined posting lists at the first level in response to the determined posting lists at the first level including values outside of the query range of values to remove values not within the query range of values to form at least one filtered posting list only including values within the query range of values, wherein merging the determined posting lists comprising merging the at least one filtered posting list and determined posting lists that are not subject to filtering.

17. The method of claim 16, wherein merging the determined posting lists comprises:

accessing documents identifiers associated with a lowest value from the determined posting lists;

adding the accessed document identifiers to the merged posting list; and

repeating the operations of accessing and adding the document identifiers for a next lowest value from the determined posting lists until all the document identifiers in the determined posting lists have been added to the merged posting list, wherein the document identifiers in the merged posting list are sorted according to the values associated with the document identifiers.

13. The method of 8, wherein the additional iterations are performed to generate posting lists for a number of levels.

18. A system in communication, comprising:

a processor;

a computer readable medium including code executed by the processor to perform operations, the operations comprising;

(i) accessing document identifiers for documents, wherein the documents include at least one value that is a member of a set of values;

(ii) generating a number of posting lists, wherein each posting list is associated with a range of consecutive values within the set of values and includes document identifiers for documents having values within the range of consecutive values associated with the posting list, and wherein each document identifier is associated with one value in the set of values included in the document identified by the document identifier; and

(iii) storing the generated posting lists.

19. The system of claim 18, wherein the operations further comprise:

sorting the document identifier and value pairs in each posting list by the document identifiers.

20. The system of claim 18, wherein each posting list includes a number of values determined by dividing the number of values in the set of values by the number of posting lists.

21. The system of claim 18, wherein the operations further comprise:

receiving a query on a query range of values within the set of values;

determining a minimum number of posting lists associated with consecutive values that together include the query range of values;

merging the determined posting lists to form a merged posting list including document identifiers of documents including values within the query range; and

returning the document identifiers in the merged posting list.

22. The system of claim 21, wherein determining the minimum number of posting lists comprises determining a minimum number of posting lists including values outside of the query range of values that are filtered before merging the posting lists.

23. The system of claim 21, wherein the operations further comprise:

filtering at least one of the determined posting lists including values outside of the query range of values to remove values not within the query range of values to form at least one filtered posting list only including values within the query range of values, wherein merging the determined posting lists comprising merging the at least one filtered posting list and determined posting lists that are not subject to filtering.

24. The system of claim 23, wherein the merging operation comprises an OR merge operation.

25. A system in communication, comprising:

a processor;

a computer readable medium including code executed by the processor to perform operations, the operations comprising;

(i) accessing document identifiers for documents including at least one value that is a member of a set of values;

(ii) generating a number of posting lists associated with a first level, wherein each posting list is associated with a range of consecutive values within the set of values and includes document identifiers for documents having values within the range of consecutive values associated with the posting list, and wherein each document identifier is associated with one value in the set of values included in the document identified by the document identifier; and

(iii) performing at least one iteration of generating posting lists for an additional level, wherein each posting list generated for the additional level is formed by merging at least two posting lists associated with a previous level, wherein each generated posting list at one additional level is associated with consecutive values in the set of values, and wherein a new additional level and posting lists associated therewith are generated with each iteration.

26. The system of claim 25, wherein the number of posting lists generated for the first level is a function of a number of the values in the set of values and a maximum number of records to filter in posting lists at the first level.

27. The system of claim 26, wherein the function comprises dividing the number of values in the set of values by two times the maximum number of records to filter.

28. The system of claim 25, wherein each posting list generated for one additional level is formed by merging a fixed number of posting lists associated with the previous level.

29. The system of claim 25, wherein the fixed number of posting lists is a function of the number of posting lists generated for the first level and a number of levels for which posting lists are generated.

30. The system of claim 25, wherein the additional iterations are performed to generate posting lists for a number of levels.

31. The system of claim 25, wherein the operations further comprise:

receiving a query on a query range of values within the set of values;

determining a minimum number of posting lists associated with one or more levels having consecutive values that include the query range of values;

merging the determined posting lists to form a merged posting list including document identifiers of documents including values within the query range; and

returning the document identifiers in the merged posting list.

32. The system of claim 31, wherein determining the minimum number of posting lists comprises determining a minimum number of posting lists including values outside of the query range of values that are filtered before merging the posting lists.

33. The system of claim 25, wherein the operations further comprise:

filtering at least one of the determined posting lists at the first level in response to the determined posting lists at the first level including values outside of the query range of values to remove values not within the query range of values to form at least one filtered posting list only including values within the query range of values, wherein merging the determined posting lists comprising merging the at least one filtered posting list and determined posting lists that are not subject to filtering.

34. The system of claim 33, wherein merging the determined posting lists comprises:

accessing documents identifiers associated with a lowest value from the determined posting lists;

adding the accessed document identifiers to the merged posting list; and

repeating the operations of accessing and adding the document identifiers for a next lowest value from the determined posting lists until all the document identifiers in the determined posting lists have been added to the merged posting list, wherein the document identifiers in the merged posting list are sorted according to the values associated with the document identifiers.

35. An article of manufacture enabled to cause operations to be performed, the operations comprising:

accessing document identifiers for documents, wherein the documents include at least one value that is a member of a set of values;

generating a number of posting lists, wherein each posting list is associated with a range of consecutive values within the set of values and includes document identifiers for documents having values within the range of consecutive values associated with the posting list, and wherein each document identifier is associated with one value in the set of values included in the document identified by the document identifier; and

storing the generated posting lists.

36. The article of manufacture of claim 35, wherein the operations further comprise:

sorting the document identifier and value pairs in each posting list by the document identifiers.

37. The article of manufacture of claim 35, wherein each posting list includes a number of values determined by dividing the number of values in the set of values by the number of posting lists.

38. The article of manufacture of claim 35, wherein the operations further comprise:

receiving a query on a query range of values within the set of values;

determining a minimum number of posting lists associated with consecutive values that together include the query range of values;

merging the determined posting lists to form a merged posting list including document identifiers of documents including values within the query range; and

returning the document identifiers in the merged posting list.

39. The article of manufacture of claim 38, wherein determining the minimum number of posting lists comprises determining a minimum number of posting lists including values outside of the query range of values that are filtered before merging the posting lists.

40. The article of manufacture of claim 38, wherein the operations further comprise:

filtering at least one of the determined posting lists including values outside of the query range of values to remove values not within the query range of values to form at least one filtered posting list only including values within the query range of values, wherein merging the determined posting lists comprising merging the at least one filtered posting list and determined posting lists that are not subject to filtering.

41. The article of manufacture of claim 41, wherein the merging operation comprises an OR merge operation.

42. An article of manufacture enabled to cause operations to be performed, the operations comprising:

accessing document identifiers for documents including at least one value that is a member of a set of values;

generating a number of posting lists associated with a first level, wherein each posting list is associated with a range of consecutive values within the set of values and includes document identifiers for documents having values within the range of consecutive values associated with the posting list, and wherein each document identifier is associated with one value in the set of values included in the document identified by the document identifier; and

performing at least one iteration of generating posting lists for an additional level, wherein each posting list generated for the additional level is formed by merging at least two posting lists associated with a previous level, wherein each generated posting list at one additional level is associated with consecutive values in the set of values, and wherein a new additional level and posting lists associated therewith are generated with each iteration.

43. The article of manufacture of claim 42, wherein the number of posting lists generated for the first level is a function of a number of the values in the set of values and a maximum number of records to filter in posting lists at the first level.

44. The article of manufacture of claim 43, wherein the function comprises dividing the number of values in the set of values by two times the maximum number of records to filter.

45. The article of manufacture of claim 42, wherein each posting list generated for one additional level is formed by merging a fixed number of posting lists associated with the previous level.

46. The article of manufacture of claim 45, wherein the fixed number of posting lists is a function of the number of posting lists generated for the first level and a number of levels for which posting lists are generated.

47. The article of manufacture of claim 42, wherein the additional iterations are performed to generate posting lists for a number of levels.

48. The article of manufacture of claim 42, wherein the operations further comprise:

receiving a query on a query range of values within the set of values;

determining a minimum number of posting lists associated with one or more levels having consecutive values that include the query range of values;

merging the determined posting lists to form a merged posting list including document identifiers of documents including values within the query range; and

returning the document identifiers in the merged posting list.

49. The article of manufacture of claim 48, wherein determining the minimum number of posting lists comprises determining a minimum number of posting lists including values outside of the query range of values that are filtered before merging the posting lists.

50. The article of manufacture of claim 42, wherein the operations further comprise:

filtering at least one of the determined posting lists at the first level in response to the determined posting lists at the first level including values outside of the query range of values to remove values not within the query range of values to form at least one filtered posting list only including values within the query range of values, wherein merging the determined posting lists comprising merging the at least one filtered posting list and determined posting lists that are not subject to filtering.

51. The article of manufacture of claim 50, wherein merging the determined posting lists comprises:

accessing documents identifiers associated with a lowest value from the determined posting lists;

adding the accessed document identifiers to the merged posting list; and

repeating the operations of accessing and adding the document identifiers for a next lowest value from the determined posting lists until all the document identifiers in the determined posting lists have been added to the merged posting list, wherein the document identifiers in the merged posting list are sorted according to the values associated with the document identifiers.