Patent ID: 7139765

Claim:
A computer-implemented method for improving compression for storage of a plurality of parallel data element sequences comprising: (a) Creating one or more dictionaries of unique values for each of said data element sequences, wherein said one or more dictionaries associate(s) a numeric index with each unique value, (b) forming an n-ary tree with leaf and interior nodes wherein: (1) each said leaf node corresponds to one of said one or more dictionaries, (2) each said interior node associates a numeric index with tuples of numeric indexes from other subordinate leaf or interior nodes, (3) one or more interior nodes store one or more sequences of mutually-consecutive tuples by representing said sequences in a form that uses less storage space than representing said sequences as individual tuples, and (4) one or more interior nodes perform at least one of: i. record the addition of a tuple that extends a tuple sequencing by modifiying one or more fields in the representation of said sequence that are capable of representing the length of said sequence, or ii. record the addition of a tuple that invalidates an existing tuple sequence by splitting said tuple sequence into one or more subsequences, wherein none of the tuples of said subsequences contain any element of said added tuple, or iii. record the addition of a tuple that has not been previously added to said interior node, wherein said added tuple does not extend a tuple sequence, by adding said tuple to a tuple collection, and wherein the forming step defines: a problem space comprising: (1) a set of states, wherein each said state has an n-ary tree design, said design comprising a set of leaves and zero or more interior nodes, wherein each said interior node contains zero or more other nodes as children, and (2) a value function, giving a numeric ranking of the value of any state n-ary tree design, wherein said numeric ranking is used to perform at least one of: a determine if said state n-ary design is acceptable or b rank the n-ary tree designs of states reachable by applying operators to a state, to select an operator, defining one or more operators that transform one state to another, and searching said problem space, starting from an initial state and applying operators to move to other states until a state with an acceptable n-ary tree design is reached.