System and method for random-access manipulation of compacted data files
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.
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.