System and method for random-access manipulation of compacted data files

Abstract

A system and method for random-access manipulation of compacted data files, utilizing a reference codebook, a random-access engine, a data deconstruction engine, and a data deconstruction engine. The system may receive a data query pertaining to a data read or data write request, wherein the data file to be read from or written to is a compacted data file. A random-access engine may facilitate data manipulation processes by transforming the codebook into a hierarchical representation and then traversing the representation scanning for specific codewords associated with a data query request. In an embodiment, an estimator module is present and configured to utilize cardinality estimation to determine a starting codeword to begin searching the compacted data file for the data associated with the data query. The random-access engine may encode the data to be written, insert the encoded data into a compacted data file, and update the codebook as needed.

What is claimed is: 
     
       1. A system for random-access manipulation of a compacted data file, comprising:
 a computing device comprising a memory, a processor, and a non-volatile data storage device; 
 a random access engine comprising a first plurality of programming instructions that, when operating on the processor, cause the computing device to:
 receive a data search query, the data search query being directed to the compacted data file, wherein the compacted file is compacted using a reference codebook; 
 organize the reference codebook into a hierarchical representation; 
 traverse the hierarchical representation until a start codeword corresponding to the beginning of the data search query is identified; and 
 send the start codeword and a plurality of immediately following codewords from the compacted data file to a decoder; and 
 
 an estimator module comprising a third plurality of programming instructions that, when operating on the processor, cause the computing device to:
 estimate a first starting bit location in the compacted data file; 
 refine the first starting bit location by:
 determining a plurality of codeword boundaries by performing distinct value estimation on the compacted data file, wherein the distinct value estimates correspond to a codeword boundary; and 
 determining whether a bit sequence starting at the first starting bit location corresponds to a codeword boundary of the plurality of codeword boundaries and, if not, traversing the hierarchical representation until a codeword boundary is located at a new starting bit. 
 
 
 
     
     
       2. The system of  claim 1 , further comprising a deconstruction engine comprising a second plurality of programming instructions that, when operating on the processor, cause the computing device to:
 deconstruct a data stream into a plurality of data sourceblocks; 
 create the compacted data file by compacting the plurality of data sourceblocks using the reference codebook; and 
 send the reference codebook to the random access engine. 
 
     
     
       3. The system of  claim 1 , wherein the estimator module sends the codeword boundary estimate to the random access engine. 
     
     
       4. The system of  claim 3 , wherein the random access engine uses the codeword boundary estimate as an initial point to begin traversing the hierarchical representation. 
     
     
       5. A method for random-access manipulation of a compacted data file, comprising the steps of:
 receiving a data search query, the data search query being directed to the compacted data file, wherein the compacted file is compacted using a reference codebook; 
 organizing the reference codebook into a hierarchical representation; 
 traversing the hierarchical representation until a start codeword corresponding to the beginning of the data search query is identified; and 
 sending the start codeword and a plurality of immediately following codewords from the compacted data file to a decoder; 
 estimating, using an estimator module, a first starting bit location in the compacted data file; and 
 refining the first starting bit location by: 
 determining a plurality of codeword boundaries by performing distinct value estimation on the compacted data file, wherein the distinct value estimates correspond to a codeword boundary; and 
 determining whether a bit sequence starting at the first starting bit location corresponds to a codeword boundary of the plurality of codeword boundaries and, if not, traversing the hierarchical representation until a codeword boundary is located at a new starting bit. 
 
     
     
       6. The method of  claim 5 , further comprising the steps of:
 deconstructing a data stream into a plurality of data sourceblocks; 
 creating the compacted data file by compacting the plurality of data sourceblocks using the reference codebook; and 
 sending the reference codebook to the random access engine. 
 
     
     
       7. The method of  claim 5 , wherein the codeword boundary estimate is used as an initial point to begin traversing the hierarchical representation.