Patent ID: 7962489

Claim:
A method for constructing and using an index in searches for matches in a dataset to a pattern, the method comprising: dividing the dataset into buckets, wherein buckets are contiguous, non-overlapping ranges of values of a chosen attribute of elements of the dataset; specifying a pattern for which a match range of values of the chosen attribute can be determined and against which entries in the dataset are to be compared; determining a range of values based on a frequency of anticipated occurrence; generating a first set of values based on being within the range, the first set being a static set; generating a second set of values based on being outside the range, the second set being a dynamic set; identifying a set of static buckets corresponding to the static set; identifying a set of dynamic buckets corresponding to the dynamic set; generating a first set of index segments corresponding to the set of static buckets; generating a second set of index segments corresponding to the set of dynamic buckets; performing a first search by using the first set of index segments; performing a second search by using the second set of index segments only when index space is available; and recording which of the second set of index segments is less frequently used, thereby allowing such index segments to be released to make way for dynamic index segments if a needed index segment of the second set of index segments is not currently available.