Patent ID: 9325344
Filing Date: 2016-04-26
CPC Classification: G06F,H03M

Claim Text:
1. A method for encoding data stored in a column-oriented manner, comprising: finding column patterns among a set of data tuples, wherein each data tuple contains a set of columns, and wherein the column patterns are identified based upon a single column individually, and upon a combination of columns together, by grouping each column together with one or more other columns, without regard for column order, and evaluating rows of the grouped columns to determine the column patterns; identifying single column values occurring in the column patterns, in order to reduce a number of nodes of a prefix tree comprising a plurality of nodes; ordering the single column values occurring in the column patterns based on their corresponding frequencies into the prefix tree, wherein the prefix tree defines a pattern order and is constructed to share the nodes corresponding to the single column values occurring more frequently; sorting the data tuples according to the pattern order, resulting in sorted data tuples; and encoding columns of the sorted data tuples using run-length encoding.