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-9, 11-21, and 23 rejected under 35 U.S.C. 101 because they are directed to an abstract idea without significantly more.
Regarding claims 1-9, 11-21, and 23,
Step 1: The preamble of claims 1-9 recites a method, which falls within the statutory category of a process. The preamble of claims 11-20 recites a system, which falls within the statutory category of an apparatus. The preamble of claim 21 recites a circuit, which falls within the statutory category of a manufacture. The preamble of claim 23 recites a non-transitory computer readable storage medium, which falls within the statutory category of a manufacture.
Regarding claim 1,
Step 2A – Prong One: Claim 1 recites:
A method of operating a data processing system, the data processing system comprising a processor operable to execute neural network processing, the method comprising:
receiving for a set of data points, each data point corresponding to a position in space, data point information indicative of one or more properties of the data points, and connectivity information indicative of connections between data points of the set of data points;
determining an order for the data points of the set of data points, based on the positions in space of the data points;
generating updated connectivity information for the set of data points based on the received connectivity information and on the determined order for the data points; and
the processor performing neural network processing using the updated connectivity information for the set of data points.
The broadest reasonable interpretation, in light of the Specification, of the bolded limitations above are directed to mental processes able to be performed in the human mind with or without the physicals aids of a pen and/or paper. A human could use observation, evaluation, and judgement to determine an order for data points based on the positions in space of the data points and generate updated connectivity information for the data points based on received connectivity information and the determined order. Step 2A – Prong One (Yes).
Step 2A – Prong Two: The additional elements of the claim regarding “the data processing system comprising a processor operable to execute neural network processing,” and “the processor performing neural network processing using the updated connectivity information for the set of data points” are mere instructions to apply the judicial exception on a generic computer (See MPEP 2106.05(f)). The additional element of the claim regarding “receiving for a set of data points, each data point corresponding to a position in space, data point information indicative of one or more properties of the data points, and connectivity information indicative of connections between data points of the set of data points;” is insignificant extra-solution activity that amounts to mere data gathering (See MPEP 2106.05(g)).
Even when viewed in combination, the additional elements of the claim fail to integrate the judicial exception into a practical application. Step 2A – Prong Two (No).
Step 2B: The additional elements of the claim regarding “the data processing system comprising a processor operable to execute neural network processing,” and “the processor performing neural network processing using the updated connectivity information for the set of data points” are mere instructions to apply the judicial exception on a generic computer (See MPEP 2106.05(f)). The computer is recited at a high level of generality and imposes no meaningful limitations on the claim. The additional element of the claim regarding “receiving for a set of data points, each data point corresponding to a position in space, data point information indicative of one or more properties of the data points, and connectivity information indicative of connections between data points of the set of data points;” is insignificant extra-solution activity that amounts to mere data gathering (See MPEP 2106.05(g)). Data gathering is a well-understood routine, conventional activity as recognized by the courts (See MPEP 2106.05(d)(II)).
Even when viewed in combination, the additional elements of the claim fail to amount to significantly more than the judicial exception. Step 2B (No).
Claim 1 is ineligible.
Regarding claims 11, 21, and 23,
These claims are similar in scope to claim 1 and are rejected under a similar rationale. The processors, storage medium, and circuits recited in these claims are also generic computing components. Thus, claims 11, 21, and 23 are ineligible.
Dependent claims:
Claims 2-3, 6-7, 12-13, and 16-17: These claims recite further abstract ideas (mental processes). Claims 6 and 16 recite an additional element regarding “wherein the processor uses the updated data point information for performing the neural network processing” which are instructions to apply the judicial exception on a generic computer (See MPEP 2106.05(f)). The computer is recited at a high level of generality and imposes no meaningful limitations on the claim. Even when viewed in combination, the additional element fails to integrate the judicial exception into a practical application and fails to amount to significantly more than the judicial exception. Thus, these claims are ineligible.
Claims 4 and 14: These claims recite further additional elements that are insignificant extra-solution activities that amount to mere data gathering (See MPEP 2106.05(g)). Data gathering is a well-understood, routine conventional activity as recognized by the courts (See MPEP 2106.05(d)(II)). Even when viewed in combination, the additional elements fail to integrate the judicial exception into a practical application and fails to amount to significantly more than the judicial exception. Thus, these claims are ineligible.
Claims 5 and 15: These claims recite further abstract ideas (mathematical concepts). Using a space filling curve to determine an order for data points is a mathematical relationship and thus falls within the mathematical concepts grouping of abstract ideas (See MPEP 2106.04(a)(2)(I)(A)). There are no additional elements recited that would integrate the judicial exception into a practical application and there are no additional elements recited that would amount to significantly more than the judicial exception. Thus, these claims are ineligible.
Claims 8-9 and 18-20: These claims recite further instructions to apply the judicial exception on a generic computer. The computer is recited at a high level of generality and imposes no meaningful limitations on the claim. Additionally, claims 9 and 19 recite an additional element regarding “wherein the connectivity information forms a data structure… wherein the updated connectivity information forms a data structure…” which are insignificant extra-solution activities that amount to mere data gathering (See MPEP 2106.05(g)). Data gathering is a well-understood, routine conventional activity as recognized by the courts (See MPEP 2106.05(d)(II)). Even when viewed in combination, the additional elements fail to integrate the recited judicial exception into a practical application and the additional elements fail to amount to significantly more than the recited judicial exception. Thus, these claims are ineligible.
Claim Rejections - 35 USC § 102
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.
Claim(s) 1-4, 6-7, 9, 11-14, 16-17, 19-21, and 23 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Zhang et al. (NPL from IDS: Point-X: A Spatial-Locality-Aware Architecture for Energy-Efficient Graph-Based Point-Cloud Deep Learning, published Oct. 2021, hereinafter “Zhang”).
Regarding claim 1, Zhang teaches a method of operating a data processing system, the data processing system comprising a processor operable to execute neural network processing (Zhang, Section 7.1 Paragraphs 3-4), the method comprising:
receiving for a set of data points (Zhang, Fig. 1 – shows receiving raw point cloud, thus receiving for a set of data points), each data point corresponding to a position in space, data point information indicative of one or more properties of the data points (Zhang, Fig. 1(a) – shows each data point corresponding to a position in space and data point information indicative of one or more properties of the data points, consistent with the Specification at Pg. 7 Lines 19-23 wherein data point information comprises position information), and connectivity information indicative of connections between data points of the set of data points (Zhang, Fig. 3 and Section 3.1 Paragraph 1 – “An example of a point cloud’s KNN graph is shown in Figure 3(a). The nodes are numbered during point cloud acquisition and preprocessing, and the graph is represented by an adjacency matrix.” – teaches connectivity information indicative of connections between data points of the set of data points (point cloud’s KNN graph represented by adjacency matrix which provides connectivity information indicative of connections between data points));
determining an order for the data points of the set of data points, based on the positions in space of the data points (Zhang, Fig. 3 and in Section 3.1 Paragraph 2 – “Our SLA clustering aims to maximize both fine-grained and coarse-grained spatial locality by taking advantage of the spatial relationship of points using graph traversals. The steps and result of SLA clustering are presented in Figure 3(b). Following the graph traversal order, the SLA clustering assigns every point into a cluster by mapping its point index to a pair of {cluster index, local point index}.” – teaches determining an order for the data points of the set of data points based on the positions in space of the data points (SLA clustering takes advantage of spatial relationship of points using graph traversals and follows graph traversal order, and Fig. 3(b) shows determining an order for the data points based on the positions in space of the data points));
generating updated connectivity information for the set of data points based on the received connectivity information and on the determined order for the data points (Zhang, Fig. 3 – teaches generating updated connectivity information for the set of data points (Fig. 3(b) shows the updated adjacency matrix, thus teaching generating updated connectivity information for the set of data points) based on the received connectivity information (Fig. 3(a) shows the initial adjacency matrix, thus the updated adjacency matrix of Fig. 3(b) is based on the initial adjacency matrix of Fig. 3(a)) and the on the determined order for the data points (as in Fig. 3(b), the updated adjacency matrix is based on the determined order for the data points as shown in Fig. 3(b)(left))); and
the processor performing neural network processing using the updated connectivity information for the set of data points (Zhang, Fig. 1, Fig. 11, and in Section 6 Paragraph 1 – “The Point-X system architecture is outlined in Figure 11. Point-X consists of a clustering module, a CTile array (CTA) module, data buffers, and controllers for system configuration, dataflow, and external communication. The system controller receives the compiled instructions from the host processor, and configures the other mod ules according to the dataflow mode.” – teaches the processor (host processor of Point-X as in Fig. 11) performing neural network processing using the updated connectivity information for the set of data points (Fig. 1(c) shows performing neural network processing using the updated adjacency matrix resulting from Fig. 1(a) and Fig. 1(b) for the raw point cloud, thus performing neural network processing using the updated connectivity information for the set of data points)).
Claims 11, 21, and 23 incorporate substantively all the limitations of claim 1 in a system, circuit, and non-transitory computer readable medium and are rejected on similar grounds as above. Zhang teaches the processors, processing circuits, and mediums of these claims at Fig. 11 and Section 6 Paragraphs 1-2.
Regarding claim 2, Zhang teaches the method of claim 1, comprising
first generating the connectivity information from which updated connectivity information is generated, by determining one or more connections between data points (Zhang, Fig. 3 and Fig. 3 description – “(a) KNN graph of input point cloud and its adjacency matrix representation;” – teaches first generating the connectivity information from which updated connectivity information is generated, by determining one or more connections between data points (Fig. 3(a) shows first generating connectivity information by determining one or more connections between data points, Fig. 3(b) shows the updated connectivity information generated from the first generated connectivity information)).
Claim 12 is similar to claim 2, hence similarly rejected.
Regarding claim 3, Zhang teaches the method of claim 1, wherein
generating the updated connectivity information comprises reordering the connectivity information according to the determined order for the data points (Zhang, Fig. 3(b), Fig. 13 and in Section 6.2 Paragraph 3 – “In Point-X, we adopt a diagonal partition by exploiting the SLA clustering as illustrated in Figure 13(b). The SLA clustering is applied to the entire input point cloud. Only the diagonal blocks in the adjacency matrix are sent to Point-X for processing. As discussed in Section 3, the SLA clustering increases the spatial locality and computation efficiency by increasing the number of local edges and bringing the foreign edges closer to the matrix diagonal” – teaches wherein generating the updated connectivity information comprises reordering the connectivity information according to the determined order for the data points (adopts diagonal partition by exploiting SLA clustering, SLA clustering increases number of local edges and brings foreign edges closer to adjacency matrix diagonal, Fig. 3(b) shows updated connectivity information by reordering the connectivity information according to the determined order, Fig. 13 also shows updated connectivity information by reordering connectivity information according to the determined order)).
Claim 13 is similar to claim 3, hence similarly rejected.
Regarding claim 4, Zhang teaches the method of claim 1, wherein
the connectivity information is in the form of an adjacency matrix, having rows and columns each corresponding to a respective data point in the order of the received set of data points, with non-zero matrix entries representing connections between data points, and zero matrix entries indicating that no connection between data points is present (Zhang, Fig. 3 – teaches wherein the connectivity information is in the form of an adjacency matrix (Fig. 3(a) and (b) both show the connectivity information in the form of an adjacency matrix), having rows and columns each corresponding to a respective data point in the order of the received set of data points (Fig. 3(a) shows the adjacency matrix having rows and columns corresponding to respective data points in the order that the input point cloud is received), with non-zero matrix entries representing connections between data points and zero matrix entries indicating that no connection between data points is present (in Fig. 3, colored matrix entries indicate the entry is non-zero and thus represents a connection between data points and non-colored matrix entries indicate the entry is zero and thus indicates that no connection between points is present)); and
wherein generating updated connectivity information comprises re-ordering the rows and columns of the adjacency matrix to correspond to the determined order for the data points in the set of data points (Zhang, Fig. 3(b) and Fig. 3 description – “(b) the KNN graph is traversed and the points clustered following traversal order; the clustered KNN graph and its adjacency matrix are shown.” – teaches wherein generating updated connectivity information comprises re-ordering the rows and columns of the adjacency matrix to correspond to the determined order for the data points in the set of data points (Fig. 3(b) shows the adjacency matrix with re-ordered rows and columns corresponding to the determined order for the data points, and thus generates updated connectivity information)).
Claim 14 is similar to claim 4, hence similarly rejected.
Regarding claim 6, Zhang teaches the method of claim 1, further comprising
generating updated data point information, based on the received data point information and on the determined order for the data points (Zhang, Fig. 3 and Fig. 3 description – teaches generating updated data point information (KNN graph and adjacency matrix of Fig. 3(b)), based on the received data point information (input point cloud, KNN graph of input point cloud) and on the determined order for the data points (KNN graph traversed and points clustered following traversal order)); and
wherein the processor uses the updated data point information for performing the neural network processing (Zhang, Fig. 1 and Fig. 1 description – teaches wherein the processor uses the updated data point information for performing the neural network processing (Fig. 1(a) shows a raw point cloud being preprocessed through a point cloud recognition pipeline for performing neural network processing as in Fig. 1(c), thus the processor uses updated data point information for preforming the neural network processing)).
Claim 16 is similar to claim 6, hence similarly rejected.
Regarding claim 7, Zhang teaches the method of claim 6, wherein
generating the updated data point information comprises re-ordering the received data point information according to the determined order for the data points (Zhang, Fig. 3 and Fig. 3 description – teaches wherein generating the updated data point information comprises re-ordering the received data point information according to the determined order for the data points (Fig. 3 shows the KNN graph is traversed and the points clustered following traversal order, thus teaching wherein generating the updated data point information comprises re-ordering the received data point information according to the determined order)).
Claim 17 is similar to claim 7, hence similarly rejected.
Regarding claim 9, Zhang teaches the method of claim 1, wherein
the connectivity information forms a data structure indicating connections between data points of the set of data points (Zhang, Fig. 3 – teaches wherein the connectivity information forms a data structure indicating connections between data points of the set of data points (Fig. 3 shows an adjacency matrix, which is a data structure, that indicates connections between data points of the set of data points));
wherein the updated connectivity information forms a data structure with one or more regions having a greater density of indicated connections (Zhang, Fig. 13 – teaches wherein the updated connectivity information forms a data structure with one or more regions having a greater density of indicated connections (Fig. 13(b) shows wherein the updated adjacency matrix has one or more regions, along the diagonal, having a greater density of indicated connections)); and
comprising, when performing neural network processing using the updated connectivity information, only using said one or more regions having a greater density of indicated connections for the neural network processing (Zhang, Fig. 1, Fig. 13, and in Section 6.2 Paragraph 3 – “In Point-X, we adopt a diagonal partition by exploiting the SLA clustering as illustrated in Figure 13(b). The SLA clustering is applied to the entire input point cloud. Only the diagonal blocks in the adjacency matrix are sent to Point-X for processing.” – teaches comprising, when performing neural network processing using the updated connectivity information (as in Fig. 1), only using said one or more regions having a greater density of indicated connections for the neural network processing (only the diagonal blocks in the adjacency matrix, which as seen in Fig. 13(b) where the diagonal has a greater density of connections, are sent to Point-X for processing)).
Claim 19 is similar to claim 9, hence similarly rejected.
Regarding claim 20, Zhang teaches the data processing system of claim 11, wherein
the processing circuit is incorporated within the processor operable to execute neural network processing (Zhang, Fig. 11, Fig. 12, and in Section 6 Paragraphs 1-2 – teaches wherein the processing circuit is incorporated within the processor operable to execute neural network processing (Fig. 11 shows the architecture in which the SLA Clustering Module, or processing circuit, is incorporated within the processor operable to execute the neural network processing)).
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.
Claim(s) 5, 8, 15, and 18 is/are rejected under 35 U.S.C. 103 as being unpatentable over Zhang in view of Calmon et al. (US Patent No. 10,853,720, published Dec. 2020, hereinafter “Calmon”).
Regarding claim 5, Zhang teaches the method of claim 1.
Zhang fails to explicitly teach using a space filling curve to determine the order for the data points of the set of data points based on the positions in space of the data points.
However, analogous to the field of the claimed invention, Calmon teaches: comprising
using a space filling curve to determine the order for the data points of the set of data points based on the positions in space of the data points (Calmon, Fig. 3, Pg. 14 Col. 6 Lines 28-35 – “Generally, space-filling curves 325 leverage the creation of matrices given some vectors as input. Space-filling curves 325 preserve the input proximity on the vector dimensions. With the space-filling curves 325 at hand, the final goal becomes, then, to create vectors that translate closeness within its axis. A unidimensional vector, for example, represents in sequential positions items that are sequentially close on the real world.”, and in Pg. 14 Col. 6 Lines 36-42 – “In the embodiment of FIG. 3, the locality-aware compression starts by filling the space-filling curve 325 from a point of interest, such as point 315, and then calculating the distance from all other non-empty points to the origin and return those with the smallest distances. Applying this procedure repeatedly generates a so called space-filling curve vector.” – teaches using a space filling curve to determine the order for the data points of the set data points based on the positions in space of the data points (fills space-filling curve from a point of interest and then calculating the distance from all other non-empty points to the origin and return those with smallest distances in a space-filling curve vector, thus uses a space filling curve to determine the order for the data points based on the positions in space of the data points)).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, to incorporate the space filling curves of Calmon to the data points, adjacency matrices, and methods of Zhang. Doing so would provide a more compact way to represent information in adjacency matrices without losing information and preserving locality of data relative to position (Calmon, Pg. 14 Col. 5).
Claim 15 is similar to claim 5, hence similarly rejected.
Regarding claim 8, Zhang teaches the method of claim 1.
Zhang fails to explicitly teach wherein providing the updated connectivity information for the set of data points for further processing by the processor comprises compressing the updated connectivity information and storing the compressed connectivity information in a storage of the data processing system.
However, analogous to the field of the claimed invention, Calmon teaches: wherein
providing the updated connectivity information for the set of data points for further processing by the processor comprises compressing the updated connectivity information (Calmon, Pg. 13, Col. 4, Line 62 – Pg. 14, Col. 5, Line 3 – “In one or more embodiments, the OD-Matrices 250 can be compressed to represent only the non-empty edges in it. The compressed OD-Matrices, if converted to an image, will result in a much smaller representation when compared to the original OD-Matrix 250. One or more aspects of the disclosure recognize that Deep Neural Networks will benefit from this compressed approach for image processing, since the computing effort of a Deep Neural Network is directly related to the size of the images under study.” – teaches compressing the updated connectivity information (OD Matrices are adjacency matrices as stated by Calmon at Pg. 13, Col. 4, Lines 21-22, OD-Matrices can be compressed to represent only non-empty edges)) and storing the compressed connectivity information in a storage of the data processing system (Calmon, Fig. 5 – shows a DNN being trained using stored compressed OD-Matrix and past compressed OD-Matrices, and in Pg. 12 Col. 2 Lines 31-50 – teaches wherein the information processing system includes storage devices, thus teaching storing the compressed connectivity information in a storage of the data processing system).
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filing date of the claimed invention, to incorporate the compression techniques and storage of Calmon to the connectivity updates, data, and methods of Zhang. Doing so would benefit neural networks by reducing the size of the adjacency matrices and thus reducing the computing effort of the neural networks (Calmon, Pg. 13 Col 4 – Pg. 14 Col. 5).
Claim 18 is similar to claim 8, hence similarly rejected. Claim 18 recites a further limitation: wherein the processor operable to perform neural network processing is operable to retrieve stored updated connectivity information for performing neural network processing (Calmon, Fig. 5, Fig. 11, and in Pg. 18, Col. 13, Lines 45-50 – “Also, numerous other arrangements of computers, servers, storage devices or other components are possible in the information processing system. Such components can communicate with other elements of the information processing system over any type of network or other communication media.” – teaches wherein the processor (such as processor of Fig. 11) operable to perform neural network processing (such as DNN processing of Fig. 5) is operable to retrieve stored updated connectivity information for performing neural network processing (components of system can communicate with other elements of information processing system, and as in Fig. 5, shows retrieval of compressed updated connectivity information for performing neural network processing)).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Zhang M. et al. (NPL: Weisfeiler-Lehman Neural Machine for Link Prediction, published Aug. 2017) teaches learning topological features in the form of graph patterns for link prediction using neural networks. Teaches encoding subgraphs as adjacency matrices. Teaches reordering vertices of graphs according to labels and data information. Teaches wherein the updated adjacency matrix and/or updated graph is used in a neural network for link prediction.
Kernert et al. (US Pub. No. 2015/0379054, published Dec. 2015) teaches storing ordered sparse matrices in an in-memory column-oriented system. Teaches compression of matrices and storage of matrices. Teaches ordering of points within matrices based on query statistics. Teaches space filling curves for determining order of points.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to LOUIS C NYE whose telephone number is 571-272-0636. The examiner can normally be reached Monday - Friday 9:00AM - 5:00PM.
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, MATT ELL can be reached at 571-270-3264. 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.
/LOUIS CHRISTOPHER NYE/Examiner, Art Unit 2141
/MATTHEW ELL/Supervisory Patent Examiner, Art Unit 2141
Prosecution Insights