US 2015/0317327 A1 · Hierarchical Index Based Compression

Abstract

Computer-readable media, systems, and methods for hierarchical index based compression are described. In embodiments, a hierarchical data log or key-value pair based data log, such as a JSON log, is received and a tree-structured index (index tree) is recursively constructed. In one embodiment, the log comprises search-engine user interaction information. Structural information of the log is preserved by the index tree structure; for example, each node of the log has a corresponding index-tree node. Frequently repeating keys, values, and correlated key-value pairs may be stored in the index-tree node, which may be indexed using multiple levels of detail including a raw-string level for raw string representations of the node, a first level for indexing keys and common values, and a second level for indexing correlated key-value pairs. The index tree may be used to compress rows of the data log and also used to decompress and restore the log.

Claims20

Dependent claims

One or more computer-readable storage media having instructions embodied thereon that, when executed, perform a method for building an index tree for compressing a logfile, the method comprising:

receiving a logfile comprising one or more nodes, each node having a one or more keys, values, or key-value pairs;
for a first node, determining whether to index a raw string representation of the node;
upon determining to index the raw string, storing the raw string representation of the node in a raw-string level index;
upon determining not to index the raw string:
(1) storing the keys of the node in a first level index;
(2) for each key-value pair in the node, determining that the key-value pair is correlated;
and
(3) upon determining that the key-value pair is correlated, storing the key-value pair in a second level index;
and
creating an index tree corresponding to the logfile from the raw string, first, and second level indexes of the first node.

7 more elements

One or more computer-readable storage media having instructions embodied thereon that, when executed, perform a method for compressing a logfile, the method comprising:

receiving a logfile including one or more logfile nodes, each logfile node having one or more keys, values, or key-value pairs;
receiving an index tree corresponding to the logfile, the index tree including one or more index tree-nodes corresponding to the one or more logfile nodes, and further comprising a raw-string level index, a first level index, and a second level index corresponding to each index tree-node;
for a first logfile node corresponding to a first index tree-node, determining whether the first logfile node is indexed as a raw string;
upon determining that the first logfile node is indexed as a raw string, replacing the logfile node with a raw-string index entry, in the raw-string level index, that corresponds to a raw string representation of the logfile node;
upon determining that the first logfile node is not indexed as the raw string:
(1) for each key-value pair of the first logfile node, determining whether the key-value pair is indexed in the second level index;
(2) upon determining that the key-value pair is indexed in the second level index, replacing the key-value pair with a second-level index entry, in the second level index, that corresponds to the key-value pair;
and
(3) upon determining that the key-value pair is not indexed in the second level index, replacing the key of the key-value pair with a first-level key index entry, in the first level index, that corresponds to the key.

6 more elements

One or more computer-readable storage media having instructions embodied thereon that, when executed, perform a method for compressing a logfile using a tree-structured index corresponding to the logfile, the method comprising:

receiving a logfile comprising one or more nodes, each node having a one or more keys, values, or key-value pairs;
for each node, recursively:
(1) determining whether to index a raw string representation of the node;
(2) upon determining to index the raw string, storing the raw string representation of the node in a raw-string level dictionary;
(3) upon determining not to index the raw string:
a) storing the keys of the node in a first-level key dictionary;
b) determining common values of the node by identifying one or more values of the node that repeat in the logfile;
c) storing the common values in the first-level value dictionary;
d) for each key-value pair in the node, determining that the key-value pair is correlated;
and
e) upon determining that the key-value pair is correlated, storing the key-value pair in a second-level dictionary;
creating an index tree corresponding to the logfile, from the raw-string level, first-level value, first-level key, and second-level dictionaries of each node;
and
for each node of the logfile, compressing the node with the index tree.

11 more elements

Dependencies are inferred from the claim text.

Hierarchical Index Based Compression

Life of this patent

Hierarchical Index Based Compression

Life of this patent

Abstract

Claims20