DETAILED ACTION
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 .
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 3, 10, and 17 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.
Claims 3, 10, and 17 recite the limitation of “the insertions sort" (emphasis added) at line 2. While there is antecedent basis for “insertion sort” there is no antecedent basis for “insertions sort.”
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.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
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:
Claim(s)
Limitation
Corresponding Structure
1, 8, 15
First Unit
Spec. [00242] states that a hybrid cascaded sort performed by processing logic comprising (1) hardware, (2) software, or (3) a combination of both.
As to (1) hardware implementations, Spec. [00238] Each block in Fig. 5 may be dedicated sorting hardware, which may be implemented in an FPGA. Spec. [0031] describes various hardware alternatives to FPGA including PLC, ASIC, and SOC.
As to (2) software implementations, Spec. [0031] describes for a software-based alternative: a processing device, a central processing unit, computer memory, or adapters.
As to (3), the Specification does not appear to describe any combination of hardware and software other than the general assertion that the system can be both. Since corresponding structure, material, or acts corresponding to a combination cannot be identified in the Specification for the combination of hardware and software in (3), the unit has not been construed to include both.
1, 8
Second Unit1
Spec. [00242] states that a hybrid cascaded sort performed by processing logic comprising (1) hardware, (2) software, or (3) a combination of both.
As to (1) hardware implementations, Spec. [00238] Each block in Fig. 5 may be dedicated sorting hardware, which may be implemented in an FPGA. Spec. [0031] describes various hardware alternatives to FPGA including PLC, ASIC, and SOC.
As to (2) software implementations, Spec. [0031] describes for a software-based alternative: a processing device, a central processing unit, computer memory, or adapters.
As to (3), the Specification does not appear to describe any combination of hardware and software other than the general assertion that the system can be both. Since corresponding structure, material, or acts corresponding to a combination cannot be identified in the Specification for the combination of hardware and software in (3), the unit has not been construed to include both.
.
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.
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 § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-3, 5-10, 12-17, and 19-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claim 1:
At step (1), claim 1 falls within one of the four statutory categories. It is directed to a method2.
At step 2A prong 1, claim 1 recites an abstract idea. The abstract idea is either mathematics or mental processes. The sorting of numbers is considered to be a topic in applied mathematics as shown by the MIT Principles of Discrete Applied Mathematics lecture notes. Both merge sort and insertion sort are described in the lecture notes. The sorting of numbers as claimed can is also reasonably be performed in the human mind with the aid of pen and paper. The Specification [00235] and Figure 4 explains how to sort 256 numbers with 8 32-value insertion sorts followed by 7 merge sorts of various sizes. Applicant’s example in the Specification falls within the scope of the claim and is therefore evidence of what can be reasonably performed in the human mind. Claim 1 recites an abstract idea as follows with the abstract idea underlined.
A method comprising:
receiving, by a processing device, an unsorted set of numbers to be sorted;
sorting, by a first unit of the processing device, a first subset of the unsorted set of numbers and a second subset of the unsorted set of numbers using an insertion sort of the first unit of the processing device to obtain a first sorted subset and a second sorted subset of numbers; and
merging and sorting, by a second unit of the processing device, the first sorted subset and the second sorted subset of numbers using a first-in first-out (FIFO) merge sort of the second unit of the processing device to obtain a first sorted set of numbers.
As to step 2A prong 2, the judicial expression is not integrated into a practical application. The claim recites the additional element of receiving, by a processing device, an unsorted set of numbers to be sorted. This additional element is nothing more than insignificant extra-solution activity directed to gathering the information necessary to perform the abstract idea. An unsorted set of numbers is a prerequisite to a meaningful sort. To the extent that the additional element says to perform the receiving in a processing device, the processing device is recited at a high level of generality and amounts to nothing more than instruction to apply the abstract idea in a computer. As to the first unit and the second unit, as explained in the Claim Interpretation section of this Office action, these limitations describe how the abstract idea is implemented either (1) in hardware using circuitry or (2) in software.using a processor and code. In both situations, The Specification describes the circuit or code algorithmically and at a high level of abstraction. At best, either claimed implementation is at best the equivalent of merely adding the words “apply it to the judicial exception. In conclusion, the additional elements do not, either alone or in combination, integrate the abstract idea into a practical application.
As to step 2B, the claim does not, alone or in combination, include additional elements that are sufficient to amount to significantly more than the judicial exception. The analysis at step 2B is essentially the same as the analysis at step 2A prong 2.
Claim 2:
At to claims 2, it merely introduces more method steps directed to the abstract idea and does not introduce any additional elements. As a result, the analysis for claim 2 is the same as for claim 1.
Claim 3:
At to claims 3, it merely introduces more method steps directed to the abstract idea and does not introduce any additional elements. Saying that a multi-step abstract idea like insertion sorting is pipelined is merely an additional characterization of the abstract idea. As a result, the analysis for claim 2 is the same as for claim 1.
Claim 5:
As to claim 5, it merely it merely limits the interpretation of the means plus function limitations to the hardware implementations discussed in the Claim Interpretation section of this Office action. Since both the hardware and software implementations of the means plus function limitations were discussed in the 101 analysis for claim 1, the rationale for claim 5 is readily apparent from the explanation given above.
Claim 6:
As to claims 6, it introduces the limitation that the sorting is performed at line rate with no dead cycles. The Specification does not explain what this limitation means and merely repeats the words. The limitation however appears to address the speed at which the sorting occurs (line rate) and the computational efficiency of the sorting (no dead cycles). The claim itself does not recite a line. Relating the claimed sorting to some unclaimed structure does not amount to adding an additional element to the claim. Accordingly, this limitation can be construed as additional characteristics of the abstract idea, and the analysis for claim 1 applies equally to claim 6. Alternatively, if claim 6 is considered to introduce an additional element, it is noted that the potential additional element is recited at a high level of generality. The claim is not limited to a high line rate. In addition, the claim states an efficiency goal of the sorting algorithms (i.e., no dead cycles). The claim therefore includes within its scope a slow line rate and sorting system whose processing speed is appropriately matched to the line rate. This limitation therefore amounts to nothing more than generally linking the abstract idea to a field of use. At step 2A prong 2, the additional element does not, either alone or in combination with the additional elements of the parent claim, integrate the abstract idea into a practical application. At step 2B, the claim does not, alone or in combination with the additional elements of the parent claim, include additional elements that are sufficient to amount to significantly more than the judicial exception. The analysis at step 2B is essentially the same as the analysis at step 2A prong 2.
.
Claim 7:
As to claim 7, it includes the additional elements. The claim requires that the numbers being sorted are “histograms of data bytes” and that an intended use of the sorting is for encoding in data compression. These additional elements merely generally link the use of the judicial exception to a particular technological environment or field of use. At step 2A prong 2, the additional elements do not, either alone or in combination with the additional elements of the parent claim, integrate the abstract idea into a practical application. At step 2B, the claim does not, alone or in combination with the additional elements of the parent claim, include additional elements that are sufficient to amount to significantly more than the judicial exception. The analysis at step 2B is essentially the same as the analysis at step 2A prong 2.
Claims 8-10 and 12-14:
Regarding claims 8-10 and 12-14, they are media claims corresponding to method claims 1-3 and 5-7, respectively. The analysis for the method claims applies equally to the media claims.
Claim 15
Regarding claim 15 it is directed to an apparatus for practicing the method of claim 1 with the additional limitation of a solid-state storage memory being operatively coupled to the processing device that practices the method of claim 1. Claim 15 does not include any language linking the storage device to the sorting performed by the processing device. Specifically, the claim does not require the unsorted numbers to come from the storage device or for the sorted numbers to be written to the storage device. Absent language linking the additional element to the claimed functionality performed by the processing device, this additional element is superfluous and merely generally links the abstract idea to a particular technological environment or field of use. Claim 15 also removes the limitation of a second unit performing the FIFO merge sort. Accordingly, the merging and sorting function starting at claim 15 line 9 now recites only abstract idea and recites no additional elements. The analysis for claim 15 is essentially the same as for claim 1 except for analysis of the additional element of the solid-state storage memory. At step 2A prong 2, this additional element does not, either alone or in combination with the additional elements identified in the discussion of the method claim, integrate the abstract idea into a practical application. At step 2B, the claim does not, either alone or in combination with the additional elements identified in the discussion of the method claim, include additional elements that are sufficient to amount to significantly more than the judicial exception. The analysis at step 2B is essentially the same as the analysis at step 2A prong 2.
Claims 16-17 and 19-20:
Regarding claims 16-17 and 19-20, they are apparatus claims corresponding to method claims 2-3 and 5-6, respectively. The analysis for the method claims applies equally to the apparatus claims.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1-3, 5-6, 8-10, 12-13, and 15-20 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Fang et al., In-memory database acceleration on FPGAs: a survey, VLDB Journal, doi.org/10.1007/s00778-019-00581-w, pp. 1-27, 2019.
Regarding claim 1, Fang teaches a processing device (Fig. 5) used to accelerate database operations such as sorting. Fang teaches the use of FPGAs (Fig. 5 VU37P FPGAs) to accelerate database functions (p. 9 § 5.4 describing FPGAs and § 5.3 explaining that FPGAs are used to accelerate the sorting described in p. 16 § 6.3). Fang explains that a sorting network (either the bubble sort or the insertion sort identified earlier in 6.3,1) is generally used for the early stages of a larger sort to generate small sorted streams that can be used as input for the FIFO merge sort or merge tree in later states (Fang. p. 16 § 6.3.1). Fang teaches that both the insertion sorting and FIFO merge sorting are implemented in an FPGA. Fang therefore teaches receiving by the overall system in Figure 5 an unsorted set of numbers. Fang also teaches sorting by a first unit as claimed followed by merging and sorting by a second unit as claimed.
Regarding claim 2, Fang teaches a method further comprising merging and sorting the first sorted set of numbers and a second sorted set of numbers, wherein the second sorted set of numbers comprises a third subset and a fourth subset of numbers of the unsorted set of numbers that have been sorted by the insertion sort and merged and sorted by the FIFO merge sort (Fang. p. 16 § 6.3.1).
Regarding claim 3, Fang teaches a method wherein the insertion sort comprises a pipeline insertion sort (Fang. p. 16 § 6.3.1).
Regarding claim 5, Fang teaches a method wherein the insertion sort and the FIFO merge sort are implemented in hardware comprising logic circuitry (Fang. p. 16 § 6.3.1 sorting implemented in FPGA).
Regarding claim 6, Fang teaches a method wherein the sorting is performed at line rate with no dead cycles (Fang. p. 16 § 6.3.1 describing a 64-input sorting network).
Regarding claims 8-10 and 12-13, they are media claims corresponding to method claims 1-3 and 5-6, respectively. They are rejected for the same reasons.
Regarding claim 15, it is directed to an apparatus that practices the method of claim 1. It includes the additional limitation that the system comprising a solid state storage memory that is operatively coupled to the processing device. Fang teaches that each FPGA in Figure 5 is attached to an NVMe device via the OpenCAPI protocol (Fig. 5 green interface to FPGA HBM; p. 16 § 6.3 storage is replaced with NVMe devices, which are solid state storage memory devices). Fang therefore teaches a an apparatus practicing the sorting method of claim 1 wherein a solid state storage memory is operatively coupled to the processing device. As to any claim limitation not explicitly discussed, the reasons for rejection should be readily apparent from the explanation given for claim 1.
Regarding claims 16-17 and 19-20, they are apparatus claims corresponding to method claims 2-3 and 5-6, respectively. The analysis for the method claims applies equally to the apparatus claims.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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 7 and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Fang in view of Mao.
Regarding claim 7, Fang teaches the invention substantially as claimed. See the rejection of claim 1 above. Fang does not explicitly teach the additional limitation of claim 7. However, Fang does teach that dictionary-based compression algorithms are a common type of database operation that could be accelerated using FPGAs. Fang therefore teaches the genus of dictionary-based compression algorithms and the species of LZ78 and LZW compression but does not teach the particular species of Huffman coding. Mao, in a similar field of endeavor, teaches a method wherein an unsorted set of numbers comprises histograms of data bytes for encoding in a data compression algorithm (Mao slide 16 – histograms for Huffman encoding as histograms of data bytes for encoding in a data compression algorithm). It would have been obvious to one of ordinary skill in the art before the effective filing date to modify the system of Fang to perform the histogram sorting for Huffman encoding as taught by Mao. This modification would have been obvious because it is the simple substitution of one known element (Huffman encoding) for another (LZW compression) to obtain predictable results. Having made this substitution, it would have been obvious to one of ordinary skill in the art to apply Fang’s improved sorting technique to the histogram sorting necessary to implement the Huffman encoding of the combination of Fang in view of Mao in order to function of Mao because of Fang’s teaching that the combined insertion/merge sort reduces the required reconfigurable resources (Fang. p. 16 § 6.3.1 col. 2 first complete paragraph).
Regarding claim 14, it is a media claim corresponding to method claim 7. It is rejected for the same reasons.
Response to Arguments
Regarding the rejection of claims under 35 U.S.C. 102(a)(1) in the prior Office action, Applicant’s arguments have been fully considered and are persuasive. Therefore, the rejection has been withdrawn. However, upon further consideration, a new ground(s) of rejection is made as explained above.
Regarding the rejection of claims under 35 U.S.C. 103 in the prior Office action, Applicant’s arguments have been fully considered and are persuasive. Therefore, the rejection has been withdrawn. However, upon further consideration, a new ground(s) of rejection is made as explained above.
Regarding the rejection under 35 U.S.C. 101, Applicant's arguments have been fully considered but they are not persuasive. Applicant argues in substance that sorting operations of a computer are improved by having the first unit perform an insertion sort and then having the second unit perform merging and sorting using a FIFO merge sort. In essence, Applicant is explaining that the improvement in the operation of the computer is the result of a combination of abstract ideas – the insertion sort followed by the merge sort. An inventive concept "cannot be furnished by the unpatentable law of nature (or natural phenomenon or abstract idea) itself." MPEP 2106.05 I citing Genetic Techs. Ltd. v. Merial LLC, 818 F.3d 1369, 1376, 118 USPQ2d 1541, 1546 (Fed. Cir. 2016). A combination of abstract ideas is still an abstract idea and therefore cannot provide the necessary improvement. Applicant should consider claim amendments that include meaningful features of a storage system using the alleged improvement.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Andrew Caldwell whose telephone number is (571) 272-3702. The examiner can normally be reached M-F 9:00-17:30. 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, TC Director John Cottingham can be reached at (571) 272-1400. 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.
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182
1 In the Response filed November 17, 2025, Applicant did not amend claim 15 to refer to a second unit as Applicant did in the other independent claims. Applicant should consider amending claim 15 to make it consistent with the other independent claims.
2 In the interest of brevity, the step 1 analysis has been omitted from the discussion of the remaining pending claims. However, all pending claims fall within one of the four statutory categories.