Efficient lossless reduction of data by deriving data from prime data elements resident in a content-associative sieve
AssigneeAscava, Inc.
InventorHarshvardhan Sharangpani
Life of this patent
Estimating the term…
Abstract
This disclosure relates to lossless data reduction on large and extremely large datasets while providing high rates of data ingestion and data retrieval. Some embodiments can generate a losslessly reduced representation of a data chunk, wherein the losslessly reduced representation includes a reference to one or more prime data elements stored in a prime data store, and optionally a description of a reconstitution program which, when applied to the one or more prime data elements results in the data chunk.
Claims25
A non-transitory computer-readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method for performing lossless data reduction, the method comprising:
- identifying one or more prime data elements based on a data chunk, wherein said identifying comprises using contents of the data chunk to navigate through a data structure that organizes prime data elements based on their contents;
- determining a reconstitution program based on the data chunk and the one or more prime data elements such that the data chunk can be reconstituted by applying the reconstitution program to the one or more prime data elements;
- and
- generating a losslessly reduced representation of the data chunk, wherein the losslessly reduced representation includes a reference to each prime data element in the one or more prime data elements and a description of the reconstitution program.
A method for performing lossless data reduction, comprising:
- identifying one or more prime data elements based on a data chunk, wherein said identifying comprises using contents of the data chunk to navigate through a data structure that organizes prime data elements based on their contents;
- determining a reconstitution program based on the data chunk and the one or more prime data elements such that the data chunk can be reconstituted by applying the reconstitution program to the one or more prime data elements;
- and
- generating, by using a processor, a losslessly reduced representation of the data chunk, wherein the losslessly reduced representation includes a reference to each prime data element in the one or more prime data elements and a description of the reconstitution program.
A data storage system, comprising:
- a storage device;
- a processor;
- and
- a memory storing instructions that, when executed by the processor, cause the data storage system to perform a method comprising:
- receiving a request to write input data to a file system implemented on the storage device;
- factorizing the input data into a set of data chunks;
- and
- for at least one data chunk in the set of data chunks:
- identifying one or more prime data elements based on the data chunk, wherein said identifying comprises using contents of the data chunk to navigate through a data structure that organizes prime data elements based on their contents;
- determining a reconstitution program based on the data chunk and the one or more prime data elements such that the data chunk can be reconstituted by applying the reconstitution program to the one or more prime data elements;
- generating a losslessly reduced representation of the data chunk, wherein the losslessly reduced representation includes a reference to each prime data element in the one or more prime data elements and a description of the reconstitution program;
- and
- storing the losslessly reduced representation of the data chunk in the storage device.
Dependencies are inferred from the claim text.