Data record compression with progressive and/or selective decompression

Abstract

Disclosed herein are systems and methods for compressing structured or semi-structured data in a horizontal manner achieving compression ratios similar to vertical compression. Collections include structured or semi-structured data include a number of fields and are described using a schema. Fields include information having semantic similarity and are compressed using methods suitable for compressing the type of data. Data of a collection is compressed after fragmentation or may be normalized prior to compression. Data with semantic similarity is compressed using token tables and/or n-gram tables, where higher weighted, consisting of the product of frequency and length, occurring values may be stored in the lower numbered indices of the data table. Records include record descriptor bytes, field descriptor bytes, zero or more array descriptor bytes, zero or more object descriptor bytes, or bytes representing the data associated with the record. Data is indexed or compressed by a suitable module.

What is claimed is: 
     
         1 . A method of compression, the method comprising:
 storing, by a processor, a collection in a node, wherein the collection contains a plurality of records, wherein each of the records contains a plurality of fields, wherein each of the fields stores a data element;   accessing, by the processor, at least one of the data elements in at least one of the fields; and   compressing, by the processor, the at least one of the data elements in the at least one of the fields according to a schema associated with the collection.   
     
     
         2 . The method of  claim 1 , wherein the at least one of the fields is associated with an n-gram table, wherein the compressing is based on the n-gram table. 
     
     
         3 . The method of  claim 2 , further comprising:
 modifying, by the processor, the n-gram table upon an identification of first data which does not match second data stored in the n-gram table.   
     
     
         4 . The method of  claim 1 , wherein the compressing is based on an identification of first data which does not match second data stored in a token table. 
     
     
         5 . The method of  claim 4 , wherein the token table is associated with the at least one of the fields. 
     
     
         6 . The method of  claim 1 , wherein the compressing is based on a data type of the at least one element. 
     
     
         7 . The method of  claim 1 , wherein the compressing is such that the at least one data element is able to be individually decompressed when returned in response to a search query. 
     
     
         8 . The method of  claim 1 , further comprising:
 modifying, by the processor, a reference value stored in a first record based on a second record, wherein the records contain the first record and the second record, wherein the reference value is associated with an object.   
     
     
         9 . The method of  claim 1 , further comprising:
 outputting, by the processor, a value of an object, wherein the object is stored in at least one of the records, wherein the object comprises at least two of the fields.   
     
     
         10 . The method of  claim 1 , wherein at least two of the fields are grouped according to the schema, wherein the at least two of the fields are associated with a reference value stored in a table, wherein the records comprise a first record and a second record, wherein the first record comprises the at least two of the fields, wherein the second record stores the reference value. 
     
     
         11 . A method of decompression, the method comprising:
 accessing, by a processor, a storage storing a collection, wherein the collection contains a plurality of records, wherein each of the records contains a plurality of fields, wherein each of the fields stores a data element, wherein at least one of the data elements in at least one of the fields is compressed according to a schema associated with the collection;   initiating, by the processor, a decompression of the at least one of the data elements.   
     
     
         12 . The method of  claim 11 , wherein the at least one of the fields is associated with an n-gram table, wherein at least one of the data elements in at least one of the fields is compressed based on the n-gram table. 
     
     
         13 . The method of  claim 12 , wherein the at least one of the data elements in the at least one of the fields is compressed based on a modification of the n-gram table upon an identification of first data which does not match second data stored in the n-gram table. 
     
     
         14 . The method of  claim 11 , wherein the at least one of the data elements in the at least one of the fields is compressed based on an identification of first data which does not match second data stored in a token table. 
     
     
         15 . The method of  claim 14 , wherein the token table is associated with the at least one of the fields. 
     
     
         16 . The method of  claim 11 , wherein the at least one of the data elements in the at least one of the fields is compressed based on a data type of the at least one element. 
     
     
         17 . The method of  claim 11 , wherein the decompression comprises an individual decompression of the at least one data element, wherein the individual decompression is responsive to a search query. 
     
     
         18 . The method of  claim 11 , wherein the decompression is based on the at least one of the data elements in the at least one of the fields being compressed based on a modification of a reference value stored in a first record based on a second record, wherein the records contain the first record and the second record, wherein the reference value is associated with an object. 
     
     
         19 . The method of  claim 11 , herein the decompression is based on the at least one of the data elements in the at least one of the fields being compressed based on an output of a value of an object, wherein the object is stored in at least one of the records, wherein the object comprises at least two of the fields. 
     
     
         20 . The method of  claim 11 , wherein at least two of the fields are grouped according to the schema, wherein the at least two of the fields are associated with a reference value stored in a table, wherein the records comprise a first record and a second record, wherein the first record comprises the at least two of the fields, wherein the second record stores the reference value.