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 § 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-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
For the Alice analysis:
Regarding step 1, claims 1-20 all fall withing a statutory category. Claims 1-10 are directed to a machine, and claims 11-20 are directed to a process.
Regarding claim 1, for Step 2A, Prong One, the claim recites “iteratively, until values of a frontier vector indicate all nodes of a graph have been discovered: a set of rows from a matrix representation of the graph based on the values of the frontier vector, the set of rows including fewer rows than the matrix representation”, which is the mathematical concept of masking; and “calculate an output vector for a current iteration as a dot product between each of the selected set of rows in the matrix representation and the frontier vector”, which is a mathematical calculation.
For Step 2A, Prong Two, the claim recites the additional elements of “a processor” and “memory coupled to the processor, the memory storing computer program instructions executed by the processor”. Regarding the processor and memory, it is recited at such a high level of generality it represents no more than mere instructions to apply the mathematical concepts on a generic computer. Regarding the storing of computer program instructions, it is claimed at a very high level of generality that represents no more than a means of mere data gathering per MPEP § 2106.05(g), and is therefore insignificant extra-solution activity. Even when viewed in combination, these additional elements do not integrate the recited judicial exception into a practical application and the claim is directed to the judicial exception.
For Step 2B, the claim does not include additional elements that are sufficient to amount
to significantly more than the judicial exception. Regarding the processor and memory, it is at best the equivalent of merely adding “apply it” to the judicial exception. See MPEP § 2106.05(f). Mere instructions to apply an exception cannot provide an inventive concept. Regarding the storing of computer program instructions, previously explained as insignificant extra-solution activity, the use of it for storing and retrieving information has been recognized by the courts as well-understood, routine and conventional per MPEP § 2106.06(d)(II)(iv).
Even when considered in combination, these additional elements represent mere instructions to apply an exception and insignificant extra-solution activity that is well-understood, routine and conventional, respectively, which do not provide an inventive concept. The claim is not eligible.
Regarding claims 4-6 and 9-10, for Step 2A, Prong One, they merely further limit the mathematical concepts in claim 1, and recite no other additional elements. Even when viewed in combination, none of the limitations integrate the recited judicial exception into a practical application and the claims are directed to the judicial exception. The claims are not eligible.
Regarding claim 7, for Step 2A, Prong Two, the claim recites an additional element of “a parallel accelerated processor including a plurality of compute units”. Merely running the processes in parallel is insignificant extra-solution material, as it is an insignificant computer implementation. See MPEP § 2106.06(g).
For Step 2B, the additional element, even when considered in combination, does not integrate the judicial exception into a practical application. Furthermore, a parallel processor is well-understood, routing and conventional. See Hennessy et al., Computer Architecture: A Quantitative Approach, Fifth Edition, hereinafter Hennessy, Chapter 5.1, “Thread-Level Parallelism, Introduction”: “Nonetheless, the importance of multiprocessors was growing throughout the 1990s as designers sought a way to build servers and supercomputers that achieved higher performance than a single microprocessor, while exploiting the tremendous cost-performance advantages of commodity microprocessors” (p. 344, ¶ 2).
Even when viewed in combination, none of the limitations integrate the recited judicial exception into a practical application and the claim is directed to the judicial exception. The claim is not eligible.
Regarding claim 8, for Step 2A, Prong One, the claim recites an additional element of “dispatching tasks to one or more compute units of the parallel accelerated processor”. Dispatching tasks to a processor is an insignificant computer implementation, and is therefore insignificant extra-solution activity.
For Step 2B, the additional element, even when considered in combination, does not integrate the judicial exception into a practical application. Dispatching tasks to compute units is well-understood, routine and conventional. See Hennessy, Chapter 4.4, “Data-Level Parallelism in Vector, SIMD, and GPU Architectures, Graphics Processing Units”, “The SIMD Thread Scheduler includes a scoreboard that lets it know which threads of SIMD instructions are ready to run, and then it sends them off to a dispatch unit to be run on the multithreaded SIMD Processor. It is identical to a hardware thread scheduler in a traditional multithreaded processor” (p. 296, ¶ 1), as well as Figure 4.20.
Even when viewed in combination, none of the limitations integrate the recited judicial exception into a practical application and the claim is directed to the judicial exception. The claim is not eligible.
Regarding claims 11-16 and 17-19, they are method claims that correspond to claims 1-6 and 8-19, respectively, and are not eligible for the same reasons.
Regarding claim 20, for Step 2A, Prong One, it merely further limits the mathematical concepts in claim 11, and recites no other additional elements. Even when viewed in combination, none of the limitations integrate the recited judicial exception into a practical application and the claim is directed to the judicial exception. The claim is not eligible.
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-20 are rejected under 35 U.S.C. 103 as being unpatentable over Burkhardt, "Optimal Algebraic Breadth-First Search for Sparse Graphs", in view of Hennessy.
Regarding claim 1, Burkhardt discloses iteratively, until values of a frontier vector indicate all nodes of a graph have been discovered (Algorithm 1): select a set of rows from a matrix representation of the graph based on the values of the frontier vector, the set of rows including fewer rows than the matrix representation (Algorithm 1, line 6); and calculate an output vector for a current iteration as a dot product between each of the selected set of rows in the matrix representation and the frontier vector, with the output vector for the current iteration acting as the frontier vector for a next iteration and the output vector for the next iteration initialized to the frontier vector for the current iteration (Algorithm 1, line 5). While Burkhardt discloses the system running on a processor and memory: “The experiments were run on a single workstation with 256 GB of RAM and 28 Intel Xeon E5-2680 cores” (Section 11, ¶ 4); Burkhardt does not explicitly state the memory storing the program instructions.
Hennessy discloses a processor (2.1, “Memory Hierarchy Design - Introduction”, Figure 2.1(b)); and memory (Figure 2.1(b), memory, L1 cache, L2 cache) coupled to the processor, the memory storing program instructions (p. 73, ¶ 2). It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to have used the architecture disclosed by Hennessy to execute the algorithm disclosed by Burkhardt because the hierarchy of a processor plus levels of cache and memory that store the instructions has been the standard since the first practical computer (p. 72, ¶ 1)
Regarding claim 2, Burkhardt discloses the system of claim 1, wherein the values of the frontier vector indicate all nodes of the graph have been discovered when each row of the frontier vector has had a value indicating a corresponding node of the graph has been discovered in at least one iteration (Algorithm 1, line 1).
Regarding claim 3, Burkhardt discloses the system of claim 1, wherein the frontier vector includes a plurality of rows, each row including a first value or a second value (Section 1, ¶ 1) and wherein selecting the set of rows from the matrix representation of the graph based on the values of the frontier vector comprises selecting rows of the matrix representation corresponding to rows of the current frontier matrix having the second value and not having had the first value in at least one iteration (Algorithm 1, line 6).
Regarding claim 4, Burkhardt discloses the system of claim 3, wherein the first value is a logical high value and the second value is a logical low value (Section 2, ¶ 1).
Regarding claim 5, Burkhardt discloses the system of claim 3, wherein the values of the frontier vector indicate all nodes of the graph have been discovered when each row of the frontier vector included the first value in at least one iteration (Figure 1).
Regarding claim 6, Burkhardt discloses the system of claim 1, wherein the memory further comprises computer program instructions executed by the processor to: initialize the frontier vector to an initial frontier vector having a first value in a row corresponding to a starting node in the graph and a second value for other rows before iterating (Algorithm 1, V2); calculate an initial output vector as a dot product between each row in the matrix representation of the graph and the initial frontier vector before iterating (Algorithm 1, line 5); and set the frontier vector to the initial output vector (Algorithm 1, line 5).
Regarding claim 7, Burkhardt discloses the system of claim 1, wherein the processor comprises a parallel accelerated processor including a plurality of compute units (Section 8, ¶ 4).
Regarding claim 8, Burkhardt discloses the system of claim 7, wherein calculating the output vector for the current iteration as the dot product between each of the selected set of rows in the matrix representation and the frontier vector comprises dispatching tasks to one or more compute units of the parallel accelerated processor, each task corresponding to a dot product between a row of the selected set of rows and the frontier vector (Section 8, Theorem 4, Proof).
Regarding claim 9, Burkhardt discloses the system of claim 1, wherein calculating the output vector for the current iteration as the dot product between each of the selected set of rows in the matrix representation and the frontier vector comprises: updating a value of a row in the output vector corresponding to a row in the selected set of rows to a dot product between the row in the selected set and the frontier vector (Figure 1); and maintaining values of rows in the output vector corresponding to a row that is not included in the selected set of rows (Figure 1).
Regarding claim 10, Burkhardt discloses the system of claim 1, wherein each element of the matrix representation of the graph corresponds to a pair of nodes in the graph and has a value indicating whether the pair of nodes is connected in the graph (Section 2, ¶ 1).
Regarding claims 11-16 and 17-19, they are method claims that correspond to claims 1-6 and 8-19, respectively, and are rejected for the same reasons.
Regarding claim 20, Burkhardt discloses the method of claim 11, wherein the matrix representation of the graph comprises a transpose of an adjacency matrix of the graph (Section 7, Observation 1, Proof, ¶ 3).
Discussion of Pertinent Art
Burkhardt ‘998 (US 10,191,998) discloses the same device as disclosed in Burkhardt. Buluç et al., “Distributed-Memory Breadth-First Search on Massive Graphs”, discloses performing graph traversal with matrix-vector multiplication where space is saved by storing the matrix in compressed state row (CSR) form. Yang et al., “Implementing Push-Pull Efficiently in GraphBLAS”, discloses graph traversal using matrix-vector multiplication where already visited nodes are masked via masking vector.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Matthew Strapp whose telephone number is (571)272-9343. The examiner can normally be reached Monday-Friday 8:00 AM-4:00 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, Andrew Caldwell can be reached at (571)272-3702. 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.
/M.S./
Matthew StrappExaminer, Art Unit 2182 (571)272-9343
/EMILY E LAROCQUE/Primary Examiner, Art Unit 2182
Prosecution Insights