System and method for providing randomly-accessible compacted data

Patent metadata

Field	Value
Publication number	US-12468662-B2
Application number	US-202318491798-A
Country	US
Kind code	B2
Filing date	Oct 22, 2023
Priority date	Oct 30, 2017
Publication date	Nov 11, 2025
Grant date	Nov 11, 2025

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 accessing a reference codebook associated with the compacted data file, a frequency table used to construct the reference codebook, and data query details. A data read request is supported by random-access search capabilities that may enable the locating and decoding of the bits corresponding to data query details. A random-access engine facilitates data write processes. 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.

First claim

What is claimed is:

1 . A system for random-access manipulation of compacted data files, comprising:
a computing system comprising a memory, a processor, and a non-volatile data storage device; a deconstruction subsystem comprising a first plurality of programming instructions stored in the memory and operable on the processor, wherein the first plurality of programming instructions, when operating on the processor, cause the computing system to:
deconstruct a data stream into a plurality of sourceblocks;
encode the data stream using a reference codebook by:
retrieving a codeword for each sourceblock from the reference codebook;
where there is no codeword for a first sourceblock, generating a hash code as a new codeword and storing the first sourceblock and its newly-created codeword in the reference codebook; and
storing the codewords corresponding to the data stream in a compacted data file;

a reconstruction subsystem comprising a third plurality of programming instructions stored in the memory and operable on the processor, wherein the third plurality of programming instructions, when operating on the processor, cause the computing system to:
retrieve a plurality of codewords from the compacted data file received from a requesting process;
decode each of the plurality of retrieved codewords by, for each retrieved codeword, retrieving the sourceblock associated with the respective codeword from the reference codebook; and
provide the retrieved sourceblocks as a data stream to the requesting process; and
a random-access subsystem comprising a second plurality of programming instructions stored in the memory and operating on the processor, wherein the second plurality of programming instructions, when operating on the processor, cause the computing subsystem to:
receive a data search query;
estimate, using an estimator module, a first starting bit location in the compacted data file;
refine the first starting bit location by:
determining whether a bit sequence starting at the first starting bit location corresponds to a codeword boundary and, if not, traversing the reference codebook until a codeword boundary is located at a new starting bit;
traversing from the new starting bit until a start codeword corresponding to the beginning of the data search query is identified; and
sending the first start codeword and a plurality of immediately following codewords from the compacted data file to the reconstruction engine for decoding.

2 . A method for random-access manipulation of compacted data files, comprising the steps of:
deconstructing, at a deconstruction subsystem comprising a first plurality of programming instructions stored in a memory and operable on a processor of a computing system, a data stream into a plurality of sourceblocks; encoding the data stream using the reference codebook by retrieving a codeword for each sourceblock from the reference codebook; and where there is no codeword for a first sourceblock, generating a hash code as a new codeword and storing the first sourceblock and its newly-created codeword in the reference codebook; retrieving, at a reconstruction subsystem comprising a second plurality of programming instructions stored in the memory and operable on the processor, a plurality of codewords from a compacted data file; decoding each of the plurality of retrieved codewords by, for each retrieved codeword, retrieving the sourceblock associated with the respective codeword from the reference codebook; providing the retrieved sourceblocks as a data stream to the requesting process; receiving, at a random-access subsystem comprising a third plurality of programming instructions stored in the memory and operating on the processor, a data search query; estimating, using an estimator module of the random-access engine, a first starting bit location in the compacted data file; refining the first starting bit location by determining whether a bit sequence starting at the first starting bit location corresponds to a codeword boundary and, if not, traversing the reference codebook until a codeword boundary is located at a new starting bit; traversing from the new starting bit until a start codeword corresponding to the beginning of the data search query is identified; and sending the first start codeword and a plurality of immediately following codewords from the compacted data file to the reconstruction subsystem for decoding.

Assignees

• Atombeam Technologies Inc

Inventors

• Riahi Aliasghar
• Cooper Joshua
• Haddad Mojgan
• Yeomans Charles

Classifications

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0641

  De-duplication techniques · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F21/572

  Secure firmware programming, e.g. of basic input output system [BIOS] · CPC title

• G06F16/1752 Primary

  based on file chunks · CPC title