Patent ID: 8738631

Claim:
A method of using a computer to represent an inverted list record containing a key and one or more ordered logical or physical pointers, the number of said pointers being n, by logically subdividing said inverted list into m ordered groups of pointers, each group containing N pointers, N being larger than or equal to 1, m being smaller than or equal to n, and representing each group by a group record consisting of the key of said inverted list record followed by a representation of said group of pointers, different group records being able to have different representations, each group record being stored in an index structure organized by pages, wherein a representation always contains an interval specification containing the lowest pointer value in the group, followed by an optional range specification, said range specification consisting of the highest pointer value in the group or, in alternative, of the difference between the highest pointer in the group and the lowest pointer in the group, the lowest pointer and the range specification being compressed or uncompressed; and the representation can contain a bitmap of length N′, where N′=N−2 if the range specification is present or N′=N−1 otherwise, the i-th bit of said bitmap, where i≧1 and i≦N′, being set if there exists a pointer in said group of pointers such that its value is equal to the lowest pointer value in the group incremented by i, said representation being called a bitmapped representation; the representation can contain a compressed representation of the set of pointers from which the lowest pointer value is excluded, the highest pointer value being excluded if a range specification is present, said representation being called a compressed representation; if the group of N pointers has contiguous values or N is equal to 1, the representation for the group record can have a mandatory range specification and can contain no additional data, said representation being called a contiguous representation; if N is equal to 1, the representation for the group record can have an optional range specification and can contain no additional data, said representation being called a point representation.