HK40016528B - Method, computer-readable storage medium and electronic apparatus for reducing video data - Google Patents

Description

Methods for simplifying video data, computer-readable storage media, and electronic devices

Technical Field

This disclosure relates to data storage, retrieval, and communication. More specifically, this disclosure relates to performing multidimensional searches and content-related retrieval of data that has been losslessly simplified using basic data filtering.

Background Technology

The information age is characterized by the generation, capture, and analysis of massive amounts of data. New data arises from diverse sources, including purchase transaction records, corporate and government records and communications, emails, social media posts, digital images and videos, machine logs, signals from embedded devices, digital sensors, cellular phones, GPS satellites, space satellites, scientific computing, and Big Data. Data is generated in diverse formats, much of it unstructured and unsuitable for input into traditional databases. Businesses, governments, and individuals are generating data at an unprecedented rate and are facing challenges in storing, analyzing, and transmitting it. Hundreds of billions of dollars are spent annually on purchasing storage systems to preserve the accumulated data. Similar enormous sums are spent on computer systems used to process this data.

In the most modern computer and storage systems, data is housed and deployed across tiered storage organized into hierarchical structures. Data that requires frequent and rapid access is placed in the fastest but also most expensive tier, while most data (including copies for backup) is preferably stored in the densest and cheapest storage media. The fastest and most expensive data storage tier is the computer system's non-volatile random access memory, or RAM, which resides immediately adjacent to the microprocessor core and provides the lowest latency and highest bandwidth for random data access. Gradually denser and cheaper but also slower tiers (with progressively higher latency and lower bandwidth for random access) include non-volatile solid-state memory or flash memory, hard disk drives (HDDs), and finally, magnetic tape drives.

To more effectively store and process ever-increasing amounts of data, the computer industry has continuously improved the density and speed of data storage media, as well as the processing power of computers. However, the rate of increase in data volume far outpaces improvements in the capacity and density of computing and data storage systems. Statistics from the data storage industry in 2014 show that the new data generated and captured in the past few years constitutes a large portion of all data captured worldwide to date. The amount of data generated worldwide to date is estimated to exceed several zettabytes (one zettabyte is 10 ^{^21} bytes). This massive increase in data places high demands on data storage, computing, and communication systems that must reliably store, process, and transmit this data. This has led to increased use of lossless data simplification or compression techniques to compact data, enabling storage and equally efficient processing and transmission at lower costs.

Various lossless data reduction or compression techniques have emerged and evolved in recent years. These techniques examine data to find some form of redundancy and utilize that redundancy to simplify the data footprint without any loss of information. For a given technique that aims to utilize a specific form of redundancy in the data, the degree of data reduction achieved depends on the frequency with which that specific form of redundancy is found in the data. The desired outcome is that data reduction techniques can flexibly discover and utilize any available redundancy in the data. Because data originates from diverse sources and environments and exists in various formats, there is great interest in the development and adoption of general-purpose lossless data reduction techniques to handle this diversity. Except for the alphabet, general-purpose data reduction techniques do not require prior knowledge of the input data; therefore, they can generally be applied to any and all data without prior knowledge of the data's structure and statistical distribution characteristics.

Metrics of goodness that can be used to compare different implementations of data compression techniques include the degree of data simplification achieved on the target dataset, the efficiency of compression or simplification, and the efficiency of decompressing and retrieving data for future use. Efficiency metrics assess the performance and cost-effectiveness of a solution. Performance metrics include the throughput or ingestion rate at which new data can be consumed and simplified, the latency or time required to simplify the input data, the throughput or rate at which data can be decompressed and retrieved, and the latency or time required to decompress and retrieve the data. Cost metrics include the cost of any required dedicated hardware components, such as microprocessor cores or microprocessor utilization (central processing unit utilization), the amount of dedicated temporary memory and memory bandwidth, and the number of accesses and bandwidth required for each storage level holding the data. It should be noted that providing efficient and fast compression, decompression, and retrieval while simplifying the data footprint not only has the benefit of reducing the overall cost of storing and transmitting data but also the benefit of efficiently allowing for subsequent processing of the data.

Many general-purpose data compression techniques currently used in the industry are derived from the Lempel-Ziv compression method developed by Abraham Lempel and Jacob Ziv in 1977, see, for example, Jacob Ziv and Abraham Lempel, “A Universal Algorithm for Sequential Data Compression,” IEEE Transactions on Information Theory, Vol. IT-23, No. 3, May 1977. This method forms the basis for enabling efficient data transmission over the Internet. The Lempel-Ziv method (i.e., LZ77, LZ78, and their variants) simplifies the data footprint by replacing repeated occurrences of strings with references to previous occurrences of the string seen within a sliding window of the sequentially presented input data stream. These techniques search through all strings previously seen within the current and previous blocks up to the window length when consuming fresh strings from a given block of input data. If the fresh string is a duplicate, it is replaced with a backreference to the original string. Data simplification is achieved if the number of bytes eliminated by the duplicate string is greater than the number of bytes required for the backreference. These techniques employ various methods to search all strings seen in the window and to provide the maximum string match, including iterative scanning and a temporary bookkeeping structure that builds a dictionary containing all strings seen in the window. While consuming new input bytes to assemble a fresh string, these techniques either scan all bytes in the existing window or reference the dictionary of strings (followed by some calculations) to determine if a duplicate is found and replaced with a backreference (or to determine if the dictionary needs to be expanded).

Lempel-Ziv compression methods are often accompanied by a second optimization applied to the data, in which source symbols are dynamically recoded based on their frequency or probability of occurrence in the data block being compressed. This dynamic recoding often employs a variable-width coding scheme, using shorter codes for more frequent symbols, thus simplifying the data. For an example of this entropy-based recoding method, see David A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,” Proceedings of the IRE–Institute of Radio Engineers, September 1952, pp. 1098-1101. This technique is called Huffman recoding and typically requires a first pass through the data to calculate frequencies and a second pass through the data to actually encode the data. Several variations on this topic are also in use.

One example of using these techniques is a scheme called "Deflate," which combines the Lempel-ZivLZ77 compression method with Huffman recoding. Deflate provides a compressed streaming data format specification that defines a method for representing a sequence of bytes as (typically shorter) bit sequences, and a method for packing said bit sequences into bytes. The Deflate scheme was originally designed by Phillip W. Katz of PKWARE, Inc. for the PKZIP archiving utility. See, for example, Phillip W. Katz's U.S. Patent 5,051,745, September 24, 1991, entitled "String searcher, and compressor using same." U.S. Patent 5,051,745 describes a method for searching a symbol vector (window) for a predetermined target string (input string). The solution employs an array of pointers having pointers to each symbol in the window and uses a hashing method to filter possible positions in the window where an exact copy of the input string needs to be searched for. The next step is to scan and match strings at these locations.

The Deflate scheme is implemented in the zlib library for data compression. zlib is a software library that is a key component of several software platforms, such as Linux, Mac OSX, and iOS, as well as various game consoles. The zlib library provides Deflate compression and decompression code for use with zip (file archiving), gzip (single-file compression), png (a portable web graphics format for lossless image compression), and many other applications. zlib is now widely used for data transmission and storage. Most HTTP transactions in servers and browsers use zlib to compress and decompress data. Similar implementations are increasingly being used by data storage systems.

A paper published by Intel Corp. in April 2014, titled "High Performance ZLIB Compression on Architecture Processors," describes the compression and performance of an optimized version of the zlib library running on a contemporary Intel processor (Core i7 4770 processor, 3.4 GHz, 8 MB cache) and operating on the Calgary database. The Deflate format used in zlib sets the minimum string length for matching to 3 characters, the maximum match length to 256 characters, and the window size to 32 kilobytes. The implementation provides control over nine optimization levels, with level 9 offering the highest compression but using the most computation and performing the most exhaustive string matching, and level 1 being the fastest level employing greedy string matching. The paper reports that, using a single-threaded processor, zlib achieves a 51% compression ratio with an average clock speed of 17.66 clock cycles per byte for the input data. At a clock frequency of 3.4 GHz, this translates to an ingestion rate of 192 MB/s while fully utilizing a single processor core. The report also describes how performance rapidly drops to an ingestion rate of 38 MB/s (average 88.1 clocks/byte) when using Level 6 optimization for a modest gain in compression, and further to an ingestion rate of 16 MB/s (average 209.5 clocks/byte) when using Level 9 optimization.

Existing data compression schemes typically operate at ingestion rates ranging from 10 MB/s to 200 MB/s using a single processor core on modern microprocessors. To further improve ingestion rates, multiple cores are employed, or the window size is reduced. Using custom hardware accelerators can achieve further improvements in ingestion rates, but this increases the cost.

The existing data compression methods described above can effectively utilize short strings and fine-grained redundancy at the symbol level within a local window typically containing a single message or file, or a few files. However, these methods suffer from serious limitations and drawbacks when used in applications operating on large or extremely large datasets and requiring high data ingestion and retrieval rates.

A significant limitation is that practical implementations of these methods can only efficiently utilize redundancy within a local window. While these implementations can accept arbitrarily long input data streams, efficiency limits the size of the window in which fine-grained redundancy will be found. These methods are highly computationally intensive and require frequent and rapid access to all data within the window. String matching and lookups in various bookkeeping structures are triggered as each fresh byte (or few bytes) of input data that produces a fresh input string is consumed. To achieve the desired ingestion rate, the window used for string matching and the associated machine must reside primarily in the processor cache subsystem, thus imposing a constraint on the window size in practice.

For example, to achieve an ingestion rate of 200 MB/s on a single processor core, the average available time budget per ingested byte (including all data accesses and computations) is 5 ns, which translates to 17 clock cycles using a modern processor operating at 3.4 GHz. This budget allows for accesses to the on-chip cache (which takes a few cycles) and some subsequent string matching. Current processors have on-chip caches of several megabytes in size. Accesses to main memory take more than 200 cycles (~70 ns), so larger windows primarily residing in memory will further slow down the ingestion rate. Furthermore, as the window size increases and the distance to repeating strings increases, the cost of specifying the length of backreferences also increases, thus necessitating searching for longer string repeats over a larger area.

In most modern data storage systems, the footprint of data stored across each tier of the storage hierarchy is several orders of magnitude larger than the system's memory capacity. For example, while a system may provide hundreds of gigabytes of memory, the footprint of active data residing in flash storage can be tens of terabytes, and the total data in the storage system can range from hundreds of terabytes to several petabytes. Furthermore, for each successive tier, the achievable data access throughput for subsequent storage tiers decreases by an order of magnitude or more. When the sliding window becomes too large to fit in memory, these techniques are constrained by significantly lower bandwidth and higher latency for random I/O (input or output) access to subsequent data storage tiers.

For example, consider a file or page with 4 kilobytes of incoming data, which can be assembled from existing data by referencing, for example, 100 strings of average length 40 bytes that already exist in the data and are scattered across a 256 terabyte footprint. Each reference would take 6 bytes to specify its address and 1 byte for the string length, while potentially saving 40 bytes. While the page described in this example could be compressed more than five times, the ingestion rate corresponding to that page would be limited by the 100 or more IO accesses to the storage system required to fetch and verify 100 repeating strings (even if the location of these strings could be perfectly predicted at low cost). Using all the bandwidth of the storage system, a storage system given 250,000 random IO accesses/second (meaning 1 GB/second of random access bandwidth for a 4KB page) could only compress 2,500 such 4KB pages per second at an ingestion rate of 10 MB/second, rendering it unusable as a storage system.

Traditional compression methods with large window sizes on the order of terabytes or petabytes are hampered by reduced data access bandwidth to the storage system and are unacceptably slow. Therefore, practical implementations of these techniques can only efficiently discover and utilize redundancy if it exists locally within a window size that can be accommodated in the processor cache or system memory. If redundant data is spatially or temporally separated from the incoming data by multiple terabytes, petabytes, or exabytes, these implementations will be unable to discover redundancy at an acceptable speed due to storage access bandwidth limitations.

Another limitation of traditional methods is their unsuitability for random data access. Individual data blocks spanning the entire compressed window need to be decompressed before any group of blocks within any block can be accessed. This imposes a practical limitation on window size. Furthermore, operations traditionally performed on uncompressed data (such as search operations) cannot be efficiently performed on compressed data.

Another limitation of traditional methods (especially those based on Lempel-Ziv) is that they only search for redundancy along one dimension—that is, replacing identical strings with backreferences. The Huffman recoding scheme is limited by the fact that it requires traversing the data twice to calculate frequencies and then recoding. This becomes slow on larger blocks.

Data compression methods for detecting long duplicate strings on a global data repository use a combination of digital fingerprinting and hashing schemes. This compression process is called data deduplication. The most basic data deduplication technique breaks a file down into fixed-size blocks and searches for duplicate blocks in the data repository. If a copy of the file is created, each block in the first file will have a duplicate in the second file, and the duplicate can be replaced with a reference to the original block. To speed up the matching of potentially duplicate blocks, a hashing method is used. A hash function is a function that converts a string into a numeric value called its hash value. If two strings are equal, their hash values are also equal. Hash functions map multiple strings to a given hash value, thus simplifying long strings into much shorter hash values. Hash value matching is much faster than matching two long strings; therefore, hash value matching is performed first to filter out possible duplicate strings. If the hash value of the input string or block matches the hash value of a string or block existing in the repository, the input string can then be compared with every string in the repository that has the same hash value to confirm the existence of a duplicate.

Breaking a file into fixed-size blocks is simple and convenient, and fixed-size blocks are highly desirable in high-performance storage systems. However, this technique is limited in the amount of redundancy it can detect, meaning that these techniques achieve lower compression levels. For example, if a first file is copied to create a second file, and even if only a single byte of data is inserted into the second file, the alignment of all downstream blocks will change, the hash value of each new block will be recalculated, and the data deduplication method will no longer be able to find all duplicates.

To address this limitation in data deduplication methods, the industry has adopted fingerprinting to synchronize and align data streams at the locations of matching content. This latter approach results in fingerprint-based variable-size blocks. Michael Rabin demonstrates how it is possible to fingerprint bit strings using randomly chosen irreducible polynomials, see, for example, Michael O. Rabin's "Fingerprinting by Random Polynomials," Center for Research in Computing Technology, Harvard University, TR-15-81, 1981. In this scheme, a randomly chosen prime number p is used to fingerprint long strings by calculating the remainder of the string as a large integer modulo p. This scheme requires integer operations on £ bit integers, where k = log ₂ (p). Alternatively, a k-th degree random irreducible polynomial can be used, where the fingerprint is the polynomial representation of the data modulo a prime polynomial.

This fingerprinting method is used in data deduplication systems to identify appropriate locations where chunk boundaries should be established, allowing the system to search for duplicates of these chunks in the global repository. Chunk boundaries can be set when a fingerprint with a specific value is found. As an example of this usage, a fingerprint can be calculated for each 48-byte string of input data using a polynomial of degree 32 or lower (starting at the first byte of input and proceeding to each subsequent byte). The 13 least significant bits of the 32-bit fingerprint can then be examined, and a breakpoint is set whenever the value of these 13 bits is a predefined value (e.g., the value 1). For random data, the probability of these 13 bits having this specific value will be 1 in 2 ^{^13} , so approximately one such breakpoint might be encountered every 8KB, resulting in variable-sized chunks with an average size of 8KB. The breakpoints or chunk boundaries will effectively align to the fingerprint depending on the data content. When no fingerprint is found for a long time, a breakpoint can be forced at a predefined threshold, ensuring that the system creates chunks shorter than the predefined size for the repository. For example, see Athicha Muthitacharoen, Benjie Chen, and David Mazières, “A Low-bandwidth Network File System,” SOSP’01, Proceedings of the eighteenth ACM symposium on Operating Systems Principles, 10/21/2001, pp. 174-187.

The Rabin-Karp string matching technique, developed by Michael Rabin and Richard Karp, provides further improvements in the efficiency of fingerprint processing and string matching (see, for example, Michael O. Rabin and R. Karp, “Efficient Randomized Pattern-Matching Algorithms,” IBM Jour. of Res. and Dev., vol. 31, 1987, pp. 249-260). It should be noted that fingerprint processing methods that examine the fingerprint of an m-byte substring can evaluate the fingerprint processing polynomial function in O(m) time. Since this method would need to be applied to substrings starting with, for example, an n-byte input stream, the total workload required to perform fingerprint processing over the entire data stream would be O(n×m). Rabin-Karp identifies a hash function called rolling hash, on which the hash value of the next substring can be calculated from the previous substring by performing only a constant number of operations independent of the substring length. Therefore, after shifting one byte to the right, fingerprint calculation can be performed incrementally on the new m-byte string. This reduces the workload for fingerprint calculation to O(1) and the total workload for fingerprinting the entire data stream to O(n), thus becoming linear with the data size. This significantly speeds up fingerprint calculation and recognition.

The typical data access and computation requirements for the data deduplication methods described above can be described as follows. For a given input, once fingerprinting is complete to create a block and a hash value for that block is computed, these methods first require a set of accesses to the memory and subsequent storage tiers to search and find a global hash table that holds the hash values of all blocks in the storage. This typically requires a first I/O access to the storage. After a match is found in the hash table, a second set of storage I/Os (depending on how many blocks with the same hash value exist in the storage, this is usually one but can be more than one) is performed to retrieve the actual data block with the same hash value. Finally, a byte-by-byte match is performed to compare the input block with the retrieved potential matching blocks, thus confirming and identifying duplicates. This is followed by a third storage I/O access (to the metadata space) to replace the new duplicate block with a reference to the original block. If no match is found in the global hash table (or if no copy is found), the system requires one I/O to input the new block into the storage and another I/O to update the global hash table to input the new hash value. Therefore, for large datasets (where metadata and the global hash table cannot fit in memory and thus require storage I/O for access), such a system may require an average of three I/O operations per input block. Further improvements can be achieved by employing multiple filters, which can often detect missing data in the global hash table without requiring the first storage I/O operation to access it, thereby reducing the number of I/O operations required to process some of these blocks to two.

A storage system with 250,000 random I/O accesses per second (meaning 1 GB/s of random access bandwidth for 4KB pages) can ingest approximately 83,333 (250,000 divided by 3 I/Os per input block) of input blocks averaging 4KB in size per second and deduplicate them, allowing an ingestion rate of 333 MB/s even when the storage system's full bandwidth is utilized. If only half of the storage system's bandwidth is used (so that the other half is available for accessing the stored data), such a deduplication system can still achieve an ingestion rate of 166 MB/s. These ingestion rates are achievable (limited by I/O bandwidth) if sufficient processing power is available in the system. Therefore, given sufficient processing power, data deduplication systems can find large data duplicates across the global data scope with economical I/O and deliver data simplification at ingestion rates of hundreds of megabytes per second on modern storage systems.

Based on the foregoing description, it should be clear that while these deduplication methods are effective at finding long strings of duplicates globally, they are primarily effective at finding large duplicates. If the data changes or is modified at a finer granular level, these methods will not find usable redundancy. This significantly reduces the breadth of effective datasets for these methods. These methods have been used in specific data storage systems and applications, such as for periodic backups of data where only a few files being backed up have been modified, and the rest are duplicates of files already preserved in previous backups. Similarly, data deduplication-based systems are often deployed in environments that generate multiple exact copies of data or code, such as virtualized environments in data centers. However, as data evolves and is modified more generally or at a finer granular level, data deduplication techniques lose their effectiveness.

Some methods (often used in data backup applications) do not perform an actual byte-by-byte comparison between the input data and the string whose hash value matches the input. Such solutions rely on the low probability of collisions using strong hash functions such as SHA-1. However, due to the finite non-zero probability of collisions (where multiple different strings can map to the same hash value), such methods cannot be considered to provide lossless data simplification and therefore will not meet the high data integrity requirements of primary storage and communication.

Some approaches combine multiple existing data compression techniques. In such a setup, a global data deduplication method is typically applied first. Subsequently, on the deduplicated dataset, and using a small window approach, a Lempel-Ziv string compression method combined with Huffman recoding is applied to achieve further data simplification.

However, despite employing all known technologies to date, a gap of several orders of magnitude remains between the ever-growing and accumulating demand for data and the affordability of the world economy using the best available modern storage systems. Given the very high storage capacity requirements of the ever-growing data, there is still a need to further simplify and improve the data footprint. Methods to overcome the limitations of existing technologies or to leverage available redundancy in data along dimensions not yet addressed by current technologies still need to be developed. At the same time, the ability to efficiently access and retrieve data at acceptable speeds and processing costs remains crucial. The ability to perform efficient search operations directly on simplified data remains essential.

In summary, there has long been a need for lossless data reduction solutions that can leverage redundancy in large and massive datasets and provide high rates of data ingestion, search, and retrieval.

Summary of the Invention

The embodiments described herein are characterized by techniques and systems that can perform lossless data simplification on large and extremely large datasets while providing high data ingestion and data retrieval rates, without the defects and limitations of existing data compression systems.

Specifically, some embodiments may extract compressed moving image data and compressed audio data from video data. Next, embodiments may extract intraframes (I-frames) from the compressed moving image data. Embodiments may then losslessly simplify the I-frames to obtain losslessly simplified I-frames. Losslessly simplifying an I-frame may include, for each I-frame, (1) identifying a first set of basic data units by performing a first content association lookup on a data structure of basic data units based on the I-frame's content organization, and (2) using the first set of basic data units to losslessly simplify the I-frame. Embodiments may additionally decompress the compressed audio data to obtain a set of audio components. Next, for each audio component in the set of audio components, embodiments may (1) identify a second set of basic data units by performing a second content association lookup on a data structure of basic data units based on the audio components' content organization, and (2) using the second set of basic data units to losslessly simplify the audio component.

Some embodiments may initialize a data structure stored in a first memory device and configured to organize basic data units based on their contents. Next, the embodiments may decompose the input data into a sequence of candidate units. For each candidate unit, the embodiments may (1) identify a set of basic data units by performing a content association lookup on the data structure using the candidate unit, and (2) losslessly simplify the candidate unit using the set of basic data units, wherein if the size of the candidate unit is not sufficiently simplified, the candidate unit is added to the data structure as a new basic data unit. Next, the embodiments may store the losslessly simplified candidate units in a second memory device. When the size of one or more components of the data structure is detected to be greater than a threshold, the embodiments may (1) move one or more components of the data structure to the second memory device, and (2) initialize the one or more components of the data structure moved to the second memory device. A losslessly simplified batch of data may include (1) losslessly simplified candidate units stored on the second memory device between temporally adjacent initializations, and (2) components of the data structure moved to the second memory device between temporally adjacent initializations. In a variant, the embodiment may create a set of packages based on lossless, simplified data batches stored on a second storage device, wherein the set of packages facilitates the archiving and movement of data from one computer to another.

Some embodiments may decompose the input data into a sequence of candidate units. Next, for each candidate unit, the embodiments may (1) divide the candidate unit into one or more fields, (2) for each field, divide the field by a prime polynomial to obtain a quotient and remainder pair, (3) determine a name based on one or more quotient and remainder pairs, (4) identify a set of basic data units by performing a content association lookup on the data structure of the basic data units based on the corresponding names of the basic data units using the name pairs, and (5) simplify the candidate units without loss by using the set of basic data units.

Some embodiments may decompose the input data into a sequence of candidate units. Next, for each candidate unit, the embodiments may (1) identify a set of basic data units by performing a content association lookup on the data structure of the basic data units based on the content organization of the basic data units using the candidate units, and (2) losslessly simplify the candidate units using said set of basic data units. The embodiments may then store the losslessly simplified candidate units in a set of distillation files. Next, the embodiments may store the basic data units in a set of basic data unit files. In some embodiments, each losslessly simplified candidate unit specifies a basic data unit file for each basic data unit used to simplify the candidate unit, the basic data unit file containing the basic data unit and an offset of the location where the basic data unit can be found in the basic data unit file. In some embodiments, each distillation file stores a list of basic data unit files containing the basic data units used to losslessly simplify the candidate units stored in the distillation file.

Using a set of basic data units to losslessly simplify data units (e.g., I-frames, audio components, candidate units, etc.) may include: (1) generating a first lossless simplified representation of the data unit in response to determining that the sum of (i) the size of the references to the set of basic data units and (ii) the size of the description of the reconstruction procedure is less than a threshold proportion of the data unit size, wherein the first lossless simplified representation includes a reference to each of the basic data units in the set of basic data units and a description of the reconstruction procedure; and (2) adding the data unit as a new basic data unit in the data structure in response to determining that the sum of (i) the size of the references to the set of basic data units and (ii) the size of the description of the reconstruction procedure is greater than or equal to a threshold proportion of the data unit size, and generating a second lossless simplified representation of the data unit, wherein the second lossless simplified representation includes a reference to the new basic data unit. Note that the description of the reconstruction procedure may specify a transformation sequence that, when applied to the set of basic data units (i.e., one or more basic data units for lossless simplification of the data unit), produces the data unit.

Attached Figure Description

Figure 1A illustrates a method and apparatus for data simplification according to some embodiments described herein, which factorizes input data into individual units and derives these units from basic data units residing in a basic data filter.

Figures 1B-1G illustrate various variations of the method and apparatus shown in Figure 1A according to some embodiments described herein.

Figure 1H shows an example of the format and specification for describing the structure of distilled data according to some embodiments described herein.

Figures 1I to 1P illustrate conceptual transformations of input data into lossless simplified forms, corresponding to various variations of the methods and apparatuses for data simplification shown in Figures 1A to 1G.

Figure 2 illustrates a data simplification process according to some embodiments described herein, which involves factoring the input data into individual units and deriving these units from the basic data units residing in the basic data filter.

Figures 3A, 3B, 3C, 3D, and 3E illustrate different data organization systems that can be used to organize basic data units based on their names, according to some embodiments described herein.

Figure 3F shows the self-describing tree node data structure according to some embodiments described herein.

Figure 3G illustrates a self-describing leaf node data structure according to some embodiments described herein.

Figure 3H illustrates a self-describing leaf node data structure including a navigation look-ahead field, according to some embodiments described herein.

Figure 4 illustrates an example of how 256TB of basic data can be organized into a tree structure according to some embodiments described herein, and shows how the tree can be arranged in memory and storage devices.

Figures 5A-5C illustrate a practical example of how data can be organized using the embodiments described herein.

Figures 6A-6C respectively illustrate how a tree data structure can be used in a content association mapper described with reference to Figures 1A-1C, according to some embodiments described herein.

Figure 7A provides an example of a transformation that can be specified in the reconstruction procedure according to some embodiments described herein.

Figure 7B shows an example of the results of deriving candidate cells from basic data cells according to some embodiments described herein.

Figures 8A-8E illustrate how, according to some embodiments described herein, data simplification is implemented by factoring input data into fixed-size units and organizing said units in a tree data structure described with reference to Figures 3D and 3E.

Figures 9A-9C illustrate an example of a DataDistillation ^™ scheme based on the system shown in Figure 1C, according to some embodiments described herein.

Figure 10A provides an example of how to apply the transformations specified in the reconstruction procedure to basic data units to produce derived elements, according to some embodiments described herein.

Figures 10B-10C illustrate data retrieval processes according to some embodiments described herein.

Figures 11A-11G illustrate systems including the Data Distillation ^™ mechanism (which may be implemented using software, hardware, or a combination thereof) according to some embodiments described herein.

Figure 11H illustrates how the Data Distillation ^™ device, according to some embodiments described herein, can interface with an exemplary general-purpose computing platform.

Figure 11I illustrates how the Data Distillation ^™ device can be used for data simplification in a block processing storage system.

Figures 12A-12B illustrate the use of the Data Distillation ^™ device to transmit data over a bandwidth-constrained communication medium according to some embodiments described herein.

Figures 12C-12K illustrate the various components of simplified data generated by the Data Distillation ^™ device for various usage models according to some embodiments described herein.

Figures 12L-12R illustrate how distillation processes can be deployed and performed on a distributed system, according to some embodiments described herein, to be able to adapt to significantly larger datasets at very high ingestion rates.

Figures 13-17 illustrate how multidimensional search and data retrieval can be performed on simplified data according to some embodiments described herein.

Figures 18A-18B show block diagrams of encoders and decoders used for compressing and decompressing audio data according to the MPEG 1, Layer 3 standard (also known as MP3).

Figure 18C illustrates how to enhance the Data Distillation apparatus, first shown in Figure 1A, to simplify MP3 data.

Figure 19 illustrates how the data distillation apparatus, first shown in Figure 1A, can be enhanced to simplify video data.

Detailed Implementation

The following description is provided to enable those skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Those skilled in the art will readily recognize various modifications to the disclosed embodiments, and the general principles defined herein can be applied to other embodiments and applications without departing from the spirit and scope of the invention. Therefore, the invention is not limited to the embodiments shown, but should be accorded the broadest scope consistent with the principles and features disclosed herein. In this disclosure, when a phrase uses the term “and/or” for a set of entities, unless otherwise stated, the phrase covers all possible combinations of the set of entities. For example, the phrase “X, Y, and/or Z” covers the following combinations: “X only,” “Y only,” “Z only,” “X and Y, but no Z,” “X and Z, but no Y,” “Y and Z, but no X,” and “X, Y, and Z.”

Efficient and lossless simplification of data using basic data filtering

In some embodiments described herein, data is organized and stored to efficiently discover and utilize redundancy across the entire dataset. The input data stream is decomposed into constituent fragments or chunks called cells, and redundancy within each cell is detected and utilized at a finer granularity than the cell itself, thereby reducing the overall footprint of the stored data. A set of cells, called basic data cells, is identified and used as common shared building blocks of the dataset, and stored in a structure called a basic data repository or basic data filter. A basic data cell is simply a sequence of bits, bytes, or digits of a specific size. Depending on the implementation, basic data cells can be fixed-size or variable-size. Other constituent cells of the input data are derived from the basic data cells and are called derived cells. Thus, the input data is factored into basic data cells and derived cells.

The basic data filter sorts and organizes basic data units, allowing them to be searched and accessed according to content association. Given some input content and certain constraints, the basic data filter can be queried to retrieve the basic data units containing that content. Given an input unit, the basic data filter can be searched using the value of that unit or the value of a specific field within that unit to quickly provide a basic data unit or a small set of basic data units from which the input unit can be derived using only the minimum storage required for the specified derivation. In some embodiments, the units in the basic data filter are organized in a tree structure. Derived units are derived from basic data units by implementing transformations on them; such transformations are specified in a reconstruction procedure that describes how to generate derived units from one or more basic data units. A distance threshold specifies a limit on the size of the stored footprint of the derived unit. This threshold effectively specifies the maximum permissible distance between the derived unit and the basic data unit, and also limits the size of the reconstruction procedure that can be used to generate the derived unit.

The retrieval of exported data is achieved by performing a reconstruction procedure on one or more basic data units defined by the export.

In this disclosure, the general non-destructive data simplification technique described above may be referred to as DataDistillation ^™ processing. This processing performs a function similar to distillation in chemistry—separating a mixture into its constituent units. The basic data filter is also referred to as a filter, Data Distillation ^™ filter, or basic data repository.

In this scheme, the input data stream is factored into a sequence of units, where each unit is a basic data unit or a derived unit derived from one or more basic data units. Each unit is transformed into a lossless simplified representation, which includes references to the basic data units in the case of the basic data units, and references to one or more basic data units involved in the derivation in the case of the derived units, as well as a description of the reconstruction procedure. Therefore, the input data stream is factored into a sequence of units in the lossless simplified representation. This sequence of units (appearing in the lossless simplified representation) is called the distilled data stream or distilled data. There is a one-to-one correspondence between the sequence of units in the distilled data and the sequence of units in the input data; that is, the nth unit in the sequence of units in the distilled data corresponds to the nth unit in the sequence of units in the input data.

The general lossless data simplification technique described in this disclosure receives an input data stream and transforms it into a combination of a distilled data stream and a basic data filter, such that the sum of the footprints of the distilled data stream and the basic data filter is generally less than the footprint of the input data stream. In this disclosure, the distilled data stream and the basic data filter are collectively referred to as lossless simplified data and will be interchangeably referred to as "simplified data stream," "simplified data," or "Reduced Data." Similarly, the following terms are interchangeably used for the sequence of cells appearing in the lossless simplification format produced by the lossless data simplification technique described in this disclosure: "simplified output data stream," "simplified output data," "distilled data stream," "distilled data," and "Distilled Data."

Figure 1A illustrates a method and apparatus for data simplification according to some embodiments described herein, which factorizes input data into individual units and derives these units from basic data units residing in a basic data filter. This figure shows a general block diagram of the data simplification, or Data Distillation ^™ method and apparatus, and provides an overview of the functional components, structure, and operation. The components and/or operations shown in Figure 1A can be implemented using software, hardware, or a combination thereof.

A sequence of bytes is received from the input data stream and given as input data 102 to the data simplification device 103, also known as the Data Distillation ^™ device. A parser and factorizer 104 parse the incoming data and decompose it into chunks or candidate units. The factorizer determines where to insert interrupts in the input stream to segment the stream into candidate units. Once two consecutive interrupts are identified in the data, the parser and factorizer create candidate units 105 and give them to a basic data filter 106, also known as the Data Distillation ^™ filter.

The Data Distillation ^™ filter, or basic data filter 106, contains all basic data units (labeled PDEs in FIG. 1A) and sorts and organizes them based on their values or content. The filter provides support for two types of access. First, each basic data unit can be accessed directly by referencing its location within the filter. Second, units can be accessed in a content-associative manner using a content association mapper 121, which can be implemented in software, hardware, or a combination thereof. This second form of access to the filter is an important feature and is used by the disclosed embodiments to identify basic data units that precisely match candidate unit 105, or to identify basic data units from which candidate units can be derived. Specifically, given a candidate unit (e.g., candidate unit 105), the basic data filter 106 can be searched (based on the value of candidate unit 105 or the value of a specific field in candidate unit 105) to quickly provide a basic data unit 107 or a smaller set of basic data units 107 from which candidate units can be derived and only the minimum storage required for the specified derivation is utilized.

The filter or basic data filter 106 can be initialized using a set of basic data units whose values are distributed throughout the data space. Alternatively, according to the Data Distillation ^™ process described herein with reference to Figures 1A-1C and 2, the filter can initially be empty, and basic data units can be dynamically added to the filter as data is ingested.

The exporter 110 receives candidate units 105 and retrieved basic data units 107 suitable for export (content retrieved in association from the basic data filter 106), determines whether simplified data components 115 (consisting of references to and reconstruction procedures of the associated basic data units) can be generated from one or more candidate units 105 among these basic data units, and provides an update 114 to the basic data filter. If the candidate unit is a duplicate of the retrieved basic data unit, the exporter places a reference (or pointer) to the basic data unit located in the basic data filter in the distillation data 108, along with an indication that it is a basic data unit. If no duplicate is found, the exporter expresses the candidate unit as the result of one or more transformations performed on one or more retrieved basic data units, wherein the sequence of transformations is collectively referred to as a reconstruction procedure, such as reconstruction procedure 119A. Each export may require the exporter to construct a procedure unique to that export. The reconstruction procedure specifies transformations that can be applied to the basic data units, such as insertion, deletion, substitution, concatenation, arithmetic, and logical operations. If the footprint of the derived unit (calculated as the size of the reconstruction procedure plus the size of the references to the desired basic data unit) is within a specific specified distance threshold for the candidate unit (to allow for data simplification), the candidate unit is revised into the derived unit and replaced by a combination of the reconstruction procedure and references to (or more) related basic data units—these form the simplified data component 115 in this example. If the threshold is exceeded, or if no suitable basic data unit is retrieved from the basic data filter, the basic data filter can be instructed to install the candidate as a fresh basic data unit. In this case, the exporter places a reference to the newly added basic data unit in the distilled data, along with an indication that it is a basic data unit.

A request for data retrieval (e.g., retrieval request 109) may take the form of a reference to a location in the basic data filter containing basic data units, or, in the case of a derived item, a combination of such a reference to a basic data unit and an associated reconstruction procedure (or, in the case of a derived item based on multiple basic data units, a combination of references to multiple basic data units and an associated reconstruction procedure). By using one or more references to basic data units in the basic data filter, the retrieval unit 111 may access the basic data filter to retrieve one or more basic data units and provide the one or more basic data units and the reconstruction procedure to the reconstructor 112, which performs (as specified in the reconstruction procedure) transformations on the one or more basic data units to generate reconstructed data 116 (i.e., the requested data) and delivers it to the retrieved data output 113 in response to the data retrieval request.

In a variation of this embodiment, basic data units can be stored in the filter in a compressed form (using techniques known in the art, including Huffman coding and the Lempel Ziv method) and decompressed when needed. The advantage of this is that it simplifies the overall footprint of the basic data filter. The only constraint is that the content association mapper 121 must continue to provide content association access to the basic data units as before.

Figures 1B and 1C illustrate variations of the method and apparatus shown in Figure 1A according to some embodiments described herein. In Figure 1B, the reconstruction procedure can be stored in the basic data filter and treated as a basic data unit. A reference or pointer 119B to the reconstruction procedure is provided in the distillation data 108, rather than providing the reconstruction procedure 119A itself. Further data simplification is achieved if the reconstruction procedure is shared by other derived items, and if the storage space required for the reference or pointer to the reconstruction procedure (plus any metadata needed to distinguish between the reconstruction procedure and the reference to the reconstruction procedure) is less than that required for the reconstruction procedure itself.

In Figure 1B, the reconstruction procedure can be treated and accessed like a basic data unit and stored as a basic data unit in the basic data filter, thereby allowing content-related searches and retrieval of the reconstruction procedure from the basic data filter. During the export process used to create the export unit, once the exporter 110 determines the reconstruction procedure required for export, it can then determine whether the candidate reconstruction procedure already exists in the basic data filter, or whether the candidate reconstruction procedure can be exported from another entry already existing in the basic data filter. If the candidate reconstruction procedure already exists in the basic data filter, the exporter 110 can determine a reference to the pre-existing entry and include the reference in the distillation data 108. If the candidate reconstruction procedure can be exported from an existing entry already residing in the basic data filter, the exporter can deliver the exported item or revision of the candidate reconstruction procedure to the distillation data; that is, the exporter puts a reference to the entry pre-existing in the basic data filter along with an incremental reconstruction procedure for exporting the candidate reconstruction procedure from the pre-existing entry into the distillation data. If a candidate reconstruction procedure neither exists in the basic data filter nor can it be exported from an entry in the basic data filter, the exporter 110 can add the reconstruction procedure to the basic data filter (the operation of adding a reconstruction procedure to the filter can return a reference to the newly added entry) and include the reference to the reconstruction procedure in the distillation data 108.

Figure 1C illustrates a variation of the method and apparatus shown in Figure 1B according to some embodiments described herein. Specifically, the mechanism used to store and retrieve the reconstruction program in Figure 1C is similar to the mechanism used to store and retrieve basic data units, but the reconstruction program is maintained in a separate structure (referred to as a basic reconstruction program filter) from the structure containing the basic data units. Entries in such a structure are called basic reconstruction programs (labeled PRP in Figure 1C). Recall that the basic data filter 106 includes a content association mapper 121 that supports fast content association lookup operations. The embodiment shown in Figure 1C includes a content association mapper 122 similar to the content association mapper 121. In Figure 1C, the content association mapper 122 and the content association mapper 121 are shown as part of the basic data filter or basic data repository 106. In other embodiments, the content association mapper 122 and the reconstruction program may be stored separately from the basic data filter or basic data repository 106 in a structure called the basic reconstruction program filter.

In a variation of this embodiment, basic data units can be stored in a filter in a compressed form (using techniques known in the art, including Huffman coding and the Lempel Ziv method) and decompressed when needed. Similarly, basic reconstruction procedures can be stored in a basic reconstruction procedure filter in a compressed form (using techniques known in the art, including Huffman coding and the Lempel Ziv method) and decompressed when needed. The advantage of this is that it reduces the overall footprint of the basic data filter and the basic reconstruction procedure filter. The only constraint is that content association mappers 121 and 122 must continue to provide content association access to the basic data units and the basic reconstruction procedures as before.

Figure 1D illustrates a variation of the method and apparatus shown in Figure 1A according to some embodiments described herein. Specifically, in the embodiment described in Figure 1D, basic data units are stored inline within the distillation data. A basic data filter or basic data repository 106 continues to provide content-associated access to the basic data units and continues to logically contain them. It maintains references or links to the basic data units inline within the distillation data. For example, in Figure 1D, basic data unit 130 is inline within distillation data 108. The basic data filter or basic data repository 106 maintains a reference 131 to basic data unit 130. Similarly, in this setup, a lossless simplified representation of the derived unit will contain references to the desired basic data unit. During data retrieval, the retriever 111 retrieves the basic data unit from the location where the desired basic data unit is located.

Figure 1E illustrates a variation of the method and apparatus shown in Figure 1D according to some embodiments described herein. Specifically, in the embodiment described in Figure 1E, as shown in Figure 1B, the reconstruction procedure can be derived from other basic reconstruction procedures and is defined as an incremental reconstruction procedure plus a reference to the basic reconstruction procedure. Such basic reconstruction procedures are treated like basic data units and are logically installed in the basic data filter. Furthermore, in this configuration, both the basic data units and the basic reconstruction procedures are stored inline in the distillation data. The basic data filter or basic data repository 106 continues to provide content-associative access to the basic data units and basic reconstruction procedures and continues to logically contain these basic data units and basic reconstruction procedures while maintaining references or links to the locations of these basic data units and basic reconstruction procedures inline in the distillation data. For example, in Figure 1E, basic data unit 130 is inline in distillation data 108. Similarly, in Figure 1E, basic reconstruction procedure 132 is inline in distillation data. The basic data filter or basic data repository 106 maintains a reference 131 (i.e., Reference_to_PDE_i) to the basic data unit 130 (i.e., PDE_i) and a reference 133 (i.e., Reference_to_PDEj) to the basic reconstruction procedure 132 (i.e., Prime_Recon_Program_l). Similarly, in this setup, the lossless simplified representation of the derived unit will contain references to the desired basic data unit and the desired basic reconstruction procedure. During data retrieval, the retriever 111 obtains the desired component from its position within the corresponding distillation data.

Figure 1F shows a variation of the method and apparatus shown in Figure 1E according to some embodiments described herein. Specifically, in the embodiment described in Figure 1F, as shown in Figure 1C, the basic data filter 108 includes separate mappers—a content association mapper 121 for basic data units and a content association mapper 122 for basic reconstruction procedures.

Figure 1G illustrates a more generalized variation of the method and apparatus shown in Figures 1A to 1F. Specifically, in the embodiment described in Figure 1G, the basic data units may be located in a basic data filter or inline within the distillation data. Some basic data units may be located in the basic data filter, while others are inline within the distillation data. Similarly, the basic reconstruction procedures may be located in a basic data filter or inline within the distillation data. Some basic reconstruction procedures may be located in the basic data filter, while others are inline within the distillation data. The basic data filter logically contains all the basic data units and basic reconstruction procedures, and when a basic data unit or basic reconstruction procedure is inline within the distillation data, the basic data filter provides a reference to its location.

The foregoing description of methods and apparatus for data simplification, which factorize input data into individual units and derive these units from the basic data units residing in a basic data filter, is given for illustrative purposes only. The description is not intended to be exhaustive or to limit the invention to the disclosed forms. Therefore, many modifications and variations will occur to those skilled in the art.

Figure 1H shows an example of the format and specification of the structure of distillation data 119A in Figures 1A-1G, which describes the methods and apparatus for Data Distillation ^™ processing according to some embodiments described herein. Since Data Distillation ^™ processing factorizes input data into basic data units and derived units, a format for a lossless simplified representation of the data identifies these units in the distillation data and describes the individual components of these units. The self-describing format identifies each unit in the distillation data, indicating whether it is a basic data unit or a derived unit, and describes the individual components of that unit, namely, references to one or more basic data units mounted in a filter, references to reconstruction procedures mounted in a basic data filter (e.g., 119B in Figure 1B), or references to reconstruction procedures stored in a Basic Reconstruction Procedure (PRP) filter (e.g., 119C in Figure 1C), and inline reconstruction procedures (RPs). The Basic Reconstruction Procedure (PRP) filter is also interchangeably referred to as a Basic Reconstruction Procedure (PRP) repository. The format in Figure 1H specifies the derivation by performing reconstruction procedures on multiple basic data units, wherein the size of the derived units and each basic data unit is independently definable. The format in Figure 1H also specifies that the basic data units are inline within the distillation data rather than within the basic data filter. This is specified by opcode 7, which specifies that the type of unit is the basic data unit inline within the distillation data. The distillation data is stored in the data storage system using this format. The data in this format is consumed by the data retrieval unit 111, thereby allowing the acquisition and subsequent reconstruction of the individual components of the data.

Figures 1I to 1P illustrate conceptual transformations of input data into lossless simplified forms, corresponding to various variations of the methods and apparatuses for data simplification shown in Figures 1A to 1G. Figure 1I shows how the input data stream is factored into candidate units, and then the candidate units are treated as basic data units or derived units. Finally, the data is transformed into a lossless simplified form. Figures 1I to 1N illustrate various variations of the lossless simplified forms corresponding to the various embodiments.

Figures 1I and 1J illustrate examples of lossless simplified forms of data produced by the method and apparatus shown in Figure 1A. The lossless simplified form in Figure 1I includes a content association mapper and allows for continuous further data ingestion and simplification of the data for existing basic data units. Meanwhile, the lossless simplified form in Figure 1J no longer retains the content association mapper, resulting in a smaller data footprint. Figures 1K and 1L illustrate examples of lossless simplified forms of data produced by the method and apparatus shown in Figure 1C. The lossless simplified form in Figure 1K includes a content association mapper and allows for continuous further data ingestion and simplification of the data for existing basic data units and basic reconstruction procedures. Meanwhile, the lossless simplified form in Figure 1L no longer retains the content association mapper, resulting in a smaller data footprint.

Figures 1M and 1N illustrate examples of lossless simplified forms of data produced by the method and apparatus shown in Figure 1F, where the basic data units and basic reconstruction procedures are inlined within the distilled data. The lossless simplified form in Figure 1M includes a content association mapper and is a form that allows for continuous further data ingestion and simplification of the data for existing basic data units and basic reconstruction procedures. Meanwhile, the lossless simplified form in Figure 1N no longer retains the content association mapper, resulting in a smaller data footprint. Figures 1O and 1P illustrate examples of lossless simplified forms of data produced by the method and apparatus shown in Figure 1G, where the basic data units and basic reconstruction procedures may be inlined within the distilled data or located within a basic data filter. The lossless simplified form in Figure 1O includes a content association mapper and is a form that allows for continuous further data ingestion and simplification of the data for existing basic data units and basic reconstruction procedures. Meanwhile, the lossless simplified form in Figure 1P no longer retains the content association mapper, resulting in a smaller data footprint.

In variations of the embodiments shown in Figures 1A to 1P, the individual components of the simplified data can be further simplified or compressed using techniques known in the art (such as Huffman coding and the Lempel Ziv method), and stored in this compressed form. These components can then be decompressed when needed for use in a data distillation apparatus. The advantage of doing so is that the overall data footprint is further simplified.

Figure 2 illustrates a data simplification process according to some embodiments described herein, which involves factoring input data into individual units and deriving these units from basic data units residing in a basic data filter. As input data arrives, it can be parsed and factored or decomposed into a series of candidate units (operation 202). The next candidate unit is consumed from the input (operation 204), and a content-related lookup is performed on the basic data filter based on the content of the candidate unit to see if any suitable unit from which the candidate unit can be derived exists (operation 206). If the basic data filter does not find any such unit (the "No" branch of operation 208), the candidate unit is assigned as a new basic data unit and input into the filter, and the entry created for the candidate unit in the distilled data will be a reference to the newly created basic data unit (operation 216). If the content-related lookup on the basic data filter does indeed produce one or more suitable units from which candidate units can potentially be derived (the "Yes" branch of operation 208), analysis and computation are performed on the retrieved basic data units to derive the candidate unit. It should be mentioned that in some embodiments, metadata for appropriate basic data units is initially retrieved and analyzed on the metadata, and the appropriate basic data units are subsequently retrieved only if deemed useful (in these embodiments, the metadata for the basic data units provides some information about the content of the basic data units, thereby allowing the system to quickly exclude matches or evaluate derivability based on the metadata). In other embodiments, the basic data filter directly retrieves the basic data units (that is, metadata is not retrieved first for analysis before retrieving the basic data units), thereby performing analysis and computation on the retrieved basic data units.

A first check is performed to see if any of these units are duplicates of the candidate (operation 210). This check can be accelerated using any suitable hashing technique. If the candidate is exactly the same as the basic data unit retrieved from the basic data filter (the "yes" branch of operation 210), the entry created for the candidate unit in the distilled data is replaced by a reference to that basic data unit and an indication that the entry is the basic data unit (operation 220). If no duplicate is found (the "no" branch of operation 210), the entry retrieved from the basic data filter based on the candidate unit is considered an entry from which the candidate unit can potentially be derived. The following is an important, novel, and not obvious feature of the basic data filter: when no duplicate is found in the basic data filter, the basic data filter can return basic data units that, while not exactly the same as the candidate units, are units from which the candidate units can potentially be derived by applying one or more transformations to the basic data units(s). The process can then be performed to perform analysis and computation to derive the candidate unit from the most suitable basic data unit or a suitable set of basic data units (operation 212). In some embodiments, the derivation expresses candidate cells as the result of transformations performed on one or more basic data cells, collectively referred to as reconstruction procedures. Each derivation may require constructing its own unique procedure. In addition to constructing reconstruction procedures, the process may also calculate a distance metric that typically indicates the level of storage and/or computational resources required to reconstruct candidate cells from the revisions. In some embodiments, the footprint of the derived cell is used as a distance metric from the basic data cells(s) to the candidate—specifically, the distance metric may be defined as the size of the reconstruction procedure plus the sum of the sizes of references to one or more basic data cells involved in the derivation. The derivation with the shortest distance can be selected. The distance corresponding to that derivation is compared to a distance threshold (operation 214), and if the distance does not exceed the distance threshold, the derivation is accepted (the "yes" branch of operation 214). For data simplification, the distance threshold must always be less than the size of the candidate cell. For example, a distance threshold can be set to 50% of the candidate cell size, such that an export is only accepted if its footprint is less than or equal to half the candidate cell footprint, thus ensuring a simplification of 2x or greater for each candidate cell for which an appropriate export exists. The distance threshold can be a predetermined percentage or proportion, either based on user-defined input or selected by the system. The distance threshold can be determined by the system based on static or dynamic parameters. Once an export is accepted, the candidate cell is revised and replaced by a combination of a reconstruction procedure and references to one or more basic data cells. The entry created for the candidate cell in the distillation data is replaced by the export, that is, by an indication that this is an exported cell along with the reconstruction procedure plus references to one or more basic data cells involved in the export (operation 218). On the other hand, if the distance corresponding to the optimal export exceeds the distance threshold (the "No" branch in operation 214), no possible exports will be accepted. In this case, candidate cells can be assigned as new basic data cells and input into the filter screen, and the entries created for candidate cells in the distillation data will be references to the newly created basic data cells along with indications that this is a basic data cell (operation 216).

Finally, the process can check if there are any additional candidate units (operation 222), and if there are more candidate units, return to operation 204 (the "yes" branch of operation 222), or terminate the process if there are no more candidate units (the "no" branch of operation 222).

Several methods can be used to implement operation 202 in Figure 2, which involves parsing the incoming data and decomposing it into candidate units. The factorization algorithm needs to determine where to insert interruptions in the byte stream to segment the stream into candidate units. Possible techniques include (but are not limited to) decomposing the stream into fixed-size blocks (e.g., 4096-byte pages), applying fingerprinting methods (e.g., applying random prime polynomials to substrings of the input stream) to locate fingerprints that become unit boundaries in the data stream (this technique can result in variable-size units), or parsing the input to detect headers or some pre-declared structure and defining units based on that structure. The input can be parsed to detect specific structures declared through a schema. The input can be parsed to detect the presence of pre-declared patterns, syntax, or rule expressions in the data. Once two consecutive interruptions are identified in the data, candidate units (the data located between the two consecutive interruptions) are created and presented to a basic data filter for content-related lookup. If variable-size cells are created, the length of the candidate cells needs to be specified and carried along with the candidate cells as metadata.

A key function of basic data filtering is to provide content-related lookups based on given candidate units and to quickly provide a basic data unit or a smaller set of basic data units from which candidate units can be derived using only the minimum storage required for the specified derivation. This is a challenging problem given large datasets. Even with kilobyte-sized units, billions of units still need to be searched and selected from given terabyte-sized data. This problem becomes even more severe with even larger datasets. Therefore, it becomes crucial to organize and sort units using appropriate techniques and subsequently detect similarity and derivability within that organization to quickly provide a smaller set of appropriate basic data units.

Entries in the filter can be sorted based on the value of each cell (i.e., the basic data unit), allowing all entries to be arranged in ascending or descending order by value. Alternatively, entries can be sorted along a primary axis based on the value of a specific field within the cell, followed by a secondary axis using the rest of the cell's content. In this context, a field is a set of adjacent bytes from the cell's content. Fields can be located by applying a fingerprinting method to the cell's content, allowing the fingerprint's position to identify the field's location. Alternatively, a specific fixed offset within the cell's content can be selected to locate the field. Other methods can also be used to locate fields, including, but not limited to, parsing the cell to detect a specific declared structure and locate fields within that structure.

In another form of organization, specific fields or combinations of fields within a cell can be considered dimensions, allowing data cells to be sorted and organized using the concatenation of these dimensions and the remaining content of each subsequent cell. Generally, the correspondence or mapping between fields and dimensions can be arbitrarily complex. For example, in some embodiments, an exact field may map to an exact dimension. In other embodiments, combinations of multiple fields (e.g., F1, F2, and F3) may map to a dimension. Field combinations can be achieved by concatenating two fields or by applying any other suitable functionality to them. An important requirement is that the arrangement of the fields, dimensions, and remaining content of the cells used to organize them must allow for the unique identification of all basic data cells by their content and their sorting in a filter.

In another embodiment, a suitable function (such as an algebraic or arithmetic transformation) can be applied to the cells, wherein the function has the property that the result of the function uniquely identifies each cell. In one such embodiment, each cell is divided by a prime polynomial or a number or value of some choice, and the result of the division (which includes a quotient and remainder pair) is used as a function to organize and sort the cells in the basic data sieve. For example, the bits containing the remainder can form the leading byte of the result of the function, followed by the bits containing the quotient. Alternatively, the bits containing the quotient can be used to form the leading byte of the result of the function, followed by the bits containing the remainder. For a given divisor used to divide the input cell, the quotient and remainder pair will uniquely identify the cell, and thus the pair can be used to form the result of the function, which is used to organize and sort the cells in the basic data sieve. By applying this function to each cell, basic data cells can be organized in the sieve based on the result of the function. The function will still uniquely identify each basic data cell and will provide an alternative method for sorting and organizing basic data cells in the basic data sieve.

In another embodiment, certain suitable functions (such as algebraic or arithmetic transformations) can be applied to each field of the cell, wherein the function has the property that the result of the function uniquely identifies the field. For example, a function such as division by a suitable polynomial or number or value can be performed on consecutive fields or consecutive portions of the contents of each cell, such that a concatenation of the results of consecutive functions can be used to sort and organize cells in the basic data filter. Note that different polynomials can be used for division on each field. Each function will provide a concatenation of appropriately sorted bits based on the quotient and remainder obtained from the division operation of that portion or field. By using such a concatenation of functions applied to the fields of the cell, each basic data cell can be sorted and organized in the filter. The concatenation of functions will still uniquely identify each basic data cell and will provide an alternative method for sorting and organizing basic data cells in the basic data filter.

In some embodiments, the content of a unit can be represented as follows: Unit = Header.*sig1.*sig2.*…sigI.*…sigN.*Tail, where “Header” is a sequence of bytes including the first byte of the unit, “Tail” is a sequence of bytes including the last byte of the unit, and “sig1”, “sig2”, “sigI”, and “sigN” are signatures, patterns, rules, or byte sequences of a specific length representing the content body of the unit. The expression “.*” between the signatures is a wildcard expression, which is a rule expression tag that allows any number of intermediate bytes of any value other than the signature following the expression “.*”. In some embodiments, the N-tuple (sig1, sig2,…sigI,…sigN) is called the skeleton data structure or skeleton of the unit and can be regarded as a simplified subset or essence of the unit. In other embodiments, the (N+2)-tuple (Header, sig1, sig2,…sigI,…sigN, Tail) is called the skeleton data structure or skeleton of the unit. Alternatively, an N+1 tuple consisting of the header or tail along with the remaining signatures can be used.

Fingerprinting methods can be applied to the content of a cell to determine the location of each component (or signature) of the skeleton data structure within the cell content. Alternatively, a specific fixed offset within the cell content can be selected to locate the components. Other methods can also be used to locate the components of the skeleton data structure, including, but not limited to, parsing the cell to detect a specific declared structure and locate the components within that structure. Basic data cells can be sorted in a filter based on their skeleton data structure. In other words, the components of a cell's skeleton data structure can be considered as dimensions, allowing the basic data cells in the filter to be sorted and organized using the concatenation of these dimensions and the remaining content of each subsequent cell.

Some implementations factorize the input data into candidate units, where the size of each candidate unit is significantly larger than the size of the references required to access all such units in the global dataset. One observation regarding data decomposed into such data chunks (and accessed in a content-associative manner) is that the actual data is very sparse with respect to all possible values that can be specified by a data chunk. Consider, for example, a 1 zettabyte dataset. Approximately 70 bits are needed to address each byte in the dataset. With a chunk size of 128 bytes (1024 bits), there are approximately 2 ^{^63} chunks in a 1 zettabyte dataset, thus requiring 63 bits (less than 8 bytes) to address all chunks. It should be noted that a 1024-bit unit or chunk can have one of 2 ^{^1024} possible values, while the actual number of values for a given chunk in the dataset is at most 2 ^{^63} (if all chunks are distinct). This demonstrates that the actual data is extremely sparse with respect to the number of values that can be reached or named through the content of a single unit. This allows for the use of tree structures, which are well-suited for organizing very sparse data, enabling efficient content-based lookups, allowing new units to be added efficiently to the tree structure, and being cost-effective in terms of the incremental storage required for the tree structure itself. While there are only ²⁶³ distinct chunks in a 1 zettabyte dataset, requiring only 63 distinguishing bits to differentiate them, the relevant distinguishing bits may be scattered across the entire 1024 bits of a unit and appear in different locations for each unit. Therefore, to fully distinguish all units, simply examining the fixed 63 bits from the content is insufficient; instead, the entire unit content needs to be involved in unit sorting, especially in solutions that provide true content-based access to any and every unit in the dataset. Within the Data Distillation ^™ framework, the goal is to detect derivability within the framework used to sort and organize data. Considering all the foregoing, a content-based tree structure (which progressively distinguishes data as more content is examined) is the appropriate organization for sorting and distinguishing all units in a factorized dataset. This structure provides numerous intermediate subtree levels that can be treated as groups of derivable units or groups of units with similar derivability properties. Such a structure can be enhanced hierarchically using metadata representing each subtree or each data unit. This structure effectively conveys the composition of the entire data it contains, including the density, proximity, and distribution of actual values within the data.

Some embodiments organize basic data units in a tree structure within a filter. Each basic data unit has a unique "name" constructed from its entire content. This name is designed to uniquely identify the basic data unit and distinguish it from all other units in the tree. The name can be constructed from the content of the basic data unit in several ways. The name can simply consist of all the bytes of the basic data unit, appearing in the name in the same order they are present in the basic data unit. In another embodiment, a specific field or combination of fields, referred to as a dimension (where fields and dimensions have been described previously), is used to form the first byte of the name, and the remaining content of the basic data unit forms the rest of the name, thus ensuring that the entire content of the basic data unit contributes to creating a complete and unique name for the unit. In yet another embodiment, a field from the skeleton data structure of the unit is selected as a dimension (where fields and dimensions have been described previously) and used to form the first byte of the name, with the remaining content of the basic data unit forming the rest of the name, thus ensuring that the entire content of the basic data unit contributes to creating a complete and unique name for the unit.

In some embodiments, the name of a cell can be calculated by performing an algebraic or arithmetic transformation on the cell, while preserving the attribute that each name uniquely identifies each cell. In one such embodiment, each cell is divided by a prime polynomial or some chosen number or value, and the result of the division (i.e., the quotient and remainder pair) is used to form the cell's name. For example, the bit containing the remainder can form the leading byte of the name, followed by the bit containing the quotient. Alternatively, the bit containing the quotient can be used to form the leading byte of the name, followed by the bit containing the remainder. For a given divisor used to divide the input cell, the quotient and remainder pair will uniquely identify the cell, and thus the pair can be used to form the name of each cell. By using this representation of the name, basic data cells can be organized in a sieve based on the name of the basic data cell. The name will still uniquely identify each basic data cell and will provide an alternative method for sorting and organizing basic data cells in a basic data sieve.

In another embodiment, a variation of this name generation method (which involves division and extracting quotient/remainder pairs) can be employed, wherein division by a suitable polynomial or number or value can be performed on consecutive fields or consecutive portions of the contents of each cell, thereby producing consecutive portions of the name of each cell (each portion is a concatenation of appropriately ordered bits of the quotient and remainder obtained according to the division operation of that portion or field). Note that different polynomials can be used for division on each field. Using this representation of names, basic data cells can be organized in a filter based on their names. The names will still uniquely identify each basic data cell and will provide an alternative method for sorting and organizing basic data cells in a basic data filter.

The name of each basic data unit is used to sort and organize the basic data units in the tree. For most real-world datasets, even those that are very large (such as a 1-zeta-byte dataset consisting of ²⁵⁸ 4KB units), it is expected that a smaller subset of the names will often be used to sort and organize the majority of the basic data units in the tree.

Figures 3A, 3B, 3C, 3D, and 3E illustrate different data organization systems that can be used to organize basic data units based on their names, according to some embodiments described herein.

Figure 3A illustrates a trie data structure, where basic data units are organized into progressively smaller groups based on the values of successive bytes from each basic data unit. In the example shown in Figure 3A, each basic data unit has a unique name constructed from its entire contents, simply consisting of all the bytes of the basic data unit appearing in the same order they are present in the basic data unit. The root node of the trie represents all basic data units. The other nodes of the trie represent subsets or groups of basic data units. Starting from the root node of the trie, or level 1 (labeled root 302 in Figure 3A), basic data units are grouped into subtrees based on the value of the most significant byte of their name (labeled N1 in Figure 3A). All basic data units with the same value in the most significant byte of their name are grouped together into a common subtree, and a link indicated by that value exists from the root node to the node representing that subtree. For example, in Figure 3A, node 303 represents a subtree or group of basic data units that have the same value 2 in the most significant byte N1 of their respective names. In Figure 3A, this group includes basic data units 305, 306, and 307.

At the second level of the prefix tree, the second most significant byte of the name of each basic data unit is used to further subdivide each group of basic data units into smaller subgroups. For example, in Figure 3A, the group of basic data units represented by node 303 is further subdivided into subgroups using the second most significant byte N2. Node 304 represents a subgroup of basic data units that have a value of 2 in the most significant byte N1 of their corresponding name and a value of 1 in the second most significant byte N2. This subgroup includes basic data units 305 and 306.

The subdivision process continues at each level of the prefix tree, creating links from parent nodes to each child node, where a child node represents a subset of the basic data units represented by the parent node. This process continues until only individual basic data units remain at the leaves of the prefix tree. Leaf nodes represent groups of leaves. In Figure 3A, node 304 is a leaf node. The group of basic data units represented by node 304 includes basic data units 305 and 306. In Figure 3A, this group is further subdivided into individual basic data units 305 and 306 by using the third most significant byte of their names. A value N3 = 3 results in basic data unit 305, and a value N3 = 5 results in basic data unit 306. In this example, only 3 significant bytes from their full names are sufficient to fully identify basic data units 305 and 306. Similarly, only two significant bytes from the name are sufficient to identify basic data unit 307.

This example illustrates how, in a given mix of basic data units, only a subset of the name's bytes are used to identify the basic data unit in the tree, and the entire name is not required to reach the unique basic data unit. Furthermore, basic data units or groups of basic data units may each require a different number of valid bytes to uniquely identify them. Therefore, the depth of the prefix tree from the root node to the basic data unit can be different for different basic data units. Additionally, in the prefix tree, each node may have a different number of links descending to the subtrees below.

In such a prefix tree, each node has a name consisting of a sequence of bytes that specifies how to reach that node. For example, the name corresponding to node 304 is "21". Furthermore, the subset of bytes from the node name that uniquely identifies a node in the current node distribution within the tree is the "path" from the root node to that basic data unit. For example, in Figure 3A, path 301 with the value 213 identifies basic data unit 305.

The prefix tree structure described here can produce very deep trees (i.e., trees with many levels) because each distinguishing byte of the unit name in the tree adds one level of depth to the prefix tree.

It should be mentioned that the tree data structure in Figures 3A-3E is drawn from left to right. Therefore, as we move from the left side of the graph to the right side, we move from a higher level of the tree to a lower level. Below a given node (that is, to the right of a given node in Figures 3A-3E), for any child selected by a specific value from the distinguishing byte of the name, all cells in the respective subtrees residing below that child will have the same value in the corresponding byte of the cell name.

We will now describe a method for performing content association lookup on a prefix tree given input candidate units. This method involves navigating the prefix tree structure using the names of the candidate units, followed by subsequent analysis and filtering to determine what the structure will return as the overall content association lookup. In other words, the prefix tree navigation process returns a first result, which is then analyzed and filtered to determine the outcome of the overall content association lookup.

To initiate the prefix tree navigation process, the value of the most significant byte of the candidate unit's name is used to select a link (represented by this value) from the root node to a subsequent node, which represents a subtree of basic data units that have the same value in the most significant byte of their name. Continuing from this node, the second byte of the candidate unit's name is examined, and the link indicated by this value is selected, thus advancing to a deeper (or lower) level in the prefix tree and selecting a smaller subgroup of basic data units that now share at least two significant bytes from their name with the candidate unit. This process continues until a single basic data unit is reached, or until no link matches the value of the corresponding byte in the candidate unit's name. Under either of these conditions, the tree navigation process terminates. If a single basic data unit is reached, it can be returned as the result of the prefix tree navigation process. If not, one alternative is to report a "miss". Another alternative is to return multiple basic data units in the subtree rooted at the node where navigation terminated.

Once the prefix tree navigation process terminates, the results can be analyzed and filtered using other criteria or requirements to determine what should be returned as a result of the content association lookup. For example, when the prefix tree navigation process returns a single basic data unit or multiple basic data units, it can be additionally required that they share a specific minimum number of bytes with the name of the candidate unit before being eligible to be returned as a result of the content association lookup (otherwise, the content association lookup returns an error). Another example of a filtering requirement could be that if the prefix tree navigation process terminates without reaching a single basic data unit, thus returning multiple basic data units (rooted at the node where the prefix tree navigation terminated) as a result of the prefix tree navigation process, then these units will only be eligible to be returned as a result of the overall content association lookup if the number of said multiple basic data units is less than a specified specific limit (otherwise, the content association lookup returns an error). A combination of multiple requirements can be used to determine the result of the content association lookup. In this way, the lookup process will report an "error" or return a single basic data unit, or, if not a single basic data unit, a set of basic data units that might serve as a good starting point for deriving candidate units.

Figures 3B-3E described below relate to variations and modifications of the tree data structure shown in Figure 3A. While these variations offer improvements and advantages over the prefix tree data structure shown in Figure 3A, the processing for navigating said data structure is similar to that described earlier with reference to Figure 3A. That is, after tree navigation of the tree data structure shown in Figures 3B-3E terminates, subsequent analysis and filtering are performed to determine the results of the overall content association lookup, which returns a set of basic data units that were missed, single basic data units, or that may serve as a good starting point for deriving candidate units.

Figure 3B illustrates another data organization system that can be used to organize basic data units based on their names. In the example shown in Figure 3B, each basic data unit has a unique name constructed from its entire content, simply consisting of all the bytes of the basic data unit, which appear in the name in the same order they are present in the basic data unit. Figure 3B shows a more compact structure where a single link uses multiple bytes from the names of basic data units in the subtree below (instead of using a single byte in the prefix tree of Figure 3A) to create subdivisions or next-level groupings. Links from parent nodes to child nodes are now identified by multiple bytes. Furthermore, each link from any given parent node can use a different number of bytes to distinguish and identify the subtree associated with that link. For example, in Figure 3B, the link from the root node to node 308 is distinguished by using 4 bytes from the name ( _{N1 N2 N3 N4} = 9845), while the link from the root node to node 309 is distinguished by using 3 bytes from the name ( _{N1 N2 N3} = 347).

It should be mentioned that during tree navigation (using candidates from a given candidate unit), when reaching any parent node in the tree, the tree navigation process needs to ensure that enough bytes from the candidate unit's name are examined to definitively determine which link to choose. To select a given link, the bytes from the candidate unit's name must match all bytes indicating the transition to that particular link. Similarly, in such a tree, each node has a name consisting of a sequence of bytes specifying how to reach that node. For example, the name of node 309 could be "347" because it represents a group of basic data units (e.g., units 311 and 312) whose names begin with "347". This data pattern causes the tree navigation process to reach node 309 as shown in Figure 3B when searching the tree using candidate units whose names begin with 347. Likewise, the subset of bytes from a unit that uniquely identifies a unit within the current mix of units in the tree is the "path" from the root node to that basic data unit. For example, in Figure 3B, byte sequence 3475 results in basic data unit 312, and basic data unit 312 is uniquely identified in the basic data unit mix shown in this example.

For diverse and sparse data, it can be demonstrated that the tree structure in Figure 3B is more flexible and compact than the prefix tree structure in Figure 3A.

Figure 3C illustrates another data organization system that can be used to organize basic data units based on their names. In the example shown in Figure 3C, each basic data unit has a unique name constructed from its entire content, simply consisting of all the bytes of the basic data unit, which appear in the name in the same order they are present in the basic data unit. Figure 3C shows another variation (for the organization described in Figure 3B) that makes the tree more compact and (where necessary and/or useful) groups units in subtrees by using regular expressions to specify the values from the basic data unit names that lead to various links. Using regular expressions allows for efficient grouping of units under the same subtree that share the same expression on the corresponding bytes; this can subsequently lead to more localized disambiguation of different basic data units within a subtree. Furthermore, using regular expressions allows for a more compact description of the byte values required to map a unit to any of the subtrees below. This further reduces the number of bytes required to specify the tree. For example, rule expression 318 specifies a pattern of 28 consecutive "F"s; if this link is followed during tree navigation, we can reach unit 314, which includes pattern 320, having 28 consecutive "F"s according to rule expression 318. Similarly, the path to unit 316 has links or branches using a rule expression specifying a pattern of 16 consecutive "0"s. For such a tree, tree navigation processing needs to detect and execute such rule expressions to determine which link to select.

Figure 3D illustrates another data organization system that can be used to organize basic data units based on their names. In the example shown in Figure 3D, each basic data unit has a unique name constructed from its entire content. A fingerprinting method is applied to each unit to identify the location of a field containing the content evaluated to a selected fingerprint. The field at the location of the first fingerprint found in the unit is treated as a dimension, and a specific number of bytes from that field (e.g., x bytes, where x is significantly smaller than the number of bytes in the unit) are extracted and used as the first byte of the unit name. The remaining bytes of the name are composed of the remaining bytes of the basic data unit and appear in the same cyclic order as they exist in the basic data unit. This name is used to organize the basic data units in the tree. In this example, when no fingerprint is detected in the unit, the name is formulated simply by using all the bytes of the unit in the order they exist in the unit. A separate subtree (by an indicator showing that no fingerprint was found) maintains and organizes all such units based on their names.

As shown in Figure 3D, fingerprinting can be applied to cell 338 (which contains t bytes of data, i.e., _{B1 B2 B3} … _Bt ) to obtain the fingerprint location "fingerprint 1" at byte Bi ₊₁ , where the identifier will be selected as "dimension 1". Next, x bytes from the location identified by "fingerprint 1" can be extracted to form "dimension 1", and these x bytes can be used as the first bytes _{N1 N2} … _Nx of the name for each cell in Figure 3D. Then, tx bytes from cell 338 (starting from Bi _+x+1 and then wrapping back to _{B1 B2 B3} … _Bi ) are concatenated and used as the remaining bytes Nx ₊₁ Nx ₊₂ … _Nt of the name. When no fingerprint is found in the cell, the name _{N1 N2} … _Nt is simply _{B1 B2 B3} … _Bt from cell 338. The basic data cells are then sorted and organized in the tree using their names. For example, after traversing two levels of the tree using path 13654…06, a basic data unit (PDE) 330 is identified and reached, where byte 13654…0 is N ₁ N ₂ …N _x as bytes from dimension 1. A separate subtree at node 335, reached from the root along link 334 (by an indicator showing that no fingerprint was found), maintains and organizes all basic data units whose contents were not evaluated to the selected fingerprint. Thus, in this organization, some links (e.g., link 336) can organize units using names consisting of bytes of units appearing in the same order as in the unit, while other links (e.g., link 340) can organize units using names derived from fingerprints.

Upon receiving a candidate cell, the process applies the same techniques described above to determine the name of the candidate cell and uses that name to navigate the tree for content-related lookups. Therefore, the same and consistent processing is applied to both basic data cells (when they are installed into the tree) and candidate cells (when they are received from the parser and factorizer) to create their names. The tree navigation process uses the names of the candidate cells to navigate the tree. In this embodiment, if no fingerprint is found in a candidate cell, the tree navigation process navigates downwards along the subtree that organizes and contains basic data cells whose content has not been evaluated to a fingerprint.

Figure 3E illustrates another data organization system that can be used to organize basic data units based on their names. In the example shown in Figure 3E, each basic data unit has a unique name constructed from the entire content of that basic data unit. A fingerprinting method is applied to each unit to identify the location of a field containing content evaluated to either of two fingerprints. The field at the first occurrence of the first fingerprint in the unit (fingerprint 1 in Figure 3E) is treated as the first dimension (dimension 1), and the field at the first occurrence of the second fingerprint (fingerprint 2 in Figure 3E) is treated as the second dimension (dimension 2). Using fingerprinting to find two different fingerprints on a unit results in four possible scenarios: (1) both fingerprints are found in the unit, (2) fingerprint 1 is found but fingerprint 2 is not found, (3) fingerprint 2 is found but fingerprint 1 is not found, and (4) no fingerprint is found. Basic data units can be grouped into four subtrees corresponding to each scenario. In Figure 3E, “FP1” indicates the presence of fingerprint 1, “FP2” indicates the presence of fingerprint 2, “~FP1” indicates the absence of fingerprint 1, and “~FP2” indicates the absence of fingerprint 2.

For each of the four scenarios, the cell name is created as follows: (1) When both fingerprints are found, x bytes from the location identified by "fingerprint 1" can be extracted to form "dimension 1", and y bytes from the location identified by "fingerprint 2" can be extracted to form "dimension 2". These x+y bytes can be used as the first bytes N ₁ N ₂ …N _x+y of the name of each such cell in Figure 3E. Then, the remaining t-(x+y) bytes from cell 348 (starting after the bytes from the first dimension) are extracted in a cyclic manner and concatenated and used as the remaining bytes N _{x+y+ 1} N _x+y+2 …N _t of the name. (2) When fingerprint 1 is found but fingerprint 2 is not found, x bytes from the location identified by "fingerprint 1" can be extracted to form the preceding dimension, and these x bytes can be used as the first bytes N ₁ N ₂ …N _x of the name of each such cell. The remaining tx bytes from cell 348 (starting from Bi _+x+1 and then wrapping back _{to B1B2B3} … _Bi ) are then concatenated and used as the remaining bytes Nx _{+1Nx +2} … _Nt for the name. ( ₃ ) When fingerprint 2 is found but fingerprint 1 is not found, y bytes from the position identified by "fingerprint 2" can be extracted to form the preceding dimension, and these _y bytes can be used as the first bytes _N1N2 … _Ny for the name of each such cell. The remaining ty bytes from cell 348 (starting from Bj _+y+1 and then wrapping back to _B1B2B3 … _{Bj )} are then concatenated and used _as the remaining bytes Ny _{+1Ny +2} … _Nt for the name. (4) When no fingerprint is found in the cell, the name _{N1N2 … Nt} is simply _B1B2B3 … _{Bt from cell} 348. Therefore, each of these four cases has a separate subtree. The processing for extracting the name ( _{N1 N2 N3} … _Nt ) for unit 348 can be summarized as follows:

(1) Both fingerprint 1 and fingerprint 2 have been found:

N ₁ -N _x ←B _i+1 –B _i+x = x bytes from dimension 1

N _x+1 – _{N x+y} ← B _j+1 – _{B j+y} = y bytes from dimension 2

N _x+y+1 …N _t = the remaining bytes (from candidate units of size t bytes) = B _i+x+1 B _i+x+2 B _{i+x+ 3} ...B _j B _j+y+1 B _j+y+2 B _j+y+3 ...B _t B ₁ B ₂ B ₃ ...B _i

(2) Fingerprint 1 was found, but fingerprint 2 was not found:

N ₁ -N _x ←B _i+1 –B _i+x = x bytes from dimension 1

N _x+1 …N _t = the remaining bytes (from candidate units of size t bytes) = B _i+x+1 B _i+x+2 B _{i+x+ 3} ...B _t B ₁ B ₂ B ₃ ...B _i

(3) Fingerprint 2 was found, but fingerprint 1 was not found:

N ₁ –N _y ←B _j+1 –B _j+y = y bytes from dimension 2

N _y+1 …N _t = the remaining bytes (from candidate units of size t bytes) = B _j+y+1 B _j+y+2 B _{j+y+ 3} ...B _t B ₁ B ₂ B ₃ ...B _j

(4) No fingerprints found:

N ₁ -N _x ←B ₁ –B _t

Upon receiving a candidate unit, the processing applies the same techniques described previously to determine the name of the candidate unit. In this embodiment, the four name construction methods described previously (depending on whether fingerprint 1 and fingerprint 2 are found) are applied to the candidate unit, just as they are applied when it is input into the filter. Therefore, the same and consistent processing is applied to basic data units (when they are installed in the tree) and candidate units (when they are received from the parser and factorizer) to create their names. The tree navigation process uses the names of the candidate units to navigate the tree for content-related lookups.

If the content association lookup is successful, basic data units with the same pattern as candidate units at a specific dimension will be generated. For example, if both fingerprints are found in a candidate unit, the tree navigation process will start from the root node and proceed downwards along link 354 of the tree. If the candidate unit has the pattern "99…3" as "dimension 1" and the pattern "7…5" as "dimension 2", the tree navigation process will reach node 334. This leads to a subtree containing two basic data units (PDE 352 and PDE 353) that may be the export targets. Additional analysis and filtering are performed (by first examining the metadata and, if necessary, by subsequently acquiring and examining the actual basic data units) to determine which basic data unit is most suitable for export. Thus, the embodiments described herein identify a variety of tree structures that can be used in the filtering. Such structures or combinations of their variations can be employed to organize basic data units. Some embodiments organize basic data units in a tree form, where the entire content of the unit is used as the name of that unit. However, the sequence of bytes appearing in the unit name is not necessarily the sequence of bytes appearing in the unit. Specific fields of a cell are extracted as dimensions and used to form the first byte of its name, with the remaining bytes forming the rest of the name. These names are used to sort cells in a tree structure during filtering. The first few digits of the name are used to distinguish higher branches (or links) of the tree, and the remaining digits are used to progressively distinguish all branches (or links) of the tree. Each node in the tree can have a different number of links emanating from it. Furthermore, each link from a node can be distinguished and identified by a different number of bytes, and these bytes can be described using regular notations and other powerful methods to express their specifications. All these features result in a compact tree structure. References to the basic data units of each cell reside at the leaf nodes of the tree.

In one embodiment, a fingerprinting method can be applied to the bytes that constitute the basic data unit. A certain number of bytes residing at the location identified by the fingerprint can be used to form a component of the unit name. One or more components can be combined to provide a dimension. Multiple fingerprints can be used to identify multiple dimensions. These dimensions are concatenated and used as the first byte of the unit name, with the remaining bytes of the unit constituting the rest of the unit name. Because the dimensions are located at the location identified by the fingerprint, the likelihood of forming a name from consistent content from each unit is increased. Units with the same content value at the field located by the fingerprint will be grouped together along the same branch of the tree. In this way, similar units will be grouped together in the tree data structure. By using substitution of their names, units in which no fingerprint was found can be grouped together in separate subtrees.

In one embodiment, a fingerprinting method can be applied to the content of a cell to determine the location of the individual components (or signatures) of the skeleton data structure (described above) within the cell content. Alternatively, a specific fixed offset within the cell content can be selected to locate the components. Other methods can also be used to locate the components of the skeleton data structure of a cell, including, but not limited to, parsing the cell to detect a specific declared structure and locate the components within that structure. The individual components of the skeleton data structure can be viewed as dimensions, and the concatenation of these dimensions, along with the remaining content of each subsequent cell, is used to create a name for each cell. The names are used to sort and organize the basic data units in the tree.

In another embodiment, cells are parsed to detect specific structures within them. Specific fields within this structure are identified as dimensions. Multiple such dimensions are concatenated and used as the first byte of a name, with the remaining bytes of the cell constituting the rest of the cell name. Because the dimensions are located at positions identified by parsing the cells and detecting their structure, the likelihood of forming names from consistent content from each cell is increased. Cells with the same content value at the field located by the parsing will be grouped together along the same branch of the tree. Similarly, in this way, similar cells will be grouped together in the tree data structure.

In some embodiments, each node in the tree data structure includes a self-describing specification. A tree node has one or more children. Each child entry contains distinguishing bytes about the links to that child and a reference to that child node. Child nodes can be tree nodes or leaf nodes. Figure 3F illustrates a self-describing tree node data structure according to some embodiments described herein. The tree node data structure shown in Figure 3F specifies (A) information about the path from the root node to the tree node, including all or a subset of the following components: the actual byte sequence from the name used to reach the tree node, the number of bytes of the name consumed to reach the node from the root node, an indication of whether the number of bytes consumed is greater than a certain predefined threshold, and other metadata describing the path to the node and useful for content association searches of the tree and for decisions involving the construction of the tree, (B) the number of children the node has, and (C) for each child (where each child corresponds to a branch of the tree), specifying (1) the child ID, (2) the number of distinguishing bytes from the name required to transition down the link of the tree, (3) the actual value of the bytes from the name for the downward transition along the link, and (4) a reference to the child node.

Figure 3G illustrates a self-describing leaf node data structure according to some embodiments described herein. A leaf node has one or more children. Each child is a link to a basic data unit. Each child entry contains information about the distinguishing bytes on the link to that basic data unit, references to that basic data unit, counts of duplicates and derivations, and other metadata about that basic data unit. The leaf node data structure shown in Figure 3G specifies (A) information about the path from the root node to the leaf node, including all or a subset of the following components: the actual byte sequence from the name used to reach the leaf node, the number of bytes of the name consumed to reach the node from the root node, an indication of whether the number of bytes consumed is greater than a predefined threshold, and other metadata describing the path to the node and useful for content association searches of the tree and for decisions involving the construction of the tree, (B) the number of children the node has, and (C) for each child (where each child corresponds to the leaf node). The basic data unit below the point specifies (1) the child ID, (2) the number of distinguishing bytes from the name required to transition down the tree to a basic data unit, (3) the actual value of the bytes from the name down the branch, (4) the reference to the basic data unit that terminates the tree on the path, (5) the count of how many duplicates and derived items point to the basic data unit (this is used to determine whether an entry can be removed from the filter when deleting data in the storage system), and (6) other metadata corresponding to the basic data unit, including the size of the basic data unit, etc.

To improve the efficiency of installing fresh basic data units into the tree, some embodiments incorporate an additional field into the leaf node data structure corresponding to each basic data unit, which is maintained at the leaf nodes of the tree. It should be noted that when a fresh unit must be inserted into the tree, additional bytes of the name or content of each basic data unit in the subtree in question may be needed to determine where the fresh unit will be inserted into the subtree, or whether to trigger further subtree splitting. The need for these additional bytes may require fetching several of the basic data units in question to extract relevant distinguishing bytes about the fresh unit for each of these units. To reduce and optimize (and in some cases eliminate) the number of I/O operations required for this task, the data structure in the leaf node includes a specific number of additional bytes from the name of each basic data unit below that leaf node. These additional bytes are called navigation look-ahead bytes and help sort the basic data units about the incoming fresh units. The navigation look-ahead bytes corresponding to a given basic data unit are installed into the leaf node structure when that basic data unit is installed into the filter. The number of bytes to be reserved for this purpose can be selected statically or dynamically using various criteria, including the depth of the subtree involved and the density of basic data units within that subtree. For example, for basic data units being installed at a shallower level of the tree, the solution can add longer lookahead bytes than for basic data units residing in a very deep tree. Furthermore, additional lookahead bytes can be reserved for fresh basic data units being installed into the subtree if there are already many lookahead bytes in the existing target subtree (thus increasing the likelihood of an impending resegmentation).

Figure 3H shows the leaf node data structure corresponding to the leaf node, including the navigation look-ahead field. This data structure specifies (A) information about the path from the root node to the leaf node, including all or a subset of the following components: the actual byte sequence from the name used to reach the leaf node, the number of bytes of the name consumed to reach the node from the root node, an indication of whether the number of bytes consumed exceeds a predefined threshold, and other metadata describing the path to the node and useful for content-related searches of the tree and for decisions involving the construction of the tree, (B) the number of children the node has, and (C) for each child (where each child corresponds to a basic data unit below the leaf node), specifying (1) the child ID, (2) The number of distinguishing bytes from the successor bytes of the name required to transition down the link of the tree to a basic data unit, (3) The specification of the actual value of the bytes going down the branch, (4) The reference to the basic data unit of the tree terminating on the path of the tree, (5) The specification of how many navigation lookahead bytes to reserve for the basic data unit and the actual value of these bytes, (6) The count of how many duplicates and derived items point to the basic data unit (which is used to determine whether an entry can be removed from the filter when deleting data in the storage system), and (7) Other metadata corresponding to the basic data unit, including the size of the basic data unit, etc.

In some embodiments, the branches of the tree are used to map individual data units to groups or ranges, which are formed by interpreting the distinguishing bytes of links along the child subtrees that act as range delimiters. All units in the child subtree will have a value in the corresponding byte less than or equal to the value of the distinguishing byte specified for the link to that particular child subtree. Thus, each subtree will now represent a group of units whose values fall within a specific range. Within a given subtree, each subsequent level of the tree progressively divides the set of units into smaller ranges. This embodiment provides a different interpretation of the components of the self-describing tree node structure shown in Figure 3F. The N children in Figure 3F are ordered by the values of their distinguishing bytes in the tree node data structure and represent an ordered sequence of non-overlapping ranges. For N nodes, there are N+1 ranges, the lowest or first range consisting of values less than or equal to the smallest entry, and the N+1th range consisting of values greater than the Nth entry. The N+1th range is treated as out of range, and thus the N links lead to the N subtrees or ranges below.

For example, in Figure 3F, child 1 defines the lowest range and uses 6 bytes (with a value of abef12d6743a) to distinguish its range—the range corresponding to child 1 is from 00000000 to abef12d6743a. If the corresponding 6 bytes of a candidate cell fall within this range (including the end value), the link corresponding to that child will be selected. If the corresponding 6 starting bytes of a candidate cell are greater than the range delimiter abef12d6743a, then child 1 will not be selected. To check if a candidate cell falls within the range corresponding to child 2, two conditions must be met—first, the candidate must be outside the range of the immediately preceding child (in this case, child 1), and second, the corresponding bytes in its name must be less than or equal to the range delimiter corresponding to child 2. In this example, the range delimiter corresponding to child 2 is described by 2 bytes with a value of dcfa. Therefore, the 2 corresponding bytes corresponding to the candidate cell must be less than or equal to dcfa. Using this method, all children of the candidate unit and the tree node can be checked to determine which of the N+1 ranges the candidate unit falls into. For the example shown in Figure 3F, an error is detected if the four corresponding bytes of the candidate unit's name are greater than the value f3231929 of the distinguishing byte corresponding to the link of child N.

The tree navigation process can be modified to accommodate this new range node. Upon reaching a range node, in order to select a given link emanating from that node, the bytes from the candidate name must fall within the range defined for that particular link. If the value of the bytes from the candidate name is greater than the value of the corresponding bytes in all links, the candidate falls outside all ranges spanned by the subtree below—in this case (called an "out-of-range condition"), an error condition is detected, and the tree navigation process terminates. If the first byte of the candidate name falls within the range determined by the corresponding distinguishing bytes of the links along the guiding child subtree, tree navigation continues down to that subtree. Unless terminated due to an "out-of-range condition," tree navigation can gradually continue deeper down the tree until it reaches the leaf node data structure.

Such range nodes can be combined with the prefix tree nodes described in Figures 3A-3E and employed in the tree structure. In some embodiments, the top node of a specific number of levels in the tree structure can be a prefix tree node, where the tree traversal is based on an exact match between the first byte of the candidate cell's name and the corresponding byte along the link in the tree. Subsequent nodes can be range nodes with a tree traversal determined by the range in which the corresponding byte of the candidate cell's name falls. When the tree navigation process terminates, as described earlier in this document, multiple criteria can be used to determine what will be returned as the overall content-related lookup result.

The foregoing description of methods and apparatus for representing and using tree nodes and leaf nodes is given for illustrative purposes only. It is not intended to be exhaustive or to limit the invention to the forms disclosed. Therefore, those skilled in the art will recognize many modifications and variations.

When candidate units are given as input, the tree node and leaf node structure described above can be traversed, and a content-related lookup can be performed on the tree based on the content of the candidate units. The name of the candidate unit is constructed from its bytes, just as the name of the basic data unit is constructed from its content when the basic data unit is placed in a filter. Given input candidate units, the method of performing a content-related lookup on the tree involves navigating the tree structure using the names of the candidate units, followed by analysis and filtering to determine what will be returned as the result of the overall content-related lookup. In other words, the tree navigation process returns a first output result, which is then analyzed and filtered to determine the result of the overall content-related lookup.

If any basic data unit exists with the same name-starting bytes as the candidate (or bytes falling within the same range), the tree identifies that subset of basic data units as a subtree of units marked by links. Generally, each tree node or leaf node can store information that allows the tree navigation process to decide which outgoing link (if any) to choose to navigate to the next lower level in the tree. This information is based on the corresponding bytes of the input unit's name and the identity of the node reached while navigating the tree along the selected link. If every node contains this information, the tree navigation process can recursively navigate down each level of the tree until no match is found (at which point the tree navigation process can return a set of basic data units existing in the subtree rooted at the current node) or until a basic data unit is reached (at which point the tree navigation process can return that basic data unit along with any associated metadata).

Once the tree navigation process terminates, the results can be analyzed and filtered using other criteria and requirements to determine what should be returned as the result of the overall content association lookup. First, basic data units with the most identical starting bytes in their names to candidates can be selected. Second, when the tree navigation process returns a single or multiple basic data units, they can be additionally required to share a specific minimum number of bytes with the candidate unit's name before being eligible for return as a content association lookup result (otherwise, the content association lookup returns an error). Another example of a filtering requirement could be that if the tree navigation process terminates without reaching a single basic data unit and thus returns multiple basic data units as a result of the tree navigation process (rooted at the node where the tree navigation terminates), then these multiple basic data units will only be eligible for return as a result of the overall content association lookup if the number of these units is less than a specified limit (e.g., 4-16 units) (otherwise, the content association lookup returns an error). A combination of multiple requirements can be used to determine the result of the content association lookup. If multiple candidates remain, the navigation lookahead bytes and associated metadata can be examined to determine which basic data units are most appropriate. If it is still not possible to narrow down the selection to a single basic data unit, multiple basic data units can be provided to the export function. In this way, the lookup process will report "missed" or return a single basic data unit, or, if not a single basic data unit, a set of basic data units that may serve as a good starting point for exporting candidate cells.

Trees need to be designed for efficient content-associative access. A well-balanced tree will provide comparable access depth for most data. It is expected that the top few levels of the tree will often reside in the processor cache, the next few levels in fast memory, and subsequent levels in flash storage. For very large datasets, one or more levels may need to reside in flash storage or even on disk.

Figure 4 illustrates an example of how 256TB of basic data can be organized into a tree structure according to some embodiments described herein, and demonstrates how the tree can be arranged in memory and storage devices. Assuming each node expands to an average of 64 (2 ^{^6} ) children, a reference to a basic data unit can be accessed by reaching a leaf node data structure (e.g., depicted in Figure 3H) residing at (on average) level 6 of the tree (i.e., after 5 link traversals or jumps). Therefore, after 5 jumps, such a structure at level 6 of the tree will reside alongside another 2 ^{^30} such nodes, each with an average of 64 children (which are references to basic data units), thus accommodating approximately 64 billion basic data units. At a cell size of 4KB, this accommodates 256TB of basic data units.

The tree can be arranged such that its six levels can be traversed as follows: three levels reside in the on-chip cache (containing approximately four thousand "upper-level" tree node data structures that define the transitions to links leading to approximately 256K nodes), two levels in memory (containing 16 million "intermediate-level" tree node data structures that define the transitions to links leading to approximately one billion leaf nodes), and a sixth level in the flash memory device (containing one billion leaf node data structures). The one billion leaf node data structures of this sixth level of the tree residing in the flash memory device provide references to 64 billion basic data units (an average of 64 units per leaf node).

In the example shown in Figure 4, at levels 4 and 5, each node has an average of 16 bytes dedicated to each cell (corresponding to 1 byte for the child ID, 6 bytes for the PDE reference, plus 1 byte for byte counting, plus an average of 8 bytes for specifying the actual transition bytes and some metadata). At level 6, each leaf node has an average of 48 bytes dedicated to each cell (corresponding to 1 byte for the child ID, 1 byte for byte counting, 8 bytes for specifying the actual transition bytes, 6 bytes for the basic data unit reference, 1 byte for counting the derived items from that basic data unit, 16 bytes for navigation lookahead, 2 bytes corresponding to the size of the basic data unit, and 13 bytes for other metadata). Therefore, the total capacity required in flash storage for the tree (including references to basic data units and any metadata) is approximately 3 terabytes. The total capacity required for nodes at the top of the tree is a fraction of this size (because there are fewer nodes, fewer bytes are needed to specify more stringent references to child nodes, and less metadata is required per node). In this example, the upper tree node has an average of 8 bytes dedicated to each unit (1 byte for the child ID, 1 byte for byte counting, plus an average of 3-4 bytes to specify the actual transition bytes, and 2-3 bytes for the reference to the child node). In this example, an additional 3TB (or 1.17% of 256TB) of additional equipment is used to sort the synthetic dataset with 256TB of basic data into 1 billion groups.

In the example shown in Figure 4, the 256TB of basic data contains 64 billion 4KB basic data units. To completely distinguish these 64 billion basic data units, less than 5 bytes (or 36 bits) of address space is required. From a content association perspective, if the data mixing results in an average of 4 bytes of progressively named names being consumed in each of the first three levels and 8 bytes in each of the next three levels, a total of (average) 36 bytes (288 bits) of names would distinguish all 64 billion basic data units. These 36 bytes would be less than 1% of the 4KB that makes up each unit. If a 4KB basic data unit can be identified by 1% (or even 5-10%) of its bytes, the remaining bytes (comprising the majority of the bytes) can tolerate perturbations, and candidates with such perturbations can still reach the basic data unit and be considered for derivation from it.

It should be mentioned that (to distinguish the various subtrees below) the number of bytes required for any given link will be determined by the actual data in the mix of units that make up the dataset. Similarly, the number of links emanating from a given node will also vary with the data. The self-describing tree node and leaf node data structures will specify the actual number and value of bytes required for each link, as well as the number of links emanating from any node.

Further controls can be imposed to limit the amount of dedicated caches, memory, and storage devices at each level of the tree, so that input can be sorted into as many distinguished groups as possible within the allocated budget of incremental storage. To address situations where there are data densities and pockets requiring very deep subtrees to fully distinguish units, such densities can be handled efficiently by grouping larger sets of related units into flat groups at specific depths of the tree (e.g., level 6) and implementing streamlined search and deriving on these groups (this is done by first examining navigation looks-throughs and metadata to determine the optimal basic data units, or (as a fallback) simply looking for duplicates for the remaining data instead of full derivings provided by the method). This avoids creating very deep trees. An alternative is to allow for very deep trees (with many levels), as long as these levels can be accommodated in available memory. When deeper levels overflow to flash memory or disk, steps can be taken to flatten the tree from that level onwards, minimizing latency that would otherwise result from multiple successive accesses to tree nodes at deeper levels stored in flash memory or disk.

It is anticipated that a relatively small subset of the total bytes from the cell name will often be sufficient to identify each basic data unit. Studies implemented on various real-world datasets using the embodiments described herein confirm that a small subset of bytes from the basic data units can be used to sort most of the units, thus allowing the solution described. Therefore, such a solution is efficient in terms of the amount of storage required for its operation.

Regarding the access required for the example from Figure 4, for each incoming 4KB input block (or candidate cell), the method will require one access to query the tree structure and reach the leaf node: three cache references, two memory references (or possibly more memory references), plus a single IO from the flash memory device to access the leaf node data structure. This single IO from the memory device will retrieve a 4KB page, which will hold information corresponding to a set of approximately 64 leaf node data structures, thus including 48 bytes dedicated to the basic data unit in question. These 48 bytes will include metadata about the basic data unit in question. This will end the tree lookup process. The number of subsequent IOs required will depend on whether the candidate cell result is a duplicate, a derivation, or a fresh basic data unit to be placed in the filter.

A candidate cell that is a duplicate of a given basic data unit requires one I/O operation to retrieve that basic data unit in order to verify the duplicate. Once the duplicate is verified, another I/O operation is required to update the metadata in the tree. Therefore, the ingestion of a duplicate cell will require two I/O operations after the tree lookup, for a total of three I/O operations.

Candidate cells that do not pass a tree search and are neither duplicates nor derived items require an additional IO to store them as new basic data units in the filter, and another IO to update the metadata in the tree. Therefore, ingesting candidate cells that do not pass a tree search will require 2 IOs after the tree search, resulting in a total of 3 IOs. However, for candidate cells where the tree search process terminates without requiring storage IO, ingesting such candidate cells only requires 2 IOs.

A candidate cell that becomes a derived item (rather than a duplicate) will first require one I/O to retrieve the basic data unit needed to compute the derived item. Since the most frequent derived items are expected to originate from a single basic data unit (rather than multiple basic data units), retrieving that basic data unit will only require a single I/O. After successfully completing the derived item, one more I/O will be required to store the reconstruction procedure and derived item details in an entry created for that cell in the storage device, and another I/O will be required to update the metadata in the tree (such as counts, etc.) to reflect the new derived item. Therefore, the ingestion of a candidate cell that becomes a derived item requires three additional I/Os after the first tree lookup, for a total of four I/Os.

In summary, approximately 3 to 4 I/O operations are required to ingest candidate cells and apply the Data Distillation ^™ method to them (while globally utilizing redundancy on very large datasets). Compared to traditional data deduplication techniques, this typically requires only one additional I/O operation per candidate cell, with the added benefit of being able to globally utilize redundancy on the dataset at a finer granularity than the cell itself.

A storage system with 250,000 random I/O accesses per second (meaning 1 GB/s of random access bandwidth for 4KB pages) can ingest approximately 62,500 (250,000 divided by 4 I/Os per input block of average size 4KB) input blocks per second and apply the Data Distillation ^™ method to them. This allows an ingestion rate of 250 MB/s even when the storage system's full bandwidth is utilized. Even if only half of the storage system's bandwidth is used (so that the other half is available for accessing the stored data), such a Data Distillation ^™ system can still deliver an ingestion rate of 125 MB/s. Therefore, given sufficient processing power, a Data Distillation ^™ system can globally utilize redundancy on a dataset with economical I/O (at a finer granularity than the individual cells) and deliver data simplification at ingestion rates of hundreds of megabytes per second on modern storage systems.

Therefore, as the test results confirm, the embodiments described herein achieve the complex task of searching for cells from a large data repository (from which input cells can be derived and only the minimum storage required for the specified derive) with economical I/O access and using the minimum incremental storage required for the device. This framework, thus constructed, makes it feasible to find suitable cells for derive using a smaller percentage of all cell bytes, leaving the majority of bytes available for perturbation and derive. A key insight explaining why this approach works effectively for most data is that the tree provides an easy-to-use, fine-grained structure that allows for the location of distinguishing and differentiating bytes that identify cells within a filter, and these bytes can be efficiently isolated and stored within the tree structure, even though they reside at different depths and positions within the data.

Figures 5A-5C illustrate a practical example of how data can be organized using the embodiments described herein. Figure 5A shows 512 bytes of input data and the result of factorization (e.g., the result of implementing operation 202 in Figure 2). In this example, fingerprinting is applied to identify breaks in the data, thus making successive breaks identify candidate units. Alternating candidate units are shown using bold and regular font. For example, the first candidate unit is "b8ac83d9dc7caf18f2f2e3f783a0ec69774bb50bbe1d3ef1ef8a82436ec43283bc1c0f6a82e19c224b22f9b2", the next candidate unit is "ac83d9619ae5571ad2bbcc15d3e493eef62054b05b2dbccce933483a6d3daab3cb19567dedbe33e952a966c49f3297191cf22aa31b98b9dcd0fb54a7f761415e", and so on. As shown in the figure, the input in Figure 5A is factored into 12 variable-size candidate units. The first byte of each block is used to sort and organize the cells in the filter. Figure 5B shows how the 12 candidate cells shown in Figure 5A can be organized into basic data cells in the filter using their names and the tree structure described in Figure 3B in a tree-like manner. Each cell has a unique name constructed from the entire content of that cell. In this example, because fingerprinting is applied to determine the breaks between the 12 candidate cells, the first byte of each candidate cell will have been aligned to the anchor fingerprint: therefore, the first byte of each name will have been constructed from the first dimension of the content anchored at that fingerprint. The first bytes of the names organize the individual cells. For example, if the first byte in the cell name is equal to "0x22", the top link is taken to select basic data cell #1. It should be mentioned that different numbers of bytes are used to distinguish the individual links in Figure 5B, as explained with reference to the tree data structure shown in Figure 3B.

Figure 5C illustrates how the 12 candidate cells shown in Figure 5A can be organized using the tree data structure described with reference to Figure 3D. Fingerprinting is further applied to the content of each cell to identify a second fingerprint within the cell content. The content bytes extracted from the location of the first fingerprint (which already exists at the boundary of each cell) are concatenated with the second fingerprint to form the first byte of the name used to organize the cell. In other words, the cell name is constructed as follows: data bytes from two dimensions or fields (located respectively by the anchor fingerprint and the second fingerprint) are concatenated to form the first byte of the name, followed by the remaining bytes. As a result of this choice in name construction, (compared to Figure 5B) different byte sequences guide the various basic data cells in Figure 5C. For example, to reach basic data cell #4, the tree navigation process first obtains the link corresponding to "46093f9d" which is the first byte of the field located in the first dimension (i.e., the first fingerprint), and then obtains the link corresponding to "c4" which is the first byte of the field located in the second dimension (i.e., the second fingerprint).

Figures 6A-6C respectively illustrate how a tree data structure can be used for content association mappers 121 and 122 as described with reference to some embodiments herein.

Once the difficult problem of finding (and attempting to derive candidate cells from) suitable basic data units is solved, the problem is narrowed down to examining a basic data unit or a smaller subset of basic data units and optimally deriving candidate cells from it, utilizing only the minimum storage required for the specified deriving. Other objectives include minimizing the number of accesses to the storage system and keeping the deriving and reconstruction times acceptable.

The exporter must express candidate cells as the result of transformations performed on one or more basic data cells, and must specify these transformations as the reconstruction procedure to be used to regenerate the exported items when retrieving the data. Each export may require constructing its own unique procedure. The exporter's function is to identify these transformations and create a reconstruction procedure with a minimal footprint. Various transformations can be employed, including arithmetic, algebraic, or logical operations performed on one or more basic data cells or on specific fields of each cell. Furthermore, byte manipulation transformations such as concatenation, insertion, substitution, and deletion of bytes in one or more basic data cells can be used.

Figure 7A provides an example of transformations that can be specified in a reconstruction procedure according to some embodiments described herein. In this example, the vocabulary of transformations for the procedure includes arithmetic operations performed on fields of a specified length in the cells, and the insertion, deletion, appending, and replacement of bytes of a declared length at specified offsets in the basic data cells. The derivative can employ various techniques and operations to detect similarities and differences between candidate cells and one or more basic data cells and to construct the reconstruction procedure. The derivative can utilize a vocabulary available in the underlying hardware to implement its functionality. The end result of this work is to specify transformations in a vocabulary defined for the reconstruction procedure, and in doing so, using a minimal amount of incremental storage and in a manner that also allows for fast data retrieval.

The extractor can leverage the processing power of the underlying machine and operate within its allocated processing budget to deliver the best possible performance within the system's cost-performance constraints. Given the greater availability of microprocessor cores and the higher cost of I/O access to storage devices, the Data Distillation ^™ solution is designed to utilize the processing power of modern microprocessors to efficiently perform local analysis and derive the contents of candidate cells from a few basic data units. The performance of the Data Distillation ^™ solution (on very large datasets) is expected to be rate-limited, not by the computational processing speed, but by the I/O bandwidth of a typical storage system. For example, a few microprocessor cores are expected to be sufficient to perform the necessary computations and analysis, supporting ingestion rates of several hundred megabytes per second on a typical flash-based storage system supporting 250,000 I/O operations per second. It should be noted that two such microprocessor cores from a modern microprocessor, such as the Intel Xeon E5-2687W (10 cores, 3.1 GHz, 25 MB cache), represent only a fraction (two-tenths) of the total computational power available from the processor.

Figure 7B illustrates an example of the results of deriving candidate units from basic data units according to some embodiments described herein. Specifically, the data pattern "Elem" is a basic data unit stored in the basic data filter, and the data pattern "Cand" is a candidate unit to be derived from the basic data unit. The 18 common bytes between "Cand" and "Elem" have been highlighted. Reconstruction procedure 702 specifies how the data pattern "Cand" can be derived from the data pattern "Elem". As shown in Figure 7B, reconstruction procedure 702 shows how "Cand" is derived from "Elem" by using 1-byte replacement, 6-byte insertion, 3-byte deletion, and 7-byte batch replacement. The cost of specifying the derived item is 20 bytes + 3-byte reference = 23 bytes, which is 65.71% of the original size. It should be mentioned that the reconstruction procedure 702 shown is a human-readable representation of the procedure and may not be the way the procedure is actually stored in the embodiments described herein. Similarly, other reconstruction procedures based on arithmetic operations (such as multiplication and addition) are also shown in Figure 7B. For example, if "Elem" is bc1c0f6a790c82e19c224b22f900ac83d9619ae5571ad2bbec152054ffffff83 and "Cand" is bc1c0f6a790c82e19c224b22f91c4da1aa0369a0461ad2bbec152054ffffff83, then as shown in the figure, the multiplication (00ac83d9619ae557)*2a＝[00]1c4da1aa0369a046 can be used to derive an 8-byte difference. The cost of the derived item is specified as 4 bytes + 3 bytes of reference = 7 bytes, which is 20.00% of the original size. Alternatively, if "Elem" is bc1c0f6a790c82e19c224b22f9b2ac83ffffffffffffffffffffffffffffb283 and "Cand" is bc1c0f6a790c82e19c224b22f9b2ac830000000000000000000000000002426, then as shown in the figure, a 16-byte difference can be derived using addition, for example, by adding 0x71a3 to a 16-byte segment starting at offset 16 and discarding the carry. The cost of the derived item is specified as 5 bytes + 3 bytes reference = 8 bytes, which is 22.85% of the original size. It should be mentioned that the example encoding in Figure 7A is chosen for illustrative purposes only. The example in Figure 7B has a data size of 32 bytes, so 5 bits are sufficient for the length and offset fields within the cell. For larger units (e.g., 4KB units), the size of these fields would need to be increased to 12 bits. Similarly, the example encoding allows for reference sizes of 3 bytes or 24 bits. This should allow references to 16 million basic data units. If the reference needs to be able to address any location in, for example, 256TB of data, then the reference size would need to be 6 bytes. When such a dataset is factored into 4KB units, the 6 bytes required for the reference would be a fraction of the size of a 4KB unit.

The size of the information required to define a derived unit (derived from one or more basic data units) is the sum of the size of the reconstruction program and the reference size required for defining the one or more basic data units. The size of the information required to define a candidate unit as a derived unit is called the distance between the candidate and the basic data units. When a candidate can be feasiblely derived from any set of multiple sets of basic data units, the set of basic data units with the shortest distance is selected as the target.

When candidate cells need to be derived from more than one basic data unit (by assembling extractables derived from each of these basic data units), the exporter needs to consider the cost of additional access to the storage system and weigh that cost against the benefits of a smaller reconstruction procedure and a smaller distance. Once an optimal reconstruction procedure has been created for a candidate, its distance is compared to a distance threshold; if the threshold is not exceeded, the export is accepted. Once the export is accepted, the candidate cell is revised into an exported cell and replaced by a combination of the basic data unit and the reconstruction procedure. Entries in the distilled data created for the candidate cell are replaced by the reconstruction procedure with one or more references to the relevant basic data unit. If the distance corresponding to the optimal export exceeds the distance threshold, the exported item will not be accepted.

To achieve data simplification, the distance threshold must always be less than the size of the candidate cell. For example, the distance threshold could be set to 50% of the candidate cell size, ensuring that an item is accepted only if its footprint is less than or equal to half the candidate cell footprint, thus guaranteeing a simplification of 2x or greater for each candidate cell for which an appropriate derivative exists. The distance threshold can be a predetermined percentage or proportion, either based on user-defined input or selected by the system. The distance threshold can also be determined by the system based on static or dynamic parameters of the system.

Figures 8A-8E illustrate how data simplification is implemented according to some embodiments described herein by factoring input data into fixed-size units and organizing these units in a tree data structure described with reference to Figures 3D and 3E. Figure 8A shows how input data can be simply factored into 32-byte chunks. Specifically, Figure 8A shows the first 10 chunks, followed by several more chunks, for example, appearing after 42 million chunks. Figure 8B illustrates the organization of basic data units in a filter using names constructed such that the first byte of the name consists of content from three dimensions of the unit content (corresponding to the positions of the anchor fingerprint, second fingerprint, and third fingerprint). Specifically, in Figure 8B, each 32-byte chunk becomes a candidate unit (fixed-size block) with 32 bytes. A fingerprinting method is applied to the content of the unit. Each unit has a name constructed as follows: bytes of data from the three dimensions or fields of the unit (located by the anchor fingerprint, second fingerprint, and third fingerprint, respectively) are concatenated to form the first byte of the name, followed by the remaining bytes of the unit. The names are used to organize the units in the filter. As shown in Figure 8B, the first 10 blocks do not contain duplicates or derived items and are successively installed as units in the filter. Figure 8B shows the filter after the 10th block has been consumed. Figure 8C shows the filter contents at a subsequent point in time after consuming an additional few million units of data input (e.g., after the next 42 million blocks are presented). The filter is checked for duplicates or derived items. Blocks that cannot be derived from units are installed in the filter. Figure 8C shows the filter after consuming 42 million blocks, which, for example, contains 1,600,001 units (logically addressable using a 3-byte reference address), and the remaining 26,000,000 blocks become derived items. Figure 8D shows an example of a fresh input that is subsequently presented to the filter and identified as a duplicate entry in the filter (shown as unit number 24789). In this example, the filter identifies unit 24789 (block 9) as the most appropriate unit corresponding to block 42000011. The export function determines that the new block is an exact duplicate and replaces it with a reference to unit 24789. The cost of the exported item is 3 bytes of reference compared to the original size of 35 bytes, which is 8.57% of the original size. Figure 8D shows a second example of the input (block 42000012) of an exported item that has been converted into an entry in the filter (shown as unit number 187126). In this example, the filter determines that there is no exact match. It identifies units 187125 and 187126 (blocks 8 and 1) as the most appropriate units. A new unit is exported from the most appropriate unit. The export compared to unit 187125 and the export compared to unit 187126 are shown in Figure 8D. The cost of the derived item compared to unit 187125 is 39 bytes + 3 bytes reference = 42 bytes, which is 120.00% of the original size. The cost of the derived item compared to unit 187126 is 12 bytes + 3 bytes reference = 15 bytes, which is 42.85% of the original size. The best derived item (compared to unit 187126) is selected. The reconstructed size is compared to a threshold. For example, if the threshold is 50%, the derived item (42.85%) is accepted. Figure 8E provides two additional examples of data blocks derived from basic data units, including one example of actually creating derived items by deriving from two basic data units. Block 42000013 is given in the first example. The filter identifies unit 9299998 (block 10) as the most appropriate unit. The derived item compared to unit 9299998 is shown in Figure 8E. The cost of the derived item is 4 bytes + 3 bytes reference = 7 bytes, which is 20.00% of the original size. The reconstructed size is compared to a threshold. For example, if the threshold is 50%, the derived item (20.00%) is accepted. Block 42000014 is given in the second example. In this example, block 42000014 makes it possible for the general half of the block to be optimally derived from cell 9299997, and the other half of the block to be optimally derived from cell 9299998. Therefore, a multi-cell derived item is created to produce further data simplification. The multi-cell derived item is shown in Figure 8E. The cost of this multi-cell derived item is 3 bytes reference + 3 bytes + 3 bytes reference = 9 bytes, which is 25.71% of the original size. The reconstructed size is compared to a threshold; for example, if the threshold is 50%, the derived item (25.71%) is accepted. It should be mentioned that the best result from a single-cell derived item would be 45.71%.

Figures 8A-8E illustrate a key advantage of the Data Distillation ^™ system: the ability to efficiently implement data simplification while consuming and generating fixed-size blocks. It should be noted that fixed-size blocks are highly desirable in high-performance storage systems. By using the Data Distillation ^™ apparatus, a large incoming input file consisting of many fixed-size blocks can be factored into many fixed-size units, ensuring that all basic data units have a fixed size. Potential variable-size reconstruction procedures corresponding to each derived unit are packaged together and maintained inline within the distilled data file, which can then be chunked into fixed-size blocks. Therefore, for all practical purposes, powerful data simplification can be implemented simultaneously in the storage system while consuming and generating fixed-size blocks.

Figures 9A-9C illustrate an example of the Data Distillation ^™ scheme of the system first shown in Figure 1C: this scheme employs a separate basic reconstruction procedure filter that can be accessed via content association. This structure allows for the detection of reconstruction procedures already existing in the basic reconstruction procedure filter. Such derivatives can be modified to reference existing reconstruction procedures. This allows for the detection of redundancy within the reconstruction procedures. Input data is ingested in Figure 9A. A fingerprinting method is applied to the data, and chunk boundaries are set at fingerprint locations. As shown, the input is factored into 8 candidate units (alternating chunks are shown in bold and regular font in Figure 9A). In Figure 9B, these 8 candidate units are shown organized within the filter. Each unit has a unique name constructed from the entire content of that unit. In this example, the unit name is constructed as follows: bytes from data from two dimensions or fields (located via anchor fingerprint and second fingerprint, respectively) are concatenated to form the first byte of the name, followed by the remaining bytes. The name is used to sort the units within the filter and also provides content association access to the filter via a tree structure. Figure 9B also shows a second content association structure containing the basic reconstruction procedure. Figure 9C shows a duplicate reconstruction. Assume the incoming 55-byte candidate cell (shown in Figure 9C) is not a duplicate of any basic data cell. Cell 3 is selected as the most appropriate cell—the first two dimensions are the same for PDEs 2 and 3, but the remaining bytes starting at 88a7 match cell 3. The new input is derived from cell 3 using a 12-byte reconstruction procedure (RP). The encoding is shown in Figure 7A. It should be noted for this example that the maximum cell size is 64 bits, and all offsets and lengths are encoded as 6-bit values, instead of the 5-bit lengths and offsets shown in Figure 7A. The basic reconstruction procedure filter is searched and this new RP is not found. The RP is inserted into the basic reconstruction procedure filter and sorted based on its values. The new cell is revised to a reference to basic data cell 3 and a reference to the newly created basic reconstruction procedure at reference 4 in the basic reconstruction procedure filter. The total storage size corresponding to this derived unit is: 3 bytes PDE reference, 3 bytes RP reference, 12 bytes RP = 18 bytes, which is 31.0% of the size compared to storing it as a PDE. It is assumed that a copy of the 55-byte candidate unit arrives. As before, a 12-bit RP is created based on unit 3. The basic reconstruction procedure filter is searched, and an RP with basic RP ID = 3 and RP reference = 4 is found. This candidate unit is represented in the system as a reference to basic data unit 3 and a reference to reconstruction procedure 4. The total increased storage size for this derived unit is now: 3 bytes PDE reference, 3 bytes RP reference = 6 bytes, which is 10.3% of the size compared to storing it as a PDE.

Figure 10A provides an example of how, according to some embodiments described herein, transformations specified in the reconstruction procedure are applied to a basic data unit to produce a derived unit. This example illustrates a derived unit specified for extraction from a basic data unit numbered 187126 (also shown in the filter of Figure 8C) by applying four transformations (insertion, replacement, deletion, and appending) to that basic data unit according to the reconstruction procedure specification shown. As shown in Figure 10A, unit 187126 is loaded from the filter, and the reconstruction procedure is executed to extract block 42000012 from unit 187126. Figures 10B-10C illustrate data retrieval processing according to some embodiments described herein. Each data retrieval request essentially takes the form of a unit of distilled data and is presented to the retrieval engine in a lossless simplified format. The lossless simplified format corresponding to each unit contains references to the associated basic data unit(s) and the reconstruction procedure. The retrieval unit of the Data Distillation ^™ device acquires the basic data unit and the reconstruction procedure and provides them to the reconstructor for reconstruction. After acquiring the relevant basic data unit and reconstruction procedure corresponding to a specific unit of distillation data, the reconstructor executes the reconstruction procedure to generate the unit in its original, unsimplified form. The amount of work required for the data retrieval process to perform the reconstruction is linear with respect to the size of the reconstruction procedure and the size of the basic data unit. Therefore, a high data retrieval rate can be achieved with this system.

It is evident that to reconstruct a cell from its lossless simplified form in distilled data back to its original unsimplified form, only the basic data units(s) specified for that cell and the reconstruction procedure are required. Therefore, to reconstruct a given cell, no other cells need to be accessed or reconstructed. This makes the Data Distillation ^™ device efficient even when serving a random sequence of requests for reconstruction and retrieval. It should be noted that traditional compression methods, such as the Lempel-Ziv method, require fetching and decompressing the entire data window containing the desired block. For example, if a storage system uses the Lempel-Ziv method to compress a 4KB database with a 32KB window, then to fetch and decompress a given 4KB block, the entire 32KB window needs to be fetched and decompressed. This incurs a performance penalty because more bandwidth is required to deliver the desired data and more data needs to be decompressed. The Data Distillation ^™ device does not incur such a penalty.

Data Distillation ^™ devices can be integrated into computer systems in various ways to organize and store data efficiently by globally discovering and utilizing redundancy across the entire system. Figures 11A-11G illustrate systems incorporating Data Distillation ^™ mechanisms (which can be implemented using software, hardware, or a combination thereof) according to some embodiments described herein. Figure 11A shows a general-purpose computing platform where software applications run on system software, which executes on a hardware platform consisting of a processor, memory, and data storage components. Figure 11B shows a Data Distillation ^™ device integrated into the application layer of the platform, where each specific application uses the device to utilize redundancy within its corresponding dataset. Figure 11C shows a Data Distillation ^™ device employed to provide a data virtualization layer or services for all applications above it. Figures 11D and 11E illustrate two different forms of integration of Data Distillation ^™ devices with the operating system, file system, and data management services of an example computing platform. Other integration methods include (but are not limited to) integration with embedded computing stacks in hardware platforms, such as the embedded computing stack in a flash-based data storage subsystem as shown in Figure 11F.

Figure 11G provides additional details on the integration of the Data Distillation ^™ device with the exemplary computing platform shown in Figure 11D. Figure 11G illustrates the components of the Data Distillation ^™ device, where the parser and factorizer, derivator, retrieval unit, and reconstructor execute as software on a general-purpose processor, and the content-associative mapping structure resides at several levels of the storage hierarchy. The basic data filter can reside in a storage medium such as a flash-based storage drive.

Figure 11H illustrates how the Data Distillation ^™ device can interface with the Exemplary General Computing Platform.

A file system (or archive system) associates files (such as text documents, spreadsheets, executable files, multimedia files, etc.) with identifiers (such as filenames, file handles, etc.) and allows operations (such as reading, writing, inserting, appending, deleting, etc.) to be performed on files using the identifiers associated with them. The namespaces implemented by a file system can be flat or hierarchical. Furthermore, namespaces can be layered; for example, a top-level identifier can be resolved into one or more identifiers at successive lower levels until the top-level identifier is fully resolved. In this way, a file system provides an abstraction of the physical data storage devices and/or storage media (such as computer memory, flash drives, disk drives, network storage devices, CD-ROMs, DVDs, etc.) that physically store the file contents.

The physical storage devices and/or storage media used to store information in the file system may use one or more storage technologies and may be located in the same network location or may be distributed in different network locations. Given an identifier associated with a file and one or more operations requested to be performed on the file, the file system may (1) identify one or more physical storage devices and/or storage media, and (2) cause the physical storage devices and/or storage media identified by the file system to perform the operations requested to be performed on the file associated with the identifier.

Each time a read or write operation is performed in the system, different software and/or hardware components may be involved. The term "reader" may refer to a selection of software and/or hardware components involved in the system when a given read operation is performed, and the term "writer" may refer to a selection of software and/or hardware components involved in the system when a given write operation is performed. Some embodiments of the data simplification methods and apparatus described herein may be utilized by one or more software and/or hardware components of the system involved in performing a given read or write operation, or may be incorporated therein. Different readers and writers may utilize or incorporate different data simplification implementations. However, each writer utilizing or incorporating a particular data simplification implementation will correspond to a reader that also utilizes or incorporates the same data simplification implementation. It should be noted that some read and write operations performed in the system may not utilize or incorporate data simplification apparatus. For example, when the Data Distillation ^™ apparatus or data simplification apparatus 103 retrieves basic data units or adds new basic data units to the basic data filter, it may perform read and write operations directly without data simplification.

Specifically, in Figure 11H, the writer 150W can generally relate to the software and/or hardware components of the system involved in performing a given write operation, and the reader 150R can generally relate to the software and/or hardware components of the system involved in performing a given read operation. As shown in Figure 11H, the writer 150W provides input data to the Data Distillation ^™ device or data simplification device 103 and receives distilled data 108 from the Data Distillation ^™ device or data simplification device 103. The reader 150R provides a retrieval request 109 to the Data Distillation ^™ device or data simplification device 103 and receives the retrieved data output 113 from the Data Distillation ^™ device or data simplification device 103.

Implementation examples corresponding to Figure 11H include, but are not limited to, incorporating or utilizing the Data Distillation ^™ device or data simplification device 103 in the firmware of applications, operating system kernels, file systems, data management modules, device drivers, or flash or disk drives. This spans the various configurations and uses described in Figures 11B-11F.

Figure 11I illustrates how the Data Distillation ^™ device is used for data simplification in a block-processing storage system. In such a block-processing system, data is stored in blocks, each identified by a Logical Block Address (LBA). Blocks are constantly modified and rewritten, such that new data may be rewritten into blocks identified by a specific LBA. Each block in the system is considered a candidate unit, and the Data Distillation ^™ device can be used to simplify these candidate units into a lossless simplified form consisting of references to basic data units (stored in specific basic data unit blocks) and, in the case of derived units, references to reconstruction procedures (stored in specific reconstruction procedure blocks). Figure 11I illustrates data structure 1151, which maps the contents of blocks identified using LBAs to corresponding units in the lossless simplified form. Regarding the specification of each LBA residing in the associated unit, for systems using fixed-size blocks, it is convenient to make the incoming blocks, basic data unit blocks 1152, and reconstruction procedure blocks 1153 all fixed-size. In this system, each basic data unit can be stored as a separate block. Multiple rebuild procedures can be packaged into rebuild procedure blocks of the same fixed size. For each basic data unit and rebuild procedure, the data structure also includes a count field residing in the leaf node data structure and a reference to associated metadata, so that when a block is rewritten with new data, the previous data residing in the LBA can be effectively managed—the count field of the existing basic data unit (being rewritten) and rebuild procedure must be decremented, and similarly, the count of the basic data unit referenced by the incoming data entering the LBA must be incremented. By maintaining a reference to the count field in data structure 1151, rewriting can be managed quickly, enabling a high-performance block processing storage system that fully utilizes the data simplification provided by the Data Distillation ^™ device.

Figure 12A illustrates the use of a Data Distillation ^™ device to transmit data over a bandwidth-constrained communication medium according to some embodiments described herein. In the illustrated setup, communication node A creates a set of files to be sent to communication node B. Node A uses the Data Distillation ^™ device to convert the input files into distillation data or distillation files, which contain references to basic data units mounted in a basic data filter and a reconstruction procedure for deriving units. Node A then sends the distillation files along with the basic data filter to node B (the basic data filter can be sent before, simultaneously with, or after sending the distillation files; additionally, it can be sent through the same communication channel or through a different communication channel than the one used to send the distillation files). Node B mounts the basic data filter at the end of the corresponding structure and then feeds the distillation files through a retrieval unit and a reconstructor residing in the Data Distillation ^™ device to produce the original set of files created by node A. Thus, by using the Data Distillation ^™ device at both ends of the bandwidth-constrained communication medium to send only simplified data, the use of the medium becomes more efficient. It should be mentioned that using Data Distillation ^™ allows for the utilization of a greater range of redundancy (beyond the capabilities of traditional techniques such as Lempel-Ziv), enabling the efficient transfer of very large files or groups of files.

We will now discuss the use of Data Distillation ^™ devices in wide area network (WAN) setups where various workgroups collaborate to share data distributed across multiple nodes. When data is initially created, it can be simplified and transmitted as shown in Figure 12A. The WAN maintains a copy of the data at each site to allow for fast local access to the data. Using Data Distillation ^™ devices simplifies the footprint at each site. Furthermore, when subsequent ingestion of fresh data at any site, any redundancy between the fresh data and the existing basic data filters can be utilized to simplify the fresh data.

In such a setup, any modifications to the data at any given site need to be transmitted to all other sites to keep the basic data filters consistent across all sites. Therefore, as shown in Figure 12B, according to some embodiments described herein, updates such as the installation and deletion of basic data units, as well as metadata updates, can be transmitted to the basic data filters at each site. For example, when a fresh basic data unit is installed into a filter at a given site, that basic data unit needs to be transmitted to all other sites. Each site can access the filter in a content-associative manner using the value of that basic data unit and determine where to add the new entry to the filter. Similarly, when a basic data unit is deleted from a filter at a given site, all other sites need to be updated to reflect the deletion. One way to achieve this is by transmitting the basic data unit to all sites, allowing each site to access the filter in a content-associative manner using the basic data unit to determine which entry in the leaf node needs to be deleted, along with necessary updates to the relevant links in the tree and the deletion of the basic data unit from the filter. Another approach is to transmit to all stations a reference to the entry for the basic data unit in the leaf node where the basic data unit resides.

Therefore, Data Distillation ^™ devices can be used to simplify the footprint of data stored at various sites on a wide area network, and to make efficient use of network communication links.

Figures 12C-12K illustrate the various components of simplified data generated by the Data Distillation ^™ device for various usage models according to some embodiments described herein.

Figure 12C illustrates how the Data Distillation ^™ device 1203 ingests an input file 1201 and generates a collection of distilled files 1205 and a basic data filter or basic data repository 1206 after the distillation process is completed. The basic data filter or basic data repository 1206 of Figure 12C itself consists of two components: a mapper 1207 as shown in Figure 12D and a basic data unit (or PDE) 1208.

The mapper 1207 itself comprises two components: a set of tree node data structures defining the overall tree and a set of leaf node data structures. The set of tree node data structures can be placed in one or more files. Similarly, the set of leaf node data structures can be placed in one or more files. In some embodiments, a single file, referred to as the tree node file, holds the entire set of tree node data structures corresponding to the tree created for the basic data units of a given dataset (input file 1201), and another single file, referred to as the leaf node file, holds the entire set of leaf node data structures corresponding to the tree created for the basic data units of that dataset.

In Figure 12D, basic data unit 1208 contains a set of basic data units created for a given dataset (input file 1201). This set of basic data units can be placed in one or more files. In some embodiments, a single file, referred to as a PDE file, holds the entire set of basic data units created for the given dataset.

Tree nodes in a tree node file will contain references to other tree nodes within the file. The deepest (or lowest) level tree node in a tree node file will contain references to entries in the leaf node data structure of the leaf node file. Entries in the leaf node data structure of the leaf node file will contain references to the basic data units in the PDE file.

Figure 12E illustrates the tree node file, leaf node file, and PDE file, showing details of all components created by the device. Figure 12E shows an input file set 1201 comprising N files named file1, file2, file3…fileN, which are simplified by the Data Distillation ^™ device to produce a distillation file set 1205 and the various components of the basic data filter, namely the tree node file 1209, leaf node file 1210, and PDE file 1211. Distillation file 1205 comprises N files named file1.dist, file2.dist, file3.dist…fileN.dist. The Data Distillation ^™ device factorizes the input data into its constituent units and creates two categories of data units—basic data units and derived units. The distillation file contains a description of the data units in a lossless simplified format and includes references to the basic data units in the PDE file. Each file in input file 1201 has a corresponding distillation file in distillation file 1205. For example, file1 1212 in input file 1201 corresponds to the distillation file named file1.dist 1213 in distillation file 1205. Figure 12R shows an alternative representation of an input dataset that is specified as a set of input files and directories or folders.

It should be noted that Figure 12E illustrates the various components created by the data distillation apparatus based on the organization of distillation data and a basic data filter according to Figure 1A, wherein the reconstruction procedure is placed in a non-destructive simplified representation of a cell in the distillation file. It should be noted that in some embodiments (according to Figure 1B), the reconstruction procedure can be placed in the basic data filter and treated as a basic data cell. The non-destructive simplified representation of a cell in the distillation file will contain references to the reconstruction procedure in the basic data filter (rather than containing the reconstruction procedure itself). In these embodiments, the reconstruction procedure will be treated as a basic data cell and generated in PDE file 1211. In another embodiment, according to Figure 1C, the reconstruction procedure is stored separately from the basic data cell and is stored in a structure called a reconstruction procedure repository. In such an embodiment, the non-destructive simplified representation of a cell in the distillation file will contain references to the reconstruction procedure in the reconstruction procedure repository. In such an embodiment, as shown in FIG12F, in addition to generating tree node files 1209, leaf node files 1210 and PDE files 1211 corresponding to the tree organization of basic data units, the apparatus will also generate a second set of tree and leaf node files called reconstructed tree node files 1219 and reconstructed leaf node files 1220, together with a file called RP file 1221 containing all reconstruction procedures.

The Data Distillation ^™ device shown in Figure 12E also stores configuration and control information that manages its operation in one or more of the tree node file 1209, leaf node file 1210, PDE file 1211, and distillation file 1205. Alternatively, a fifth component containing this information can be generated. Similarly, for the device shown in Figure 12F, the configuration and control information can be stored in one or more of the components shown in Figure 12F, or it can be stored in another component generated for this purpose.

Figure 12G shows an overview of the use of the Data Distillation ^™ device, where a given dataset (input file 1221) is fed to the Data Distillation ^™ device 1203 and processed to produce a lossless simplified dataset (lossless simplified dataset 1224). The input dataset 1221 can consist of files, objects, chunks, groups, or a selection of extracts from a data stream. It should be noted that Figure 12E shows an example where the dataset consists of files. The input dataset 1221 of Figure 12G corresponds to the input file 1201 of Figure 12E, and the lossless simplified dataset 1224 of Figure 12G includes the four components shown in Figure 12E: the distillation file 1205, the tree node file 1209, the leaf node file 1210, and the PDE file 1211 of Figure 12E. In Figure 12G, the Data Distillation ^™ device utilizes redundancy across the entire range of data units in the given input dataset.

The Data Distillation ^™ apparatus can be configured to utilize redundancy within a subset of the input dataset and provide lossless simplification corresponding to each given subset of data. For example, as shown in Figure 12H, the input dataset 1221 can be divided into a number of smaller data selections, each selection referred to herein as a “batch” or “data batch”. Figure 12H illustrates a Data Distillation ^™ apparatus configured to ingest input data batches 1224 and generate lossless simplified data batches 1225. Figure 12H shows that the input dataset 1221 consists of several data selections, namely data batch 1…data batch i…data batch n. Data is presented to the Data Distillation ^™ apparatus one data batch at a time, and redundancy within the range of each data batch is utilized to generate lossless simplified data batches. For example, data batch i1226 from the input dataset 1221 is fed to the apparatus, and lossless simplified data batch i1228 is delivered to lossless simplified dataset 1227. Each data batch from input dataset 1221 is fed into the device, and the corresponding lossless simplified data batch is delivered to lossless simplified dataset 1227. After consuming and simplifying all data batches 1...data batch i...data batch n, input dataset 1221 is simplified to lossless simplified dataset 1227.

While the Data Distillation ^™ device is already highly efficient in utilizing redundancy across the entire data range, the aforementioned techniques can be used to further accelerate data simplification and improve its efficiency. Throughput of data simplification can be increased by limiting the size of data batches to fit within the system's available memory. For example, an input dataset of many terabytes or even petabytes in size can be broken down into multiple data batches, each of which can be rapidly simplified. In our lab, we have implemented such a solution utilizing redundancy within the 256GB range using a single processor core (Intel Xeon E5-1650 V3, Haswell 3.5GHz processor) with 256GB of memory, achieving data ingestion rates of several hundred megabytes per second while delivering 2-3x simplification levels across a variety of datasets. It should be noted that 256GB is millions of times larger than 32KB, and 32KB is the window size within which the Lempel Ziv method delivers ingestion performance between 10MB/s and 200MB/s on current processors. Therefore, improvements in the speed of data distillation processing can be achieved by appropriately limiting the scope of redundancy and potentially sacrificing some simplification.

Figure 12I illustrates a variation of the setup in Figure 12H and shows multiple data distillation processes running on multiple processors to significantly improve the throughput of data simplification (and data reconstruction/retrieval) of the input dataset. Figure 12I shows an input dataset 1201 divided into x data batches, which are fed into j independent processes running on independent processor cores (each process is allocated sufficient memory to accommodate any data batches to be fed there) for parallel execution, resulting in an approximately j-fold speedup for both data simplification and reconstruction/retrieval.

Figure 12H illustrates a Data Distillation ^™ apparatus configured to ingest input data batches 1224 and produce lossless simplified data batches 1225. Figure 12H shows that the input dataset 1221 consists of multiple data selections, namely data batch 1…data batch i…data batch n. In some embodiments, an alternative partitioning scheme can be employed to divide the input dataset into multiple data batches, wherein the data batch boundaries are dynamically determined to best utilize available memory. Available memory can be used to store all tree nodes first, or it can be used to store all tree nodes and all leaf nodes of the data batch, or it can be used last to store all tree nodes, leaf nodes, and all basic data units. These three different options allow the apparatus to have alternative operating points. For example, dedicating available memory to tree nodes allows a larger range of data to be accommodated in the data batch, but this requires the apparatus to retrieve leaf nodes and associated basic data units from the storage device when needed, resulting in additional latency. Alternatively, dedicating available memory to both tree nodes and leaf nodes speeds up the distillation process but reduces the effective size of the tree, thereby reducing the range of data that can be accommodated in the data batch. Finally, using available memory to hold all tree nodes, leaf nodes, and basic data units will achieve the fastest distillation, but will also minimize the size of the data batches that can be supported as a single range. In all these embodiments, data batches will be dynamically shut down when memory limits are reached, and subsequent files from the input dataset will become part of new data batches.

Further improvements exist that can increase the efficiency of the device and accelerate the reconstruction process. In some embodiments, a single unified mapper is used for distillation, but instead of keeping the basic data units in a single PDE file, the basic data units are kept across N PDE files. Thus, the previously single PDE file is divided into n PDE files, each smaller than a certain threshold size, and each partition is created during the distillation process as the PDE file exceeds that threshold size (due to the growth caused by the mounting of the basic data units). Each input file is distilled by consulting the mapper to content-relatedally select the appropriate basic data units suitable for export, and then exporting the appropriate basic data units obtained from the appropriate PDE file in which they reside. Each distillation file is further enhanced to list all PDE files (out of the n PDE files) that contain the basic data units referenced by the specific distillation file. Only those listed PDE files will need to be loaded or opened to be accessed for reconstruction in order to reconstruct a specific distillation file. The advantage of this approach is that, for the reconstruction of a single or a few distillation files, only those PDE files containing the essential data units required for that specific distillation file need to be accessed or kept active, while other PDE files do not need to be retained or loaded into a fast memory or storage device layer. Therefore, reconstruction can be faster and more efficient.

Partitioning a PDE file into n PDE files can also be guided by a standard that localizes the reference patterns of the underlying data during the simplification of any given file in the dataset. The device can be enhanced by a counter that counts and estimates the density of references to cells in the current PDE file. If this density is high, the PDE file will not be partitioned or split and will continue to grow with subsequent cell installations. Once the reference density in a given distillation file gradually decreases, the PDE file can be allowed to be split and partitioned if subsequent growth exceeds a certain threshold. Once partitioned, a new PDE file will be opened, and subsequent installations from subsequent distillations will be performed in that new PDE file. This arrangement will further accelerate reconstruction if only a subset of files in the data batch needs to be reconstructed.

Figure 12J illustrates the components of simplified data generated by the Data Distillation ^™ device for a usage model where the mapper is no longer needed after simplification of the input dataset. An example of such a usage model is a particular type of data backup and data archiving application. In such a usage model, subsequent use of the simplified data involves reconstructing and retrieving the input dataset from the simplified dataset. In this case, the footprint of the simplified data can be further simplified by not storing the mapper after data simplification is complete. Figure 12J shows the input file 1201 fed to the device, resulting in a distillation file 1205 and a PDE file 1211—these components constitute the simplified data in this scenario. It should be noted that the input file 1201 can be completely regenerated and restored using only the distillation file 1205 and the PDE file 1211. Recall that the lossless simplified representation corresponding to each unit in the distillation file contains the reconstruction procedure (if needed) and references to the basic data units in the PDE file. Coupled with the PDE file, this is all the information needed to perform the reconstruction. It should also be noted that this arrangement has significant benefits for the performance efficiency of reconstructing and retrieving the input dataset. In this embodiment, the apparatus decomposes the input dataset into distillation files and basic data units contained in separate PDE files. During reconstruction, the PDE files can be loaded from storage into available memory first, and then the distillation files can be read sequentially from storage for reconstruction. During the reconstruction of each distillation file, any basic data units required to reconstruct the distillation file are quickly retrieved from memory without any additional storage access latency caused by reading basic data units. The reconstructed distillation files can be written to storage when they are complete. This arrangement eliminates the need for random memory accesses, which would otherwise have a detrimental impact on performance. In this solution, the load from the PDE files of storage is a set of accesses to sequential, consecutive blocks of bytes, the read of each distillation file is also a set of accesses to sequential, consecutive blocks of bytes, and finally each reconstructed input file is written to storage as an access to a set of sequential, consecutive blocks of bytes. The storage performance of this arrangement more closely follows the performance of sequentially reading and writing consecutive blocks of bytes, rather than the performance of solutions that cause multiple random memory accesses.

It should be mentioned that Figure 12J illustrates the various components created by the data distillation apparatus based on the organization of distillation data and a basic data filter according to Figure 1A, wherein the reconstruction procedure is placed in a non-destructive simplified representation of the cell in the distillation file. It should be mentioned that in some embodiments (according to Figure 1B), the reconstruction procedure can be placed in the basic data filter and treated as a basic data cell. The non-destructive simplified representation of the cell in the distillation file will contain references to the reconstruction procedure in the basic data filter (rather than containing the reconstruction procedure itself). In these embodiments, the reconstruction procedure will be treated as a basic data cell and generated in PDE file 1211. In another embodiment, according to Figure 1C, the reconstruction procedure is stored separately from the basic data cell and is stored in a structure called a reconstruction procedure repository. In such an embodiment, the non-destructive simplified representation of the cell in the distillation file will contain references to the reconstruction procedure in the reconstruction procedure repository. In such an embodiment, in addition to generating a PDE file corresponding to the basic data cell, the apparatus will also generate a file called an RP file containing all the reconstruction procedures. This is illustrated in Figure 12K, which shows the simplified data components for a usage model where the mapper is no longer needed. Figure 12K shows the simplified data components including distillation file 1205, PDE file 1211, and RP file 1221.

Figures 12L-12P illustrate how, according to some embodiments described herein, a distillation process can be deployed and executed on a distributed system to accommodate very large datasets at very high ingestion rates.

Distributed computing paradigms require the distributed processing of large datasets through programs running on multiple computers. Figure 12L illustrates multiple computers networked together in an organization known as a distributed computing cluster. Figure 12L shows point-to-point links between computers; however, it will be understood that any communication topology (e.g., hub-and-spoke or mesh topology) can be used instead of the topology shown in Figure 12L. In a given cluster, a node is designated as the master node, which assigns tasks to slave nodes and controls and coordinates the entire operation. Slave nodes execute tasks according to the master node's instructions.

Data distillation can be performed in a distributed manner across multiple nodes in a distributed computing cluster to utilize the combined computing, memory, and storage capacity of the multiple computers in the cluster. In this setup, the master distillation module on the master node interacts with slave distillation modules running on slave nodes to perform data distillation in a distributed manner. To facilitate this distribution, the basic data filters of the apparatus can be divided into multiple independent subsets or subtrees, which can be distributed across multiple slave modules running on slave nodes. Recall that in a data distillation apparatus, basic data units are organized in a tree structure based on their names, and their names are derived from their contents. The basic data filters can be divided into multiple independent subsets or sub-filters based on the leading byte of the unit name in the basic data filters. There are various methods to partition the namespace across multiple subtrees. For example, the value of the leading byte of the unit name can be divided into multiple subranges, and each subrange can be assigned to a sub-filter. The number of subsets or partitions can be varied, and since there are slave modules in the cluster, each independent partition is deployed on a specific slave module. Using the deployed sub-filters, each slave module is designed to perform data distillation processing on the candidate units it receives.

Figure 12M illustrates the division of basic data filters into four basic data filters or sub-filters, labeled PDS_1, PDS_2, PDS_3, and PDS_4, which will be deployed on four slave modules running on four nodes. The partitioning is based on the leading byte of the basic data unit's name. In the example shown, the leading byte of the name of all units in PDS_1 will be in the range A to I, and filter PDS_1 will have the name A_I, marked by the range of values leading to it. Similarly, the leading byte of the name of all units in PDS_2 will be in the range J to O, and sub-filter PDS_2 will have the name J_0, marked by the range of values leading to it. Likewise, the leading byte of the name of all units in PDS_3 will be in the range P to S, and sub-filter PDS_3 will have the name P_S, marked by the range of values leading to it. Finally, the leading byte of the name of all units in PDS_4 will be in the range T to Z, and sub-filter PDS_4 will have the name T_Z, marked by the range of values leading to it.

In this setup, the master module running on the master node receives the input file and performs lightweight parsing and factorization of the input file to decompose it into a sequence of candidate units. Each candidate unit is then directed to the appropriate slave module for further processing. Lightweight parsing may include parsing each candidate unit graphically, or it may include applying a fingerprint to the candidate unit to determine the dimension of the leading bytes that make up the candidate unit's name. Parsing at the master node is limited to identifying enough bytes to determine which slave module should receive the candidate unit. Based on the value in the leading bytes of the candidate unit's name, the candidate is forwarded to the slave module at the slave node that maintains a sub-sieve corresponding to that specific value.

As data accumulates in the filter, partitions can be intermittently revisited and rebalanced. Partitioning and rebalancing can be performed by the main module.

Upon receiving a candidate cell, each slave module performs data distillation, starting with a complete parsing and inspection of the candidate cell to create its name. Using this name, the slave module performs a sub-sieve content association query and performs distillation to convert the candidate cell into a cell in a lossless simplified representation of that sub-sieve. This is done using a field called SlaveNumber, which identifies the slave module, and a lossless simplified representation of the cell in the corresponding sub-sieve enhanced distillation file. The lossless simplified representation of the cell is sent back to the master module. If a candidate cell is not found in the sub-sieve, or cannot be derived from the basic data cells in the sub-sieve, a new basic data cell is identified and assigned to the sub-sieve.

The master module continues to guide all candidate cells from the input file to the appropriate slave modules and accumulates the incoming cell descriptions (in a lossless simplified representation) until it has received all cells from the input file. At this point, a global commit communication can be sent to all slave modules to update their respective subsieves based on the results of their respective distillation processes. The distillation file for the input is stored in the master module.

In some embodiments, instead of waiting for the entire distillation file to be prepared before any slave device can update its subsieve with new basic data units or metadata, the update of the subsieve can be completed while the candidate units are being processed at the slave module.

In some embodiments, as described in Figures 1B and 1C, each sub-sieve contains basic data units and reconstruction procedures. In such embodiments, reconstruction procedures are stored in the sub-sieve, and the lossless simplified representation contains references to the basic data units and reconstruction procedures (if needed) in the sub-sieve. This further reduces the unit size and thus the size of the distillation file that needs to be stored in the main module. In some embodiments, the basic reconstruction procedure filter in each sub-sieve contains those reconstruction procedures for creating derived items from the basic data units residing in that sub-sieve. In this case, the basic reconstruction procedures are locally available on the slave node, enabling fast export and reconstruction without any latency that would otherwise be incurred from obtaining the basic reconstruction procedures from remote nodes. In other embodiments, the basic reconstruction procedure filters are globally distributed across all nodes to utilize the total capacity of the distributed system. The lossless simplified representation is enhanced by a second field that identifies the slave node or sub-sieve containing the basic reconstruction procedures. In such embodiments, this solution results in additional latency in obtaining the basic reconstruction procedures from remote nodes to generate the final reconstruction procedure or reconstruction unit through export. The entire method utilizes the combined storage capacity of all slave nodes to distribute files across all nodes based on the content of each block or candidate unit in each file.

Data retrieval is similarly coordinated by the master module. The master module receives the distillation file and examines the lossless simplified specification of each cell in the file. Its extracted field, "SlaveNumber," indicates which slave module will reconstruct the cell. The cell is then sent to the appropriate slave module for reconstruction. The reconstructed cell is then sent back to the master module. The master module assembles the cells reconstructed from all slave modules and forwards the reconstructed file to the consumer that requested it.

Figure 12N illustrates how a data distillation apparatus can be deployed and executed in a distributed system. Input file 1251 is fed to the master module, which parses and identifies the leading byte of the name of each candidate cell in the file. The master module directs the candidate cells to one of four slave modules. Slave module 1, at slave node 1 of slave node PDS_1 or a sub-sieve holding a basic data cell with the name A_I and a leading byte containing a name-bearing value in the range A to I, receives candidate cell 1252 with the name BCD..., which is determined to be a copy of the cell already existing in the sub-sieve named A_I. Slave module 1 returns a lossless simplified representation 1253, which contains the cell as an indicator and resides at address refPDE1 on Slave1. As shown in Figure 12N, the master module sends all candidate cells to the relevant slave modules, assembles and collects them, and finally stores the distillation file.

Figure 120 shows a variation of the illustration shown in Figure 12N. In this variation, in the lossless simplified representation of each cell in the distillation file, the field identifying the specific Child_Sieve to which the cell has been simplified contains the name of the Child_Sieve, rather than the number of the module or node to which the Child_Sieve resides. Therefore, the SlaveNumber field is replaced by the Child_Sieve_Name field. This has the advantage of referencing the associated Child_Sieve by its virtual address rather than the number of the module or physical node to which the Child_Sieve resides. Thus, as shown in Figure 120, slave module 1 at slave node 1 of PDS_1 or subsieve, which holds a basic data cell with the name A_I and a leading byte containing a name-bearing value in the range A to I, receives a candidate cell 1252 with the name BCD..., which is determined to be a copy of the cell already existing in the subsieve named A_I. Return lossless simplified representation 1254 from module 1, which contains the basic pointer of the cell and resides at address refPDE1 in Slave1.

Note that by employing the arrangement described in Figures 12L to 12O, the overall throughput of data distillation processing can be improved. The throughput of the main module will be limited by lightweight parsing and the scheduling of candidate units from the main module. Distillation of many candidate units will be performed in parallel, as long as their contents direct them to different slave modules.

To further improve overall throughput, the lightweight parsing and factorization of the input stream can be parallelized to identify which Child_Sieve should receive candidate units. This task can be divided into multiple parallel tasks by the master module, executed in parallel by slave modules running on multiple slave nodes. This can be accomplished by predicting the data stream and dividing it into multiple partially overlapping segments. These segments are sent by the master module to each slave module that performs the lightweight parsing and factorization in parallel, and the results of the factorization are sent back to the master module. The master module factorizes the data across the boundaries of each segment and then routes the candidate units to the appropriate slave module.

Figures 12L to 12O depict an arrangement in which the data distillation apparatus operates in a distributed manner, with a master distillation module running on a master node and multiple slave distillation modules running on slave nodes. The master module is responsible for performing partitioning of basic data units across various subsieves. In the arrangement shown, all input files to be ingested are ingested by the master module, and lossless simplified distillation files remain at the master module, while all basic data units (and any major reconstruction procedures) reside in the subsieves at the respective slave modules. Data retrieval requests for files are also handled by the master module, and the reconstruction of the corresponding distillation files is coordinated by the master module. Figure 12P shows a variation where input files can be ingested by any slave distillation module (and the corresponding distillation files retained in those modules), and data retrieval requests can be handled by any slave distillation module. The master module continues to perform partitioning of basic data units on the subsieves in the same manner, so that the distribution of basic data units across the subsieves will be the same as the arrangement shown in Figures 12L to 12O. However, in the new configuration shown in Figure 12P, each slave module is aware of the partition because each slave module can ingest and retrieve data. Furthermore, all modules are aware of the existence and location of distillation files created and stored on each module when data is ingested by these modules. This allows any module to fulfill data retrieval requests for any file stored throughout the system.

As shown in Figure 12P, each slave module can ingest and retrieve data from the distributed storage system. For example, distillation module 1 1270 ingests input file I 1271 and performs lightweight parsing to factorize input file I and route candidate units to modules containing sub-sieves corresponding to the names of each candidate unit in input file I. For example, candidate unit 1275 from input file I is sent to distillation module 2 1279. Similarly, distillation module 2 1279 ingests input file II and performs lightweight parsing to factorize input file II and route candidate units to modules containing sub-sieves corresponding to the names of each candidate unit in input file II. For example, candidate unit 1277 from input file II is sent to distillation module 1 1270. Each slave distillation module processes the candidate units it receives, completes the distillation process with respect to its sub-sieves, and returns a lossless simplified representation of the candidate units to the initiating module that ingested the data. For example, in response to receiving candidate unit 1275 from input file I from distillation module 1 1270, distillation module 2 1279 returns lossless simplification unit 1276 to distillation module 1 1270. Similarly, in response to receiving candidate unit 1277 from input file II from distillation module 2 1279, distillation module 1 1270 returns lossless simplification unit 1278 to distillation module 2 1279.

In this setup, data retrieval can be satisfied at any slave module. The module receiving the retrieval request first needs to determine the location where the distillation file of the requested file resides and obtain the distillation file from the corresponding slave module. Subsequently, the initiating slave module needs to coordinate the distributed reconstruction of the individual units within the distillation file to generate the original file and deliver it to the requesting application.

In this way, data distillation can be performed in a distributed manner across multiple nodes in a distributed system to more effectively utilize the total computing, memory, and storage capacity of multiple computers in the cluster. All nodes in the system can be used to ingest and retrieve data. This should enable very high data ingestion and retrieval rates while fully utilizing the combined total storage capacity of the nodes in the system. It also allows applications running on any node in the system to query any data stored anywhere in the system on their local node, and to satisfy that query efficiently and seamlessly.

In the arrangement described in Figures 12M to 12P, the data partitioning across sub-sieves residing in various nodes of the system is based on cell names in a globally visible namespace, where each cell is extracted by factoring the input file. In another arrangement, data batches or entire groups of files sharing certain metadata can be allocated and stored on specific nodes. Thus, the master partitioning of the overall data is based on data batches and is performed and managed by the master data. All slave modules remain aware of the data batch allocation to the module. The data batch will reside entirely on the given slave node. The sub-sieves on the distillation slave module running on that slave node will contain all the basic data units belonging to that data batch. In other words, the entire tree of all basic data units of a given data batch will reside entirely on a single sub-sieve within a single slave distillation module. All distillation files of a given data batch will also reside in the same slave distillation module. Using this arrangement, the input file can still be ingested by any slave distillation module, and data retrieval requests can still be processed by any slave distillation module. However, the entire data distillation process for a given data batch is performed entirely on the module containing that data batch. Data ingestion and retrieval requests are routed from the initiating module to a specific slave module designated to hold a particular batch of data. This approach offers the advantage of reduced communication overhead in a distributed environment when factoring and distilling data batches. Redundancy is no longer employed across the entire global data footprint; instead, it is utilized very efficiently locally within the data batch. The approach still utilizes the combined storage capacity of the distributed system and provides the seamless capability to query, ingest, and retrieve any data from any node in the system.

Therefore, by employing the aforementioned techniques, resources in a distributed system can be efficiently utilized to perform data distillation on very large datasets at very high speeds.

The Data Distillation ^™ method and apparatus can be further enhanced to facilitate efficient data movement and migration. In some embodiments, lossless simplified datasets can be delivered in the form of multiple containers or packages to facilitate data movement. In some embodiments, one or more simplified data batches can be assembled into a single container or package, and alternatively, a single simplified data batch can be converted into multiple packages. In some embodiments, a single simplified data batch is delivered as a single self-describing package. Figure 12Q illustrates an example structure of such a package. Package 1280 in Figure 12Q can be viewed as a continuous collection of single files or bytes, containing the following components concatenated sequentially: (1) Header 1281, which is the package header, first containing a package length 1282 specifying the length of the package, and then containing offset identifiers identifying the positions of distillation files, PDE files, and various lists within the package; (2) Distillation files 1283, which are distillation files of data batches concatenated one after another, where the length of each distillation file is first specified, followed by all the bytes that make up that distillation file; (3) PDE files 1284, which are PDE files, starting with the length identifier of the PDE file, followed by the body of the PDE file containing all the basic data units; (4) Source list 1285, which is the source list describing the structure of the input dataset and identifying the unique directory structure, pathname, and filename of each file in the package. The source list also contains a list of each node in the input data batch (which has been simplified and transformed into a package) and metadata associated with each node; (5) Destination list and mapper 1286, which is the destination list and mapper. The destination mapper provides the expected mapping from each input node and file to the destination directory and file structure or the target bucket/container and object/binary large object (bolb) structure in the cloud. This manifest helps to move, rebuild, and reposition the individual components of the package to the final destination after data movement. Note that this destination mapper section can be modified individually to reposition the data in the package to the destination to be transferred and rebuilt.

In this way, the lossless simplified representation of data batches is delivered as packages in a self-describing format suitable for data movement and relocation.

Data simplification was performed on various real-world datasets using the embodiments described herein to determine the effectiveness of these embodiments. The real-world datasets studied included the Enron corpus of corporate emails, various records and documents from the U.S. government, U.S. Department of Transportation records accessed through a MongoDB NoSQL database, and publicly available corporate PowerPoint presentations. Using the embodiments described herein and factoring the input data into variable-size units averaging 4KB (boundaries determined by fingerprints), an average data simplification of 3.23x was achieved on these datasets. A 3.23x simplification means that the size of the simplified data is equal to the size of the original data divided by 3.23x, resulting in a simplification footprint of 31% compression. Conventional deduplication techniques were found to deliver 1.487x data simplification on these datasets using equivalent parameters. Using the embodiments described herein and factoring the input data into fixed-size units of 4KB, an average data simplification of 1.86x was achieved on these datasets. Conventional deduplication techniques were found to deliver 1.08x data simplification on these datasets using equivalent parameters. Therefore, the Data Distillation ^™ scheme was found to provide better data simplification than conventional deduplication schemes.

The test run also confirmed that a small subset of bytes of the basic data unit was used to sort most of the units in the filter, thus enabling a scheme that requires minimal incremental storage for its operations.

The results confirm that the Data Distillation ^™ device effectively leverages redundancy across global data units throughout the dataset at a finer granularity than the unit itself. This lossless data simplification is achieved through economical data access and I/O, requiring minimal incremental storage for the data structures themselves and utilizing only a fraction of the total computational power available on modern multi-core microprocessors. The embodiments described in the preceding sections are characterized by systems and techniques for performing lossless data simplification on large and extremely large datasets, while providing high-rate data ingestion and retrieval, without the drawbacks and limitations of conventional techniques.

Data is derived from the basic data units residing in the basic data filter, and the data has been losslessly simplified. Perform content-related search and retrieval

Certain features can be leveraged to enhance the data distillation apparatus described in the preceding text and shown in Figures 1A to 12P, enabling efficient multidimensional search and content-related retrieval of information from data stored in a lossless, simplified format. This multidimensional search and data retrieval is a key component of analytics or data warehousing applications. These enhancements will now be described.

Figure 13 illustrates a leaf node data structure similar to that shown in Figure 3H. However, as shown in Figure 13, the entries in the leaf node data structure for each basic data unit are enhanced to include references to all units in the distillation data (also referred to as backreferences or backlinks), including references to that particular basic data unit. Recall that the data distillation schema factorizes data from the input file into a sequence of units placed in the distillation file in a simplified format using specifications such as those described in Figure 1H. There are two types of units in the distillation file—basic data units and derived units. The specification for each unit in the distillation file will contain references to the basic data units residing in the basic data filter. For each of these references (from a unit in the distillation file to a basic data unit in the basic data filter), a corresponding backlink or backreference (from an entry of the basic data unit in the leaf node data structure to a unit in the distillation file) will be placed in the leaf node data structure. The backreference determines an offset in the distillation file that marks the start of the lossless simplified representation of the unit. In some embodiments, the backreference includes the name of the distillation file and the offset within that file that positions the start of the unit. As shown in Figure 13, in addition to backreferences to each cell in the distillation file, the leaf node data structure also maintains an indicator that identifies whether the cell referenced in the distillation file is a basic data cell (basic) or a derived cell (deriv). During distillation, backlinks are placed into the leaf node data structure when cells are added to the distillation file.

Reverse references or reverse links are designed as universal handles that can reach all cells in all distillation files that share a basic data filter.

The addition of expected backreferences will not significantly affect the data simplification achieved because the expected data unit size is chosen such that each reference is a portion of the data unit size. For example, consider a system where derived units are constrained to no more than one basic data unit per derived item (thus disallowing multi-unit derived items). The total number of backreferences across all leaf node data structures will equal the total number of units in all distilled files. Suppose a 32GB sample input dataset is simplified to 8GB of lossless simplified data with an average unit size of 1KB, resulting in a 4x simplification rate. There are 32M units in the input data. If each backreference is 8B in size, the total space occupied by backreferences is 256MB, or 0.25GB. This is a small increase for simplified data with an 8GB footprint. The new footprint will reach 8.25GB, resulting in an effective reduction of 3.88x, equivalent to a 3% simplification loss. This is a small cost for the powerful content-related data retrieval benefits of simplified data.

As described earlier in this article, the distillation apparatus can employ various methods to determine the location of each component of the skeletal data structure within the content of a candidate cell. Each component of the cell's skeletal data structure can be considered a dimension, so the concatenation of these dimensions, immediately following the rest of the cell's content, is used to create the name of each cell. This name is used to sort and organize the basic data unit in the tree.

In the usage model of the known input data structure, a schema defines the various fields or dimensions. This schema is provided by the analytics application that is using the content-related data retrieval device and is provided to the device through the application's interface. Based on the declarations in the schema, the parser of the distillation device is able to parse the content of candidate cells to detect and locate each dimension and create names for the candidate cells. As previously mentioned, cells with the same content in the fields corresponding to dimensions will be grouped together along the same branch (leg) of the tree. For each basic data cell placed in the filter, information on the dimension can be stored as metadata in the entry of the basic data cell in the leaf node data structure. This information may include the position, size, and value of the content on each declared dimension and can be stored in a field referred to as "Other Metadata of Basic Data Cells" in Figure 13.

Figure 14A illustrates an example diagram describing the structure of an input dataset according to some embodiments described herein, and a description of the correspondence between the structure of the input dataset and its dimensions. Structure description 1402 is an excerpt or part of a more complete diagram describing the full structure of the input data. Structure description 1402 includes a list of keys (e.g., “PROD_ID”, “MFG”, “MONTH”, “CUS_LOC”, “CATEGORY”, and “PRICE”), followed by the type of the value corresponding to that key. A colon character “:” is used as a separator to separate the types of keys and values, and a semicolon character “;” is used as a separator to separate different key pairs and their respective types. Note that the complete diagram (of which structure 1402 is a part) may specify additional fields to identify the beginning and end of each input, and may also specify fields other than dimensions. Dimension mapping description 1404 describes how the dimensions used to organize basic data units are mapped to the key values in the structured input dataset. For example, the first line in dimension mapping description 1404 specifies that the first four bytes corresponding to the value of the key "MFG" in the input dataset (because the first line ends with the text "prefix=4") are used to create dimension 1. The remaining lines in dimension mapping description 1404 describe how to create the other three dimensions based on the structured input data. In this key-to-dimension mapping, the order in which the keys appear in the input does not necessarily match the order of the dimensions. Using the provided graphical description, the parser can identify these dimensions in the input data to create names for candidate cells. For the example in Figure 14A, and using dimension mapping description 1404, the names of candidate cells will be created as follows: (1) The first 4 bytes of the name will be the first 4 bytes of the value corresponding to the key “MFG” declared as dimension 1; (2) The next 4 bytes of the name will be the first 4 bytes of the value corresponding to the key “CATEGORY” declared as dimension 2; (3) The next 3 bytes of the name will be the first 3 bytes of the value corresponding to the key “CUS_LOC” declared as dimension 3; (4) The next 3 bytes of the name will be the first 3 bytes of the value corresponding to the key “MONTH” declared as dimension 4; (5) The next set of bytes of the name will be a concatenation of the remaining bytes of the dimension; (6) And finally, after all the bytes of the dimension have been used up, the remaining bytes of the name will be created from the concatenation of the remaining bytes of the candidate cells.

The schema provided by the application driving the device can specify multiple primary dimensions and multiple secondary dimensions. Information about all these primary and secondary dimensions can be preserved in the metadata of the leaf node data structure. Primary dimensions are used to form the main axis along which cells in the filter are categorized and organized. If the primary dimensions are exhausted and a subtree with a large number of members still exists, secondary dimensions can be used deeper into the tree to further subdivide the cells into smaller groups. Information about the secondary dimensions can be preserved as metadata or used as a second criterion to distinguish cells within a leaf node. In some embodiments that provide content-related multidimensional search and retrieval, all incoming data can be required to contain the key and valid value for each dimension declared by the schema. This allows the system to ensure that only valid data enters the required subtree in the filter. Candidate cells that do not contain all fields specified as dimensions or contain invalid values in the values corresponding to the fields of a dimension will be sent to different subtrees as illustrated earlier in Figure 3E.

The data distillation apparatus is constrained in an additional way to comprehensively support content-related searches and retrievals of data based on the content within dimensions. When creating derived units from basic data units, the exporter is constrained to ensure that the basic data unit and the exported item have exactly the same content in the value fields of each corresponding dimension. Therefore, when creating exported items, the refactoring process is not allowed to interfere with or modify the content in the value fields corresponding to any dimension of the basic data unit to construct the exported item. Given a candidate unit, during the search filtering process, if the candidate unit has different content in any dimension compared to the corresponding dimension of the target basic data unit, a new basic data unit needs to be placed, and the exported item is not accepted. For example, if a subset of the primary dimension sufficiently categorizes the units into different groups in the tree, such that a candidate unit reaches a leaf node to find a basic data unit that has the same content in this subset of the primary dimension but has different content in the remaining primary or second dimension, then a new basic data unit needs to be placed instead of creating an exported item. This feature ensures that all data can be searched using dimensions by simply querying the basic data filter.

The exporter can employ various implementation techniques to enforce the constraint that candidate cells and basic data cells must have identical content in the value fields of each corresponding dimension. The exporter can extract information from the skeleton data structure of the basic data cell, including the position, length, and content of the fields corresponding to the dimensions. This information is similarly received from the parser/decomposer or computed for the candidate cell. Next, the corresponding fields of the dimensions of the candidate cell and the basic data cell can be compared for equality. Once equality is confirmed, the exporter can continue with the remaining export. If they are not equal, the candidate cell will be added to the filter as a new basic data cell.

The aforementioned limitations are not expected to significantly hinder the data simplification of most models. For example, if the input data consists of a set of units, which are data warehouse transactions, each 1000 bytes in size, and if the diagram specifies a set of 6 primary dimensions and 14 secondary dimensions, each with 8 bytes of data, the total number of bytes occupied by the content across the dimensions is 160 bytes. These 160 bytes are not allowed to be perturbed when creating derived items. This still leaves 840 bytes of candidate unit data available for perturbing to create derived items, thus providing ample opportunity to utilize redundancy while enabling the searching and retrieval of data from the data warehouse using dimensions in a content-related manner.

To perform a search query on data containing specific values of fields in a dimension, the apparatus can traverse the tree and reach the node in the tree that matches the specified dimension, returning all leaf node data structures below that node as the search result. References to the basic data units present at leaf nodes can be used to retrieve the required basic data units when needed. If necessary, backlinks can retrieve input units (in a lossless simplified format) from a distillation file. This unit can then be reconstructed to produce the original input data. Therefore, the enhanced apparatus allows for complete searches of data in a basic data repository (which is a smaller subset of the entire data) while being able to reach and retrieve all derived units as needed.

The enhanced mechanism allows for the execution of search and lookup queries to powerfully search and retrieve relevant subsets of data based on content within the dimensions specified in the query. Content-related data retrieval queries will have the form "get (dimension 1, value of dimension 1; dimension 2, value of dimension 2; ...)". The query will specify the dimensions involved in the search, along with the value for each specified dimension used for content-related searches and looks. Queries can specify all dimensions or only a subset of dimensions. Queries can specify composite conditions based on multiple dimensions as criteria for search and retrieval. All data filtered with specified values for specified dimensions will be retrieved.

It supports various retrieval queries and makes them usable by analytics applications that are using the content-related data retrieval device. These queries are provided to the device through the application's interface. The interface provides the device with queries from the application and returns the query results from the device to the application. First, the query `FetchRefs` can be used to retrieve a reference to or process the leaf node data structure (along with the sub-ID or index of the entry) in Figure 13 for each basic data unit that matches the query. A second form of the query `FetchMetaData` can be used to retrieve metadata (including the skeleton data structure, information about dimensions, and references to the basic data unit) from the entries in the leaf node data structure in Figure 13 for each basic data unit that matches the query. A third form of the query `FetchPDEs` will retrieve all basic data units that match the search criteria. Another form of the query `FetchDistilledElements` will retrieve all units in the distilled files that match the search criteria. Another form of the query `FetchElements` will retrieve all units in the input data that match the search criteria. Note that for the `FetchElements` query, the device will first retrieve the distilled units, then reconstruct the relevant distilled units into units from the input data and return them as the result of the query.

In addition to such multidimensional content association retrieval primitives, the interface can also provide applications with the ability to directly access basic data units (using references to basic data units) and units in distillation files (using backreferences to units). Furthermore, the interface can provide applications with the ability to reconstruct distillation units in distillation files (given a reference to the distillation unit) and pass that unit because it exists in the input data.

The intelligent combination of these queries can be used by analytics applications to perform searches, identify relevant unions and intersections, and gather important insights.

Figure 14B, explained below, illustrates an example of an input dataset with the structure described in structure description 1402. In this example, the input data contained in file 1405 comprises e-commerce transactions. This input data is transformed into a sequence of candidate cells 1406 by an analyzer in the data distillation apparatus using the schema and dimension claims in Figure 14A. Note how the leading byte of each candidate cell's name is composed of the dimensions' contents. For example, the leading byte of the name 1407 for candidate cell 1 is PRINRACQNYCFEB. These names are used to organize the candidate cells in a tree structure. After data simplification, the distilled data is placed in distillation file 1408.

Figure 14C, explained below, illustrates how the dimension mapping description 1404 is used to parse the input dataset shown in Figure 14A according to the structure description 1402, determine the dimensions according to the dimension mapping description 1404, and organize the basic data units in the tree based on the determined dimensions. In Figure 14C, the basic data units are organized in the main tree using a total of 14 characters from the 4 dimensions. The main tree shows a portion of the leaf node data structure for the various basic data units. Note that the complete leaf node data structure of Figure 13 is not shown for ease of viewing. However, Figure 14C shows the path information or name of each entry in the leaf node data structure, the sub-ID, all backreferences or backlinks from the basic data unit to the unit in the distillation file, and an indicator indicating whether the unit in the distillation file is a "prime" (denoted by P) or a "derived item" (denoted by D), as well as references to the basic data unit. Figure 14C shows 7 units in the distillation file mapped to 5 basic data units in the main tree. In Figure 14C, the backlink A for the basic data cell, named PRINRACQNYCFEB, returns to cell 1 in the distillation file. Meanwhile, the basic data cell named NIKESHOELAHJUN has three backlinks B, C, and E to cells 2, 3, and 58, respectively. Note that cells 3 and 58 are derivations of cell 2.

Figure 14D illustrates an auxiliary index or auxiliary tree created from a dimension to improve search efficiency. In this example, the auxiliary mapping tree is created based on dimension 2 (i.e., CATEGORY). By directly traversing this auxiliary tree, all cells in the input data for a given CATEGORY can be found without the need for a more expensive main tree traversal that might otherwise occur. For example, traversing down the leg, denoted by "SHOE," directly leads to the two basic data cells of shoe: ADDIKHOESJCSEP and NIKESHOELAHJUN.

Alternatively, such an auxiliary tree can be based on a second dimension and used to leverage the dimension to help the search converge quickly.

An example of a query executed on the apparatus shown in Figure 14D will now be provided. The query `FetchPDEs(Dimension 1, NIKE;)` will return two basic data units named `NIKESHOELAHJUN` and `NIKEJERSLAHOCT`. The query `FetchDistilledElements(Dimension 1, NIKE;)` will return units 2, 3, 58, and 59, which are distillation units in a lossless simplified format. The query `FetchElements(Dimension 1, NIKE; Dimension 2, SHOE)` will return transactions 2, 3, and 58 from input data file 1405. The query `FetchMetadata(Dimension 2, SHOES)` will return metadata stored in the leaf node data structure entry for each of the two basic data units named `ADIDSHOESJCSEP` and `NIKESHOELAHJUN`.

The apparatus described so far can be used to support searches based on content specified in fields called dimensions. Additionally, the apparatus can be used to support searches based on a list of keywords not included in the dimension list. Such keywords can be provided to the apparatus by an application such as the search engine that powers it. Keywords can be specified to the apparatus via a schema declaration or passed via a keyword list containing all keywords, each keyword separated by a declared delimiter (such as a space, comma, or newline). Alternatively, all keywords can be specified using both a schema and a keyword list. A large number of keywords can be specified – the apparatus has no limit on the number of keywords. These search keywords will be referred to as Keywords. The apparatus can use these keywords to maintain an inverted index for the search. For each keyword, the inverted index contains a list of backreferences to cells in distilled files containing that keyword.

Based on keyword declarations in a schema or keyword list, the parser of the distillation apparatus can parse the contents of candidate cells to detect and locate individual keywords within the incoming candidate cells (whether they are found and where they are found). The candidate cells are then converted into basic data cells or derived cells by the data distillation apparatus and placed as cells in the distillation file. The inverted index of the keywords found in this cell can be updated using backreferences to the cells in the distillation file. For each keyword found in a cell, the inverted index is updated to include a backreference to that cell in the distillation file. Recall that the cells in the distillation file are represented using a lossless simplified representation.

After performing a search query on the data using a keyword, the inverted index is queried to find and extract back references to cells in distillation files containing that keyword. Using these back references, a lossless simplified representation of the cell can be retrieved, and the cell can be reconstructed. The reconstructed cell can then be provided as a result of the search query.

The inverted index can be enhanced to include information about the offset of the locating keyword within the reconstructed cell. Note that the offset or position of each keyword detected in the candidate cell can be determined by the parser; therefore, this information can also be recorded in the inverted index when a backreference to a cell in the distillation file is placed there. During a search query, after querying the inverted index to retrieve a backreference to a cell in the distillation file containing the relevant keyword, and after that cell is reconstructed, the recorded offset or position of the keyword within the reconstructed cell (the same as the original input candidate cell) can be used to determine the location of the keyword in the input data or input file.

Figure 15 illustrates an inverted index that facilitates searching by keyword. For each keyword, the inverted index contains a pair of values—the first is a backreference to the lossless simplification cell in the distillation file containing the keyword, and the second value is the offset of the keyword in the reconstructed cell.

Dimensions and keywords have different meanings for the basic data filters in a data distillation apparatus. Note that dimensions serve as the main axis along which the basic data units are organized in the filter. Dimensions form the skeleton data structure of each unit in the data. Dimensions are declared based on knowledge of the incoming data structure. The derivator is restricted such that any derived unit created must have exactly the same content as the basic data unit in the value of each corresponding dimension's field.

These properties do not need to be maintained for keywords. In some embodiments, there are no prior requirements for keywords to even exist in the data, nor is there a requirement to organize basic data filtering based on keywords, nor is there any constraint on the exporter involving derivations containing keywords. If needed, the exporter can freely create derivations from the basic data unit by modifying the value of the keyword. The position of the keyword is only recorded where it is found when scanning the input data, and the inverted index is updated. During keyword-based content association searches, the inverted index is queried and all positions of the keyword are obtained.

In other embodiments, the keyword is not required to exist in the data (the absence of the keyword in the data does not invalidate the data), but the basic data filter is required to include all units containing the keyword, and the exporter is constrained in its export of content containing the keyword – no export is allowed except to reduce duplicates. The aim of these embodiments is that all distinct units containing any keyword must exist in the basic data filter. This is an example where the rules controlling the selection of basic data are conditional on keywords. In these embodiments, a modified inverted index can be created that contains a backreference to each basic data unit containing that keyword. In these embodiments, powerful keyword-based search capabilities are implemented, where searching only the basic data filter is as effective as searching the entire data.

Other embodiments may exist in which the exporter is constrained such that the reconstruction process is not allowed to interfere with or modify the content of any keywords found in the basic data unit in order to designate a candidate unit as a derived unit of that basic data unit. Keywords need to be propagated unchanged from the basic data unit to the derived item. If the exporter needs to modify the bytes of any keywords found in the basic data unit in order to successfully designate a candidate as a derived item of that basic data unit, then the derived item may be rejected, and the candidate must be installed in the filter as a new basic data unit.

Regarding exported items involving keywords, the exporter can be constrained in various ways so that the rules for managing the selection of basic data are conditional on the keywords.

The device for searching data using keywords can accept updates to the list of keywords. The device enables updates to the keyword list. Keywords can be added without altering the data stored in a lossless simplified form. When a new keyword is added, the new input data can be parsed against the updated keyword list, and the inverted index, updated with the input data, is subsequently stored in a lossless simplified form. If existing data (already stored in a lossless simplified form) needs to be indexed against new keywords, the device can progressively read distillation files (one or more distillation files at a time, or one batch of lossless simplified data at a time), reconstruct the original files (without interfering with the lossless simplified data storage), and parse the reconstructed files to update the inverted index. During this entire process (all this while), the entire data repository can continue to be stored in a lossless simplified form.

Figure 16A illustrates a variant of the schema declaration shown in Figure 14A. The schema in Figure 16A includes the declaration of the second dimension 1609 and the keyword list 1610. Figure 16B shows an example of an input dataset 1611 with the structure described in structure description 1602, which is parsed and transformed into a set of candidate cells with names based on the declared primary dimension. The candidate cells are transformed into cells in the distillation file 1613. The declaration of the second dimension “PROD_ID” sets a constraint on the exporter such that it is possible not to derive candidate cell 58 from the basic data cell “NIKESHOELAHJUN with PROD_ID=348”, and thus create another basic data cell “NIKESHOELAHJUN with PROD_ID=349” in the basic data filter. Although the input dataset is the same as the input dataset shown in Figure 14B, the result of distillation is the production of 7 distillation cells but 6 basic data cells. Figure 16C shows the distillation file, main tree, and basic data cells created as a result of the distillation process.

Figure 16D illustrates the auxiliary tree created for the second dimension, “PROD_ID”. Traversing this tree using a specific PROD_ID value results in a basic data unit with that specific PROD_ID. For example, the query FetchPDEs(dimension 5, 251) or the query FetchPDEs(PROD_ID, 251) requesting a basic data unit with PROD_ID = 251 produces the basic data unit WILSBALLLAHNOV.

Figure 16E shows the inverted index (labeled as inverted index 1631) created for the three keywords declared in structure 1610 of Figure 16A. These keywords are FEDERER, LAVER, and SHARAPOVA. The inverted index is updated after parsing and consuming the input dataset 1611. The query FetchDistilledElements(keyword, Federer) will utilize the inverted index (instead of the main tree or auxiliary tree) to return cells 2, 3, and 58.

Figure 17 shows a block diagram of the entire apparatus for enhanced content-related data retrieval. The content-related data retrieval engine 1701 provides the data distillation apparatus with a schema 1704 or a structural definition including dimensions of the data. It also provides the apparatus with a keyword list 1705. It issues queries 1702 to search for and retrieve data from the distillation apparatus and receives the query results as results 1703. The exporter 110 is enhanced to be aware of dimension declarations, thus preventing modification of content at the dimension's location when creating exported items. Note that backreferences from entries in the leaf node data structure to cells in the distillation file are stored in the leaf node data structure in the basic data filter 106. Similarly, secondary indexes are also stored in the basic data filter 106. The inverted index 1707, updated by the exporter 110 via backreferences 1709, is also shown when cells are written to distilled data. This content-related data retrieval engine interacts with other applications, such as analytics, data warehousing, and data analysis applications, providing them with the results of executed queries.

In summary, the enhanced data distillation device enables powerful multidimensional content-related searches and retrievals of data stored in a lossless, simplified form.

The Data Distillation ^™ device can be used for lossless simplification of audio and video data. Data simplification achieved using this method is accomplished by deriving components of audio and video data from basic data units residing in a content-related filter. The application of this method to such applications is described below.

Figures 18A-18B show block diagrams of encoders and decoders used for compressing and decompressing audio data according to the MPEG 1, Layer 3 standard (also known as MP3). MP3 is an audio encoding format for digital audio that compresses incoming audio using a combination of lossy and lossless data reduction techniques. It manages to compress CD audio from 1.4 Mbps to 128 Kbps. MP3 takes advantage of the limitations of the human ear to suppress audio components that are imperceptible to most people. To achieve this, a set of techniques collectively known as perceptual coding techniques are used, which lossily but imperceptibly reduce the size of a segment of audio data. Perceptual coding techniques are lossy, and information lost during these steps cannot be recovered. These perceptual coding techniques are complemented by Huffman coding, a lossless data reduction technique described earlier in this paper.

In MP3, the incoming audio stream is compressed into a series of smaller data frames, each containing a frame header and compressed audio data. The original audio stream is periodically sampled to produce a series of audio segments, which are then compressed using perceptual coding and Huffman coding to produce a series of MP3 data frames. Both perceptual coding and Huffman coding techniques are applied locally within each segment of the audio data. Huffman coding utilizes redundancy locally within an audio segment, but not globally across the audio stream. Thus, MP3 technology does not utilize redundancy globally across a single audio stream, nor across multiple audio streams. This represents an opportunity for further data simplification beyond what MP3 can achieve.

Each MP3 data frame represents a 26ms audio segment. Each frame stores 1152 samples, which are subdivided into two granules, each containing 576 samples. In the encoder block diagram in Figure 18A, it can be seen that during the encoding of the digital audio signal, filtering is performed, and a modified Discrete Cosine Transform (MDCT) is applied to obtain time-domain samples, which are then transformed into 576 frequency-domain samples. Perceptual coding is applied to reduce the amount of information contained in the samples. The output of perceptual coding is a non-uniform quantization granule 1810, where each frequency line contains the reduced information. Huffman coding is then used to further reduce the size of the granules. Multiple Huffman tables can be used for encoding the 576 frequency lines of each granule. The output of Huffman coding is the main data component of the frame, containing the scaling factor, Huffman-coded bits, and auxiliary data. Side information (used to characterize and locate individual fields) is placed in the MP3 header. The encoded output is the MP3 encoded audio signal. At a bitrate of 128Kbps, the size of an MP3 frame is 417 or 418 bytes.

Figure 18C illustrates how to enhance the data distillation apparatus first shown in Figure 1A to simplify MP3 data. The method illustrated in Figure 18C factorizes the MP3 data into candidate cells and utilizes redundancy between cells at a finer granularity than the cells themselves. For MP3 data, particles are selected as cells. In one embodiment, a non-uniform quantization particle 1810 (shown in Figure 18A) can be considered a cell. In another embodiment, a cell can be composed of a cascade of quantization frequency lines 1854 and scaling factors 1855.

In Figure 18C, the MP3 encoded data stream 1862 is received by the data distillation device 1863 and simplified into a distilled MP3 data stream 1868 stored in a lossless simplified form. The incoming MP3 encoded data stream 1862 consists of a series of multiple pairs of MP3 headers and MP3 data. The MP3 data includes CRC, side information, main data, and auxiliary data. The outgoing distilled MP3 data created by the device consists of a similar series of multiple pairs (each pair is a DistMP3 header, followed by a unit specification in a lossless simplified format). The DistMP3 header contains all components of the original frame except for the main data; that is, it contains the MP3 header, CRC, side information, and auxiliary data. The unit field in the distilled MP3 data contains particles specified in a lossless simplified form. The parser/factorizer 1864 performs the first decoding of the incoming MP3 encoded stream (including Huffman decoding) to extract the quantization frequency line 1851 and scaling factor 1852 (shown in Figure 18B), and generates audio particles 1865 as candidate units. The first decoding step performed by the parser/factorizer is the same as the synchronization and error checking 1851, Huffman decoding 1852, and scaling factor decoding 1853 steps in Figure 18B—these steps are performed in any standard MP3 decoder and are well known in the art. The basic data filter 1866 contains particles organized as basic data units for access in a content-associative manner. During the installation of particles in the basic data filter, the content of the particles is used to determine where the particle should be installed in the filter and to update the skeleton data structure and metadata in the appropriate leaf nodes of the filter. Subsequently, the particles are Huffman encoded and compressed so that the particle can be stored in the filter with a footprint no larger than it would occupy when residing in MP3 data. Whenever the exporter needs a particle in the filter as a basic data unit, the particle is decompressed before being provided to the exporter. Using a data distillation device, incoming audio particles are extracted by the extractor 1870 from the basic data units (which are also audio particles) residing in the filter, thereby creating a lossless simplified representation or distillation representation of the particles, which is then placed into the distilled MP3 data 1868. This distilled representation of the particles is placed in a unit field that replaces the Huffman-coded information originally present in the main data field of the MP3 frame. Using the format shown in Figure 1H, the distillation representation of each unit or particle is encoded—each unit in the distilled data is either a basic data unit (accompanied by a reference to the basic data unit or basic particle in the filter) or an extracted unit (accompanied by a reference to the basic data unit or basic particle in the filter, plus a reconstruction procedure from the referenced basic data unit, generating the extracted unit). During the extraction step, a threshold for accepting extracted items can be set to a portion of the size of the original Huffman-coded information residing in the main data field of the frame being simplified. Therefore, unless the sum of the reconstruction procedure and the references to the basic data units is less than the stated portion of the size of the corresponding main data field of the MP3 encoded frame (including Huffman-coded data), the derived item will not be accepted. If the sum of the reconstruction procedure and the references to the basic data units is less than the stated portion of the size of the existing main data field of the encoded MP3 frame (including Huffman-coded data), then it can be decided to accept the derived item.

The method described above enables the global utilization of redundancy across multiple audio particles stored in the device. MP3 encoded data files can be transformed into distilled MP3 data and stored in a lossless, simplified form. When retrieval is required, a data retrieval process (using retrieval unit 1871 and reconstructor 1872) can be invoked to reconstruct the MP3 encoded data 1873. In the device shown in Figure 18C, the reconstructor is responsible for performing the reconstruction procedure to generate the desired particles. Furthermore, it is enhanced to perform the Huffman coding steps required to generate the MP3 encoded data (represented as Huffman coding 1811 in Figure 18A). This data can then be fed to a standard MP3 decoder for audio playback.

In this way, data distillation devices can be modified and employed to further reduce the size of MP3 audio files.

In another variation of the scheme, upon receiving the MP3 encoded stream, the parser/factor treats the entire main data field as candidate units for derivation, or as basic data units to be loaded into the basic data filter. In this variation, all units remain in Huffman-coded state, and the reconstruction process operates on the units that have already been Huffman-coded. This variation of the data distillation device can also be used to further reduce the size of the MP3 audio file.

In a manner similar to that described in the preceding sections and illustrated in Figures 18A-18C, the Data Distillation ^™ apparatus can be used for the purpose of lossless simplification of video data. This data simplification is achieved by deriving components of video data from basic data units residing in a content-associative filter. The video data stream contains audio and moving picture components. Methods for distilling the audio components have already been described. The moving picture components will now be addressed. Moving picture components are typically organized into a series of picture groups. A picture group begins with an I-frame and is typically followed by multiple prediction frames (called P-frames and B-frames). I-frames are typically large and contain a complete snapshot of the picture, while the prediction frames are derived after employing techniques such as motion estimation relative to the I-frames or other derived frames. Some embodiments of the Data Distillation ^™ apparatus extract I-frames as units from the video data and perform a data distillation process on them, thereby retaining certain I-frames as basic data units residing in the content-associative filter, while the remaining I-frames are derived from these basic data units. The described method enables the utilization of redundancy across multiple I-frames within a video file and globally across multiple video files. Since I-frames are typically large components of moving image data, this method will reduce the footprint of the moving image components. Applying distillation techniques to both audio and moving image components will help to losslessly simplify the overall size of the video data.

Figure 19 illustrates how the data distillation apparatus, first shown in Figure 1A, can be enhanced to simplify video data. Video data stream 1902 is received by data distillation apparatus 1903 and simplified into a distilled video data stream 1908 stored in a lossless simplified form. The incoming video data stream 1902 comprises two components—compressed moving picture data and compressed audio data. The outgoing distilled video data created by this apparatus also comprises two components, namely, compressed moving picture data and compressed audio data; however, the size of these components is further reduced by data distillation apparatus 1903. A parser/decomposer 1904 extracts the compressed moving picture data and compressed audio data from the video data stream 1902 and extracts (including performing any necessary Huffman decoding) in-frames (I-frames) and prediction frames from the compressed moving picture data. The I-frames are used as candidate units 1905 to perform content association lookups in a basic data filter 1906. The exporter 1910 uses the set of basic data units (i.e., I-frames) returned by the basic data filter 1906 to generate a lossless simplified representation or distillation representation of the I-frame, and the lossless simplified I-frame is placed in the distilled video data 1908. The distillation representation is encoded using the format shown in Figure 1H—each unit in the distilled data is either a basic data unit (accompanied by a reference to the basic data units in the filter) or an exported unit (accompanied by a reference to the basic data units in the filter and a reconstruction procedure that generates the exported unit from the referenced basic data units). During the export step, a threshold for accepting the export can be set as a fraction of the size of the original I-frame. Therefore, an export will not be accepted unless the sum of the reconstruction procedure and the references to the basic data units is less than this fraction of the size of the corresponding I-frame. If the sum of the reconstruction procedure and the references to the basic data units is less than this fraction of the size of the original I-frame, a decision can be made to accept the export.

The method described above enables the global utilization of redundancy across multiple I-frames from multiple video datasets stored in the device. When retrieval is needed, the data retrieval process (using retriever 1911 and reconstructor 1912) can be invoked to reconstruct the video data 1913. In the device shown in Figure 19, the reconstructor is responsible for performing the reconstruction procedure to generate the desired I-frame. It is also enhanced to combine compressed audio data with compressed moving picture data (essentially the inverse operation of the extraction operation performed by parser & decomposer 1904) to generate the video data 1913. This data can then be fed into a standard video decoder for video playback.

In this way, the data distillation device can be adapted and used to further reduce the size of video files.

The foregoing description is provided to enable those skilled in the art to make and use the described embodiments. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art without departing from the spirit and scope of this disclosure, and the general principles defined herein are applicable to other embodiments and applications. Therefore, the invention is not limited to the illustrated embodiments, but should be given the broadest scope consistent with the principles and features disclosed herein.

The data structures and code described in this disclosure may be stored, in part or in whole, on computer-readable storage media and/or hardware modules and/or hardware devices. Computer-readable storage media include, but are not limited to, volatile memory, non-volatile memory, magnetic and optical storage devices (such as disk drives, magnetic tapes, CDs (compact discs), DVDs (Digital Universal Discs or Digital Video Discs)), or other media now known or hereafter developed capable of storing code and/or data. Hardware modules or devices described in this disclosure include, but are not limited to, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), dedicated or shared processors, and/or other hardware modules or devices now known or hereafter developed.

The methods and processes described in this disclosure can be implemented, in part or in whole, as code and/or data stored in a computer-readable storage medium or device, such that when a computer system reads and executes the code and/or data, the computer system performs the associated methods and processes. The methods and processes can also be implemented, in part or in whole, in a hardware module or device, such that when the hardware module or device is activated, it performs the associated methods and processes. It should be noted that the methods or processes can be implemented using a combination of code, data, and hardware modules or devices.

The foregoing description of embodiments of the present invention is provided for illustrative purposes only. The description is not intended to be exhaustive or to limit the invention to the disclosed forms. Therefore, many modifications and variations will occur to those skilled in the art. Furthermore, the foregoing disclosure is not intended to limit the invention.

Claims (30)

1. A method for simplifying video data to obtain simplified video data, the method comprising: Compressed moving image data and compressed audio data are extracted from the video data; Extract inner frames (I-frames) from the compressed moving image data; Extract the predicted frames from the compressed moving image data; Maintain the data structure of the organization's basic data units, each of which consists of a sequence of bytes; Losslessly simplify I-frames to obtain losslessly simplified I-frames, wherein the losslessly simplified I-frames consist of, for each I-frame: The first set of basic data units is identified by using I-frames to perform a first content association lookup on the data structure of basic data units organized based on basic data units, and... The first set of basic data units is used to losslessly simplify an I-frame so that (i) if the I-frame is a copy of a basic data unit in the first set of basic data units, a reference to that basic data unit is obtained, or (ii) if the I-frame is not a copy of any basic data unit in the first set of basic data units, a reference to one or more basic data units in the first set of basic data units and a transform sequence from said one or more basic data units is obtained; and The simplified video data mentioned therein includes lossless simplified I-frames, basic data units referenced by the lossless simplified I-frames, predicted frames, and compressed audio data. 2. The method of claim 1, wherein using the first set of basic data units to losslessly simplify the I-frame comprises: In response to determining that the sum of (i) the size of the references to the first set of basic data units and (ii) the size of the description of the reconstruction procedure is less than a threshold proportion of the size of the I-frame, a first lossless simplified representation of the I-frame is generated, wherein the first lossless simplified representation includes a reference to each basic data unit in the first set of basic data units and a description of the reconstruction procedure; and In response to determining that the sum of (i) the size of the reference to the first set of basic data units and (ii) the size of the description of the reconstruction procedure is greater than or equal to a threshold proportion of the size of the I-frame, In the data structure, I-frames are added as new basic data units, and A second lossless simplified representation of an I-frame is generated, wherein the second lossless simplified representation includes a reference to the new basic data unit. 3. The method of claim 2, wherein the description of the reconstruction procedure specifies a transformation sequence that generates an I-frame when applied to the first set of basic data units. 4. The method of claim 1, wherein the method further comprises: The compressed audio data is decompressed to obtain a set of audio components; and For each audio component in the set of audio components The second set of basic data units is identified by performing a second content association lookup on the data structure of the basic data units based on the content organization using this audio component, and The second set of basic data units is used to losslessly simplify the audio component; and The simplified video data includes lossless simplified I-frames, basic data units referenced by the lossless simplified I-frames, prediction frames, lossless simplified audio components, and basic data units referenced by the lossless simplified audio components. 5. The method of claim 4, wherein using the second set of basic data units to losslessly simplify the audio component comprises: In response to determining that the sum of (i) the size of the references to the second set of basic data units and (ii) the size of the description of the reconstruction procedure is less than a threshold proportion of the size of the audio component, a first lossless simplified representation of the audio component is generated, wherein the first lossless simplified representation includes a reference to each basic data unit in the second set of basic data units and a description of the reconstruction procedure; and In response to determining that the sum of (i) the size of the reference to the second set of basic data units and (ii) the size of the description of the reconstruction procedure is greater than or equal to a threshold proportion of the size of the audio component, The audio components are added as new basic data units to the data structure, and A second lossless simplified representation of the audio component is generated, wherein the second lossless simplified representation includes a reference to the new basic data unit. 6. The method of claim 5, wherein the description of the reconstruction procedure specifies a transformation sequence that, when applied to the second set of basic data units, generates the audio components. 7. The method of claim 1, further comprising: In response to receiving a request to retrieve video data, Recreating compressed moving image data includes reconstructing the I-frame from the lossless simplified I-frame and the basic data units referenced by the lossless simplified I-frame, and combining the I-frame with the predicted frame. The compressed moving image data is combined with the compressed audio data to obtain the video data. 8. The method of claim 1, wherein extracting an I-frame from the compressed moving image data includes performing Huffman decoding. 9. The method of claim 8, further comprising performing Huffman coding on the lossless simplified I-frame and the basic data unit referenced by the lossless simplified I-frame to obtain a Huffman-coded lossless simplified I-frame and a Huffman-coded basic data unit, respectively, wherein the simplified video data includes the Huffman-coded lossless simplified I-frame, the Huffman-coded basic data unit, the predicted frame, and the compressed audio data. 10. The method of claim 9, further comprising: In response to receiving a request to retrieve video data, The compressed motion picture data is recreated by (1) performing Huffman decoding on a lossless simplified I-frame encoded with Huffman to obtain a lossless simplified I-frame, and performing Huffman decoding on a Huffman-coded basic data unit to obtain a basic data unit; (2) reconstructing an I-frame from the lossless simplified I-frame and the basic data unit; and (3) performing Huffman coding on the I-frame and combining it with the predicted frame. The compressed moving image data is combined with the compressed audio data to obtain the video data. 11. A computer-readable storage medium storing instructions, said instructions, when executed by a computer, causing the computer to perform a method for simplifying video data to obtain simplified video data, said method comprising: Compressed moving image data and compressed audio data are extracted from the video data; Extract inner frames (I-frames) from the compressed moving image data; Extract the predicted frames from the compressed moving image data; Maintain the data structure of the organization's basic data units, each of which consists of a sequence of bytes; Losslessly simplify I-frames to obtain losslessly simplified I-frames, wherein the losslessly simplified I-frames consist of, for each I-frame: The first set of basic data units is identified by using I-frames to perform a first content association lookup on the data structure of basic data units organized based on basic data units, and... The first set of basic data units is used to losslessly simplify an I-frame so that (i) if the I-frame is a copy of a basic data unit in the first set of basic data units, a reference to that basic data unit is obtained, or (ii) if the I-frame is not a copy of any basic data unit in the first set of basic data units, a reference to one or more basic data units in the first set of basic data units and a transform sequence from said one or more basic data units is obtained; and The simplified video data mentioned therein includes lossless simplified I-frames, basic data units referenced by the lossless simplified I-frames, predicted frames, and compressed audio data. 12. The computer-readable storage medium of claim 11, wherein using the first set of basic data units to losslessly simplify an I-frame comprises: In response to determining that the sum of (i) the size of the references to the first set of basic data units and (ii) the size of the description of the reconstruction procedure is less than a threshold proportion of the size of the I-frame, a first lossless simplified representation of the I-frame is generated, wherein the first lossless simplified representation includes a reference to each basic data unit in the first set of basic data units and a description of the reconstruction procedure; and In response to determining that the sum of (i) the size of the reference to the first set of basic data units and (ii) the size of the description of the reconstruction procedure is greater than or equal to a threshold proportion of the size of the I-frame, In the data structure, I-frames are added as new basic data units, and A second lossless simplified representation of an I-frame is generated, wherein the second lossless simplified representation includes a reference to the new basic data unit. 13. The computer-readable storage medium of claim 12, wherein the description of the reconstruction procedure specifies a transformation sequence that generates an I-frame when applied to the first set of basic data units. 14. The computer-readable storage medium of claim 11, wherein the method further comprises: The compressed audio data is decompressed to obtain a set of audio components; and For each audio component in the set of audio components The second set of basic data units is identified by performing a second content association lookup on the data structure of the basic data units based on the content organization using this audio component, and The second set of basic data units is used to losslessly simplify the audio component; and The simplified video data includes lossless simplified I-frames, basic data units referenced by the lossless simplified I-frames, prediction frames, lossless simplified audio components, and basic data units referenced by the lossless simplified audio components. 15. The computer-readable storage medium of claim 14, wherein using the second set of basic data units to losslessly simplify the audio component comprises: In response to determining that the sum of (i) the size of the references to the second set of basic data units and (ii) the size of the description of the reconstruction procedure is less than a threshold proportion of the size of the audio component, a first lossless simplified representation of the audio component is generated, wherein the first lossless simplified representation includes a reference to each basic data unit in the second set of basic data units and a description of the reconstruction procedure; and In response to determining that the sum of (i) the size of the reference to the second set of basic data units and (ii) the size of the description of the reconstruction procedure is greater than or equal to a threshold proportion of the size of the audio component, The audio components are added as new basic data units to the data structure, and A second lossless simplified representation of the audio component is generated, wherein the second lossless simplified representation includes a reference to the new basic data unit. 16. The computer-readable storage medium of claim 15, wherein the description of the reconstruction procedure specifies a transformation sequence that, when applied to the second set of basic data units, generates the audio components. 17. The computer-readable storage medium of claim 11, further comprising: In response to receiving a request to retrieve video data, Recreating compressed moving image data includes reconstructing the I-frame from the lossless simplified I-frame and the basic data units referenced by the lossless simplified I-frame, and combining the I-frame with the predicted frame. The compressed moving image data is combined with the compressed audio data to obtain the video data. 18. The computer-readable storage medium of claim 11, wherein extracting an I-frame from the compressed moving picture data includes performing Huffman decoding. 19. The computer-readable storage medium of claim 18, further comprising performing Huffman coding on the lossless simplified I-frame and the basic data unit referenced by the lossless simplified I-frame to obtain a Huffman-coded lossless simplified I-frame and a Huffman-coded basic data unit, respectively, wherein the simplified video data includes the Huffman-coded lossless simplified I-frame, the Huffman-coded basic data unit, the predicted frame, and compressed audio data. 20. The computer-readable storage medium of claim 19, further comprising: In response to receiving a request to retrieve video data, The compressed motion picture data is recreated by (1) performing Huffman decoding on a lossless simplified I-frame encoded with Huffman to obtain a lossless simplified I-frame, and performing Huffman decoding on a Huffman-coded basic data unit to obtain a basic data unit; (2) reconstructing an I-frame from the lossless simplified I-frame and the basic data unit; and (3) performing Huffman coding on the I-frame and combining it with the predicted frame. The compressed moving image data is combined with the compressed audio data to obtain the video data. 21. An electronic device comprising: processor; and A memory storing instructions, which, when executed by the processor, cause the processor to perform a method for simplifying video data to obtain simplified video data, the method comprising: Compressed moving image data and compressed audio data are extracted from the video data; Extract inner frames (I-frames) from the compressed moving image data; Extract the predicted frames from the compressed moving image data; Maintain the data structure of the organization's basic data units, each of which consists of a sequence of bytes; Losslessly simplify I-frames to obtain losslessly simplified I-frames, wherein the losslessly simplified I-frames consist of, for each I-frame: The first set of basic data units is identified by using I-frames to perform a first content association lookup on the data structure of basic data units organized based on basic data units, and... The first set of basic data units is used to losslessly simplify an I-frame so that (i) if the I-frame is a copy of a basic data unit in the first set of basic data units, a reference to that basic data unit is obtained, or (ii) if the I-frame is not a copy of any basic data unit in the first set of basic data units, a reference to one or more basic data units in the first set of basic data units and a transform sequence from said one or more basic data units is obtained; and The simplified video data mentioned therein includes lossless simplified I-frames, basic data units referenced by the lossless simplified I-frames, predicted frames, and compressed audio data. 22. The electronic device of claim 21, wherein using the first set of basic data units to losslessly simplify an I-frame comprises: In response to determining that the sum of (i) the size of the references to the first set of basic data units and (ii) the size of the description of the reconstruction procedure is less than a threshold proportion of the size of the I-frame, a first lossless simplified representation of the I-frame is generated, wherein the first lossless simplified representation includes a reference to each basic data unit in the first set of basic data units and a description of the reconstruction procedure; and In response to determining that the sum of (i) the size of the reference to the first set of basic data units and (ii) the size of the description of the reconstruction procedure is greater than or equal to a threshold proportion of the size of the I-frame, In the data structure, I-frames are added as new basic data units, and A second lossless simplified representation of an I-frame is generated, wherein the second lossless simplified representation includes a reference to the new basic data unit. 23. The electronic device of claim 22, wherein the description of the reconstruction procedure specifies a transformation sequence that generates an I-frame when applied to the first set of basic data units. 24. The electronic device of claim 21, wherein the method further comprises: The compressed audio data is decompressed to obtain a set of audio components; and For each audio component in the set of audio components, perform the following operations: The second set of basic data units is identified by performing a second content association lookup on the data structure of the basic data units based on the content organization using this audio component, and The second set of basic data units is used to losslessly simplify the audio component; and The simplified video data includes lossless simplified I-frames, basic data units referenced by the lossless simplified I-frames, prediction frames, lossless simplified audio components, and basic data units referenced by the lossless simplified audio components. 25. The electronic device of claim 24, wherein using the second set of basic data units to losslessly simplify the audio component comprises: In response to determining that the sum of (i) the size of the references to the second set of basic data units and (ii) the size of the description of the reconstruction procedure is less than a threshold proportion of the size of the audio component, a first lossless simplified representation of the audio component is generated, wherein the first lossless simplified representation includes a reference to each basic data unit in the second set of basic data units and a description of the reconstruction procedure; and In response to determining that the sum of (i) the size of the reference to the second set of basic data units and (ii) the size of the description of the reconstruction procedure is greater than or equal to a threshold proportion of the size of the audio component, The audio components are added as new basic data units to the data structure, and A second lossless simplified representation of the audio component is generated, wherein the second lossless simplified representation includes a reference to the new basic data unit. 26. The electronic device of claim 25, wherein the description of the reconstruction procedure specifies a transformation sequence that, when applied to the second set of basic data units, generates the audio component. 27. The electronic device of claim 21, further comprising: In response to receiving a request to retrieve video data, Recreating compressed moving image data includes reconstructing the I-frame from the lossless simplified I-frame and the basic data units referenced by the lossless simplified I-frame, and combining the I-frame with the predicted frame. The compressed moving image data is combined with the compressed audio data to obtain the video data. 28. The electronic device of claim 21, wherein extracting an I-frame from the compressed moving image data includes performing Huffman decoding. 29. The electronic device of claim 28, further comprising performing Huffman coding on the lossless simplified I-frame and the basic data unit referenced by the lossless simplified I-frame to obtain a Huffman-coded lossless simplified I-frame and a Huffman-coded basic data unit, respectively, wherein the simplified video data includes the Huffman-coded lossless simplified I-frame, the Huffman-coded basic data unit, the predicted frame, and compressed audio data. 30. The electronic device of claim 29, further comprising: In response to receiving a request to retrieve video data, The compressed motion picture data is recreated by (1) performing Huffman decoding on a lossless simplified I-frame encoded with Huffman to obtain a lossless simplified I-frame, and performing Huffman decoding on a Huffman-coded basic data unit to obtain a basic data unit; (2) reconstructing an I-frame from the lossless simplified I-frame and the basic data unit; and (3) performing Huffman coding on the I-frame and combining it with the predicted frame. The compressed moving image data is combined with the compressed audio data to obtain the video data.