Searching documents for ranges of numeric values
First Claim
1. A system in communication, comprising:
- a processor; and
a computer readable storage medium including code executed by the processor to perform operations, 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 including at least one value 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;
storing the generated posting lists, wherein the posting lists are used to process a query on a range of values within the set of values;
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.
0 Assignments
0 Petitions
Accused Products
Abstract
Provided are a system and article of manufacture for searching documents for ranges of numeric values. A number of posting lists is generated, wherein each posting list is associated with a range of consecutive values within the set of values and includes document identifiers for documents including at least one value 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. The generated posting lists are stored. A query on a query range of values within the set of values is received and a determination is made of a minimum number of posting lists associated with consecutive values that together include the query range of values. The determined posting lists are merged.
-
Citations
36 Claims
-
1. A system in communication, comprising:
-
a processor; and a computer readable storage medium including code executed by the processor to perform operations, 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 including at least one value 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; storing the generated posting lists, wherein the posting lists are used to process a query on a range of values within the set of values; 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system in communication, comprising:
-
a processor; and a computer readable storage medium including code executed by the processor to perform operations, 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 including at least one value 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; 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, wherein each document in the generated posting list at the additional level includes one value in the consecutive values associated with the posting list at the additional level, and wherein a new additional level and posting lists associated therewith are generated with each iteration; 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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. An article of manufacture comprising at least one of a hardware device implementing logic and a computer storage media having computer executable code 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 including at least one value 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; storing the generated posting lists, wherein the posting lists are used to process a query on a range of values within the set of values; 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. - View Dependent Claims (20, 21, 22, 23, 24, 25)
-
-
26. An article of manufacture comprising at least one of a hardware device implementing logic and a computer storage media having computer executable code 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 including at least one value 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; 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, wherein each document in the generated posting list at the additional level includes one value in the consecutive values associated with the posting list at the additional level, and wherein a new additional level and posting lists associated therewith are generated with each iteration; 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. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
Specification