DETAILED ACTION
This office action is in response to claims filed 28 February 2024.
Claims 1-19 are pending.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Examiner’s Note
Claims 15 and 16 were not rejected using prior art, but stand rejected under other statutes
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: “division unit”, “compression processing unit”, “probability calculation unit”, “entropy coding unit”, “mixer model”, “learning unit”, “model selection unit”, “history management unit”, “conversion unit”, “reception unit”, “storage processing unit”, “data reduction unit”, “decompression processing unit”, “second probability calculation unit”, “entropy decoding unit”, “decompression unit”, “second block corresponding guarantee code creation unit”, “first block guarantee code creation unit”, in claims 1-17.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof, comprising a processor executing instructions stored in memory to implement the units, as described in [0037].
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-19 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claim 1,
a. In line 6: The claim fails to particularly point out and distinctly claim what is meant by the term “the compression processing unit”, because there is a lack of antecedent basis. For examination purposes this will be interpreted as one of the plurality of compression processing units.
b. In line 10: The claim fails to particularly point out and distinctly claim what is meant by the terms “the data unit” and “each data unit”, because there is a lack of antecedent basis. For examination purposes this will be interpreted as one of the plurality of predetermined data units.
Regarding claim 14, and 16 (line numbers correspond to claim 14)
In line 4: The claim fails to particularly point out and distinctly claim what is meant by the term “the decompression processing unit”, because there is a lack of antecedent basis. For examination purposes this will be interpreted as one of the plurality of decompression processing units.
Regarding claims 2-17, they are dependent claims that fail to resolve the deficiencies of the parent claim, and are therefore rejected for similar rationale.
Regarding claim 18, it comprises limitations similar to claim 1, and includes the same deficiencies of claim 1.
Regarding claim 19, it comprises limitations similar to claim 1, and includes the same deficiency discussed in 8.b.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-3, 9, 13-14, and 18-19 are rejected under 35 U.S.C. 103 as being unpatentable over MINNEN et al. Pub. No.: US 2019/0356330 A1 (hereafter MINNEN), in view of CHANG et al. WO 2013/071721 A1 (hereafter CHANG).
Regarding claim 1, MINNEN teaches the invention substantially as claimed, including:
A data compression system that compresses data ([0058] The system receives data to be compressed (i.e., “compression target data”) (302)), the system comprising:
a division unit that divides compression target data into a plurality of pieces of partial data ([0063] The system identifies a partition of the collection of code symbols into one or more code symbol subsets (i.e., code symbol subsets represent “pieces of partial data”)); and
a [compression processing unit to] perform compression processing on each piece of the partial data in parallel ([0103] the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some cases, multitasking and parallel processing may be advantageous), wherein
the compression processing unit includes
a probability calculation unit that includes a neural network and calculates an appearance probability for each predetermined data unit of the partial data ([0062] The encoder neural network processes the input in accordance with current values of encoder neural network parameters to generate an output that defines the collection of code symbols [0069] The system determines a compressed representation of each code symbol subset (314). The compressed representation of each code symbol subset may include: (i) the entropy encoded representation of the code symbol subset (e.g., as described with reference to 312)…if the code symbol probability distribution used to entropy encode the code symbol subset is a custom code symbol probability distribution, then the data indicating the custom code symbol probability distribution may include a respective custom probability value for each code symbol in the discrete set of possible code symbols (i.e., custom code symbol probability distribution represents a probability that a particular code symbol “appears” in a set of code symbols, representing a “data unit”)), and
an entropy coding unit that outputs a coded bit string that is an entropy-coded bit string based on the data unit and the appearance probability for each data unit ([0070] The system determines a compressed representation of the data (316). The system may determine the compressed representation of the data based on: (i) the compressed representation of each code symbol subset (e.g., as described with reference to 314), and (ii) representations of any custom code symbol probability distributions used to entropy encode any of the code symbol subsets. The compressed representation of the data may be represented in any appropriate format. For example, the compressed representation of the data may be numerically represented as binary data (i.e., a stream of binary data represents a “coded bit stream”)).
While MINNEN discusses performing compression processing on pieces of partial data in parallel (see for example, [0103]), MINNEN does not explicitly teach:
a plurality of compression processing units that perform compression processing on each piece of the partial data in parallel,
However, in analogous art that similarly discusses performing compression processing in parallel, CHANG teaches:
a plurality of compression processing units that perform compression processing on each piece of the partial data in parallel ([0005] Said encoding the first video parameters to generate the current first compressed data may utilize a first entropy coder, and wherein said encoding the second video parameters to generate the current second compressed data utilizes the first entropy coder or a second entropy coder. [0006] In yet another embodiment according to the present invention, the first logic unit may be further partitioned into multiple sub-logic units, where each sub- logic unit corresponds to first compressed data associated with the coding units associated with a region of the picture. The region of the picture may be may be a row of coding units or multiple rows of coding units. The multiple sub-logic units may share a same entropy coder or use multiple entropy coders in parallel),
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined CHANG’s teaching of performing entropy encoding on partial data using a plurality of parallel encoders, with MINNEN’s teaching of performing entropy encoding in parallel, to realize, with a reasonable expectation of success, a system that performs entropy encoding in parallel, as in MINNEN, using parallel encoders, as in CHANG. A person having ordinary skill would have been motivated to make this combination to leverage advantages of parallel processing such as improved throughput and scalability.
Regarding claim 2, MINNEN further teaches:
the probability calculation unit includes an estimation model that calculates estimation information for each data unit, and the estimation model is configured with a neural network ([0069] The system determines a compressed representation of each code symbol subset (314). The compressed representation of each code symbol subset may include: (i) the entropy encoded representation of the code symbol subset (e.g., as described with reference to 312)…if the code symbol probability distribution used to entropy encode the code symbol subset is a custom code symbol probability distribution, then the data indicating the custom code symbol probability distribution may include a respective custom probability value for each code symbol in the discrete set of possible code symbols (i.e., custom code symbol probability distribution represents a probability or “estimation” that a particular code symbol “appears” in a set of code symbols, representing a “data unit”)).
Regarding claim 3, MINNEN further teaches:
the estimation model is configured with a neural network including processing of reducing a length direction ([0011] The code symbol probability distribution for the code symbol subset is identified to be a code symbol probability distribution from the dictionary with a minimal corresponding length of entropy encoded representation (i.e., goal of probability distribution is to minimize, or “reduce” length of representation)).
Regarding claim 9, MINNEN further teaches:
a reception unit that receives a command identification code and data related to compression of the compression target data ([0058] The system receives data to be compressed (302). The data may be image data, audio data, video data, or any other form of data. [0088] For one or more computer programs to be configured to perform particular operations or actions means that the one or more programs include instructions that, when executed by data processing apparatus, cause the apparatus to perform the operations or actions (i.e., system receives data to be compressed and instructions causing the system to perform compression on the data)), wherein the compression processing unit compresses data based on the command identification code and data ([0069] The system determines a compressed representation of each code symbol subset (314) (i.e., executing instructions causes the data to be compressed)).
Regarding claim 13, MINNEN further teaches:
the compression target data is predetermined media data ([0034] The data to be compressed can be image data, video data, or any other type of data), the data compression system further comprises a data reduction unit that reduces data volume of the compression target data, and the division unit divides the compression target data after data reduction in which the data volume is reduced by the data reduction unit ([0060] The system can generate the collection of code symbols by any appropriate means. For example, the system may determine the coefficients of a set of basis functions (e.g., Fourier basis functions) that represent the data, and generate the collection of code symbols by quantizing the coefficients to integer values within a bounded range (i.e., in generating collection of code symbols based on quantizing coefficients to integer values within a bounded range, the system reduces the volume of input data to only values within the range)).
Regarding claim 14, MINNEN further teaches:
a plurality of decompression processing units that perform decompression processing ([0038] FIG. 6 is a flow diagram of an example process for determining a reconstruction of data from a compressed representation of the data. For convenience, the process 600 will be described as being performed by a system of one or more computers located in one or more locations. For example, a decoding system, e.g., the decoding system 200 of FIG. 2, appropriately programmed in accordance with this specification, can perform the process 600.) on each coded bit string corresponding to the plurality of pieces of partial data ([0084] The system receives a compressed representation of the data (e.g., the data compressed by an encoding system, as described with reference to FIG. 3) (602). The compressed representation of the data includes a compressed representation of each of one or more of the code symbol subsets representing the data (e.g., as described with reference to 306)), and
the decompression processing unit includes
a second probability calculation unit that includes a neural network and calculates an appearance probability for each predetermined data unit of the partial data ([0084] The compressed representation of each code symbol subset may include: (i) an entropy encoded representation of the code symbol subset, and (ii) data indicating a code symbol probability distribution (i.e., “appearance probability”) used to entropy encode the code symbol subset (e.g., as described with reference to 314). [0085] For each compressed representation of a code symbol subset, the system determines the code symbol subset based on the code symbol probability distribution used to entropy encode the code symbol subset (604)), and
an entropy decoding unit that outputs an entropy-decoded data unit based on the coded bit string and the appearance probability ([0087] The system determines an (approximate or exact) reconstruction of the data based on the ordered collection of code symbols (608). For example, if the ordered collection of code symbols are the coefficients of a representation of the data with respect to a set of basis functions (e.g., the Fourier basis), then the system may determine a reconstruction of the data as a linear combination of the basis functions with coefficients given by the collection of code symbols. As another example, if the ordered collection of code symbols are the output of an encoder neural network, then the system may determine a reconstruction of the data by providing the collection of code symbols as an input to a decoder neural network. The decoder neural network is configured to process the collection of code symbols in accordance with current values of decoder neural network parameters to generate an output that defines a reconstruction of the data (i.e., reconstruction of data represents entropy decoded data associated with a decoder neural network and based on the appearance probability)).
Regarding claims 18, and 19, they comprise limitations similar to claim 1, and are therefore rejected for similar rationale.
Claim 4 is rejected under 35 U.S.C. 103 as being unpatentable over MINNEN, in view of CHANG, as applied to claim 1 above, and in further view of BEN-ITZHAK et al. Pub. No.: US 2021/0397990 A1 (hereafter BEN-ITZHAK).
Regarding claim 4, while MINNEN and CHANG discuss encoding data using machine learning models, they do not explicitly teach:
the probability calculation unit is configured with a plurality of estimation models that calculate estimation information for each data unit, and
includes a mixer model that determines an appearance probability of each data unit based on estimation information output by the plurality of estimation models.
However, in analogous art that similarly discusses encoding data using machine learning models, BEN-ITZHAK teaches:
the probability calculation unit is configured with a plurality of estimation models that calculate estimation information for each data unit, and includes a mixer model that determines an appearance probability of each data unit based on estimation information output by the plurality of estimation models ([0012] [0012] FIG. 1 depicts a computing device/system 100 that implements the predictability-driven compression techniques of the present disclosure. As shown, computing device/system 100 comprises a data set compression module 102 that includes a simple ML model S (reference numeral 104), a predictability computation component 106, and a filtering component 108. Data set compression module 102, which may be implemented in software, hardware, or a combination thereof, is configured to receive as input a training data set X (reference numeral 110) and to generate as output a compressed version of X (i.e., compressed training data set X′; reference numeral 112). [0022] Although FIG. 1 depicts a particular arrangement of components within data set compression module 102, other arrangements are possible (e.g., the functionality attributed to a particular component may be split into multiple components, components may be combined, etc.) and each component may include sub-components or implement functions that are not specifically described. For example, in a particular embodiment simple ML model S may be composed of an ensemble of multiple ML models and the predictability measures may be calculated as a function of the multiple models' outputs (e.g., average, median, etc.) (i.e., system averages, or “mixes” outputs of multiple machine learning models representing “estimation models” to determine appearance predictability, or “probability”)).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined BEN-ITZHAK’s teaching of averaging output from a plurality of machine learning models to calculate predictability measures, with the combination of MINNEN and CHANG’s teaching of calculating predictability measures for use in entropy-based encoding, to realize, with a reasonable expectation of success, a system that performs entropy-based encoding of data by calculating predictability measures, as in MINNEN and CHANG, based on the average of multiple machine learning model outputs, as in BEN-ITZHAK. A person having ordinary skill would have been motivated to make this combination to improve accuracy of the predictability measures.
Claim 5 is rejected under 35 U.S.C. 103 as being unpatentable over MINNEN, in view of CHANG, in view of BEN-ITZHAK, as applied to claim 4 above, and in further view of HALOWANI et al. Pub. No.: US 2007/0233477 A1 (hereafter HALOWANI).
Regarding claim 5, while MINNEN, CHANG, and BEN-ITZHAK discuss performing data compression using neural networks, they do not explicitly teach:
the mixer model includes weights for outputs from a plurality of estimation models, the data compression system further comprises:
a learning unit that determines weights for the estimation model by performing learning processing on the mixer model; and a model selection unit that selects an estimation model to be used by the probability calculation unit based on the weights.
However, in analogous art that similarly discusses performing lossless data compression using neural networks, HALOWANI teaches:
the mixer model includes weights for outputs from a plurality of estimation models, the data compression system further comprises: a learning unit that determines weights for the estimation model by performing learning processing on the mixer model; and a model selection unit that selects an estimation model to be used by the probability calculation unit based on the weights ([0014] Disclosed is a computer program for lossless compression of data. The program is comprised of a plurality of independent sub-models, wherein each sub-model provides an output of prediction of the next pattern of the input data and its probability in accordance with different context type. The program also comprises a neural network mapping module for processing the output of all sub modules, performing an updating process of the current maps of the adaptive model weights. The adaptive model includes weights representing the success rate of the different models prediction, a decoder for implementing the proper sub module on the input data and an optimizer module for filtering duplicate text patterns. [0015] The computer program may also include at least one mixer module, for processing parts of the sub-models output by assigning weights to each model in accordance with the prediction pattern success rate. The output of each mixer is fed to the neural network mapping module (i.e., output of sub-models representing “estimation models” are weighed and mixed by the mixers and neural network mapping module, resulting in a “selected model” used to make an input data prediction)).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined HALOWANI’s teaching of weighing output of sub-models used to predict input data patterns for use in lossless data compression, with the combination of MINNEN, CHANG, and BEN-ITZHAK’s teaching of combining output of prediction models for use in data compression, to realize, with a reasonable expectation of success, a system that combines output of prediction models for use in data compression, as in MINNEN, CHANG, and BEN-ITZHAK, where the outputs are weighted based on predicted success rate, as in HALOWANI. A person having ordinary skill would have been motivated to make this combination to improve prediction pattern success rate.
Claims 6, and 11 are rejected under 35 U.S.C. 103 as being unpatentable over MINNEN, in view of CHANG, as applied to claim 1 above, and in further view of SOFIA et al. Patent No.: US 10,666,289 B1 (hereafter SOFIA).
Regarding claim 6, while MINNEN and CHANG discuss data compression using entropy encoding, they do not explicitly teach:
a history management unit that stores history information in a storage unit, the history information including identification information for identifying data used during calculation which is data used to calculate an appearance probability of the data unit and the calculated appearance probability, wherein the probability calculation unit calculates an appearance probability based on the history information.
However, in analogous art that similarly discusses data compression using entropy encoding, SOFIA teaches:
a history management unit that stores history information in a storage unit, the history information including identification information for identifying data used during calculation ([Column 5, Lines 27-42] the encoder 104 compresses individual blocks of a data file independently and sequentially. In other embodiments, the encoder 104 operates on an entire data file during compression. The encoder 104 can initially store data blocks of data onto an input buffer 106. From the input buffer 106, a data block or a data file can be loaded into a history buffer 108. Each block of data can be a uniform size or the size may vary depending upon an application. The history buffer 108 can be configured to be the same size as a block of data or larger than a single block of data. At the history buffer 108, the encoder 104 replaces data with associated symbols from the dictionary 112. From time to time, the encoder 104 can scan the history buffer 108 and make additions or subtractions from a dictionary 112. After the block or data file has been encoded, the encoder 104 can output the compressed data to an output buffer 110 (i.e., data stored in the history buffer represents “history information”)) which is data used to calculate an appearance probability of the data unit and the calculated appearance probability, wherein the probability calculation unit calculates an appearance probability based on the history information ([Column 4, Lines 12-19] Entropy encoding is a lossless compression method of determining variable-length codes based upon the frequencies or probabilities that characters will appear in an input data set. Each symbol is assigned a respective prefix-free codeword. These codewords are associated with symbols of respective inputs and together comprise a dictionary of uniquely decodable prefix-free codewords that can be instantaneously decoded (i.e., entropy encoding based on frequency or probability of character appearance in input data is performed on data in the history buffer)).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined SOFIA’s teaching of a history buffer storing history information used to calculate probabilities that data will appear in a data set, with MINNEN and CHANG’s teaching of calculating probabilities that data will appear in a data set, to realize, with a reasonable expectation of success, a system that calculates probabilities that data will appear in a data set, as in MINNEN and CHANG, from history data, as in SOFIA. A person having ordinary skill would have been motivated to make this combination to better compress data to reduce the amount of storage space needed for a file, free that storage for other files, and decrease resources required for data transmission (SOFIA Column 1, Lines 18-26).
Regarding claim 11, while MINNEN and CHANG discuss data compression using entropy encoding, they do not explicitly teach:
a storage processing unit that stores coded bit strings corresponding to a plurality of pieces of the partial data such that the coded bit strings corresponding to each piece of partial data are identifiable.
However, in analogous art that similarly discusses entropy encoding of data, SOFIA teaches:
a storage processing unit that stores coded bit strings corresponding to a plurality of pieces of the partial data such that the coded bit strings corresponding to each piece of partial data are identifiable ([Column 7, Lines 20-26] Compressed data from the history buffer 202 is written to the output buffer 206. During this process, the encoder is continuously replacing data in the history buffer with symbols from the dictionary 204. The data blocks can be stored on a first in first out (FIFO) basis. The data blocks can be stored sequentially in the aggregate until the entire data stream is complete (i.e., identifiable compressed data is written to a output storage buffer). [Column 3, Line 61] Each symbol in the dictionary is a bit or a set of bits).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined SOFIA’s teaching of storing encoded data in an output buffer, with MINNEN and CHANG’s teaching of compressing data using entropy encoding, to realize, with a reasonable expectation of success, a system that compresses data using entropy encoding, as in MINNEN and CHANG, and storing compressed data in a storage buffer, as in SOFIA. A person having ordinary skill would have been motivated to make this combination to enable encoded data to be more easily accessed.
Regarding claim 12, SOFIA further teaches:
in the compression processing unit, regarding a coded bit string corresponding to a part of each piece of partial data, the probability calculation unit calculates an appearance probability for each predetermined data unit of each piece of partial data only for update data corresponding to a part of each piece of partial data, and outputs a coded bit string by the entropy coding unit ([Column 4, Lines 12-29] Entropy encoding is a lossless compression method of determining variable-length codes based upon the frequencies or probabilities that characters will appear in an input data set. Each symbol is assigned a respective prefix-free codeword. These codewords are associated with symbols of respective inputs and together comprise a dictionary of uniquely decodable prefix-free codewords that can be instantaneously decoded…dictionary-based compression algorithms store a dictionary of previously used symbols, codewords, and associated inputs to use when encoding future inputs. [Column 6, Lines 15-23] The dictionary 112 is a data structure for mapping symbols to inputs from data sets. The dictionary 112 can be in the form of a hash table, a red-black tree, or any other appropriate data structure. The dictionary 112 can be configured such that the dictionary 112 is static or dynamic (adaptive)…A dynamic dictionary stores strings found in input data streams and allows for the subtraction or addition of entries (i.e., entropy encoding is based upon appearance probabilities of characters associated with dynamically updated symbols, codewords, and inputs representing “update data”)).
Claim 7 is rejected under 35 U.S.C. 103 as being unpatentable over MINNEN, in view of CHANG, as applied to claim 1 above, and in further view of LIN, RUEI-SUNG et al. “SPEC Hashing: Similarity Preserving algorithm for Entropy-based Coding”. Available 2010 (hereafter LIN).
Regarding claim 7, while MINNEN and CHANG discuss performing entropy-based encoding, they do not explicitly teach:
the history management unit calculates locality sensitive hashing (LSH) corresponding to the data used during calculation as the identification information.
However, in analogous art that similarly teaches performing entropy-based encoding, LIN teaches:
the history management unit calculates locality sensitive hashing (LSH) corresponding to the data used during calculation as the identification information ([Section 1] With the advance of Internet, we are inundated with an abundance of data of images, documents, music, videos, etc. As the size of the data continues to grow, the density of similar objects in the data space also increases. These objects are likely to have similar semantics. As a result, inferences based on nearest neighbors can be more reliable than ever before… Searching nearest neighbors in sublinear time has been an ongoing research…Recently, Locality Sensitive Hashing (LSH) [2], [3] has been successfully applied to datasets with high dimensional features. It uses random projections to map objects from feature space to bits, and treats these bits as keys for multiple hash tables. As a result, the collision of similar samples in at least one hash bucket has high probability. This randomized algorithm has tight asymptotic bound (i.e., recent entropy-based coding includes calculation of LSH corresponding to data involving mapping, or keys, both of which may represent “identification information”)).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined LIN’s teaching of calculating LSH corresponding to data for entropy-based encoding, with the combination of MINNEN and CHANG’s teaching of performing entropy-based encoding of data to realize, with a reasonable expectation of success, a system that performs entropy-based encoding, as in MINNEN and CHANG, by calculating LSH corresponding to data, as in LIN. A person having ordinary skill would have been motivated to make this combination to improve nearest neighbor search in data encoding (LIN Section 1).
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over MINNEN, in view of CHANG, as applied to claim 1 above, and in further view of LI WO2023088562A1 (hereafter LI).
Regarding claim 8, while MINNEN and CHANG discuss performing entropy-based encoding, they do not explicitly teach:
the compression processing unit includes a conversion unit that inputs a bit string to the probability calculation unit, the bit string being obtained by performing one-hot encoding on each data unit of compression target data.
However, in analogous art that similarly discusses data compression using entropy encoders, LI teaches:
the compression processing unit includes a conversion unit that inputs a bit string to the probability calculation unit, the bit string being obtained by performing one-hot encoding on each data unit of compression target data ([Claim 1] training an autoencoder (200) for data compression, the autoencoder comprising a first neural network (204) for processing and downsampling input data to generate latent variables, a probability estimator (210) for determining probability mass functions of the latent variables, and an entropy encoder for compressing the latent variables based on the probability mass functions, the method comprising: inputting (302) training data into the first neural network to generate a plurality of first latent variables; using (304) the probability estimator to obtain respective probability mass functions for the plurality of first latent variables; determining (306) a first rate measure based on the probability mass functions and a plurality of coded latent variables, wherein the plurality of coded latent variables is based on one-hot encoding of a plurality of first quantized latent variables obtained by quantizing the plurality of first latent variables (i.e., one hot encoding is applied to quantized latent variables generated from the downsampled input data)).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined LI’s teaching of one-hot-encoding input data to obtain entropy-encoded data, with the combination of MINNEN and CHANG’s teaching of compressing data using entropy encoding, to realize, with a reasonable expectation of success, a system that compresses data using entropy encoding, as in MINNEN and CHANG, by one-hot-encoding input data, as in LI. A person having ordinary skill would have been motivated to make this combination to ensure input is converted into a format suitable for operation using machine learning models.
Claim 10 is rejected under 35 U.S.C. 103 as being unpatentable over MINNEN, in view of CHANG, as applied to claim 9 above, and in further view of NAKANISHI et al. Pub. No.: US 2020/0304142 A1 (hereafter NAKANISHI).
Regarding claim 10, while MINNEN and CHANG discuss entropy based compression of data, they do not explicitly teach:
a reception unit that receives hint information related to compression of the compression target data, wherein the probability calculation unit calculates a probability distribution for each data unit based on the hint information.
However, in analogous art that similarly discusses entropy based compression of data, NAKANISHI teaches:
a reception unit that receives hint information related to compression of the compression target data, wherein the probability calculation unit calculates a probability distribution for each data unit based on the hint information ([0019] A method of compressing the write data (e.g., user data) and writing the compressed write data into the nonvolatile memory has been developed. For this reason, the memory system has a data compression function. Thus, the memory system compresses the data to be written, and executes the write command to write the compressed write data into the nonvolatile memory. The user data is compressed using a lossless compression method. [0023] By estimating a compression ratio of the write data using compression-ratio estimation information linked to the write command (i.e., a hint of the compression ratio), and determining an execution order of the write command based on the estimated compression ratio, it is possible to prevent an increase in capacity of the buffer memory and improve efficiency in writing of the write data. The compression-ratio estimation information may be included in the write command. [0030] When the DMAC 5 issues a write command, the entropy calculation unit 5a obtains compression-ratio estimation information (for example, entropy information) as a hint of a compression ratio of write data corresponding to the write command by checking appearance frequencies of symbols in the write data. The DMAC 5 issues a write command including the compression-ratio estimation information obtained by the entropy calculation unit 5a (i.e., hint of a compression ratio corresponds to frequency of symbols in the write data, representing a “probability distribution for a data unit” and is “received” by the compression function for use in data compression)).
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to have combined NAKANISHI’s teaching of receiving a hint related to probability distribution to better calculate data compression, with the combination of MINNEN and CHANG’s teaching of calculating data compression, to realize, with a reasonable expectation of success, a system that calculates data compression, as in MINNEN and CHANG, by receiving a hint related to probability distribution, as in NAKANISHI. A person having ordinary skill would have been motivated to make this combination to prevent an increase in buffer memory capacity and improve write efficiency (NAKANISHI [0023]).
Claim 17 is rejected under 35 U.S.C. 103 as being unpatentable over MINNEN, in view of CHANG, as applied to claim 9 above, and in further view of HALLAK et al. Pub. No.: US 2019/0379394 A1 (hereafter HALLAK).
Regarding claim 17, while MINNEN and CHANG discuss entropy-based data encoding, they do not explicitly teach:
the compression processing unit uses reference information to the partial data as a compression result when overlap between previously processed partial data and the partial data is detected.
However, in analogous art that similarly discusses compression of data, HALLAK teaches:
the compression processing unit uses reference information to the partial data as a compression result when overlap between previously processed partial data and the partial data is detected ([0021] FIG. 1 shows an example flowchart illustrating a method for global compression of data according to an embodiment. [0027] At S130, the blocks are compared to identify similar blocks. In an embodiment, S130 includes using similarity hashing to compare each block to each other block. Specifically, one or more similarity hashes is computed for each block and the computed similarity hashes are compared among blocks. If two datasets are similar (i.e., their Levenshtein distance is below a threshold), there is a high likelihood that their similarity hashes will be the same. Similarly, if a Jaccard distance between blocks is below a threshold, the blocks are likely to be similar. Thus, when two blocks have the same similarity hash, the two blocks may be identified as similar. [0030] At S140, reference blocks are selected from among each set of similar blocks. [0031] At S150, redundant blocks are removed and replaced. In an embodiment, each redundant block is replaced with a reference to its respective similar reference block and a delta including data included in the redundant block that is not redundant with data of the reference block (i.e., redundant data blocks representing at least partially overlapping blocks are replaced with reference information)).
It would have been obvious to a person having ordinary skill to have combined HALLAK’s teaching of replacing overlapping data blocks with reference information when compressing data, with the combination of MINNEN and CHANG’s teaching of entropy-based data encoding, to realize, with a reasonable expectation of success, a system that performs entropy-based data encoding, as in MINNEN and CHANG, by replacing overlapping data blocks with reference data, as in HALLAK. A person having ordinary skill would have been motivated to make this combination to provide a global compression of data that demonstrates fine granularity, reduces capacity costs, and minimizes numbers of required reads and writes (HALLAK [0019]).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
PIAO et al. Pub. No.: US 2018/0205958 A1 discloses a device that encodes sub-blocks of data based on respective probabilities to be input to an entropy encoder that encodes an input signal using the probabilities.
TAKEDA Pub. No.: US 2023/0057659 A1 discloses an entropy encoder that uses deviation of appearance probability of bit data to convert data to encoded data.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MICHAEL W AYERS whose telephone number is (571)272-6420. The examiner can normally be reached M-F 8:30-5 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Aimee Li can be reached at (571) 272-4169. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/MICHAEL W AYERS/Primary Examiner, Art Unit 2195
Prosecution Insights