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 .
Priority
Acknowledgment is made of applicant's claim for foreign priority under 35 U.S.C. 119 (a)-(d).
Claim Interpretation
In view of the Applicant’s recitation of a “load balancing algorithm”, it is the position of the Examiner that the claims are integrated into a practical application as the broadest reasonable interpretation of “graph nodes” are nodes in a graph database.
Continued Examination Under 37 CFR 1.114
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on June 23, 2026 has been entered. Accordingly, Claims 1-20 are pending in this application. Claim 3 has been cancelled. Claims 1, 2, 9, 10, 15, and 16 have been amended. Claims 1, 9, and 15 are independent claims.
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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1, 2, and 4-20 are rejected under 35 U.S.C. 103 as being unpatentable over Elyasi (PG Pub. No. 2020/0183604 A1) and further in view of Park (“Machine Learning-based Selection of Graph Partitioning Strategy Using the Characteristics of Graph Data and Algorithm (Regular Papers)”, September 9, 2022), Mell (”Linear Time Vertex Partitioning on Massive Graphs”, International Journal of Computer Science: Theory and Application, 2016) and Moiseev (WO2024237805A1).
Regarding Claim 1, Elyasi discloses a method for graph data partitioning, comprising:
for an associated edge of a primary graph node, constructing a replica of another graph node that corresponds to the primary graph node for the associated edge and storing the replica as a mirror graph node in a graph data partition corresponding to the primary graph node (see Elyasi, paragraph [0024], where source vertices (e.g., Vertex ‘A’, Vertex ‘B’, etc.) for each partition (e.g., Partition 0, Partition 1, etc.) may be divided into mirror vertices (e.g., 225) and master vertices (e.g., 230) [it is the position of the Examiner that ‘master’ vertices are not patentably distinguishable from primary graph nodes).
Elyasi does not disclose:
selecting an associated edge allocation strategy based on a graph data acquisition path direction of a downstream graph computing task;
allocating, in accordance with the associated edge allocation strategy, edge data of associated edges of the primary graph nodes to corresponding graph data partitions, wherein the associated edges comprise at least one of outgoing edges or incoming edges;
calculating a degree of each graph node in graph data based on a graph topology structure of the graph data;
allocating the graph nodes in the graph data to a plurality of graph data partitions based on the degrees of the graph nodes according to a computing load balancing algorithm, wherein a graph node with a higher calculated degree among unallocated graph nodes is allocated prior to a graph node with a lower calculated degree, such that the graph nodes are partitioned as primary graph nodes in the graph data partitions; and
storage of the replica as a mirror graph node in a graph data partition is for use in performing the downstream graph computing task.
Elyasi in view of Park discloses:
selecting an associated edge allocation strategy based on a graph data acquisition path direction of a downstream graph computing task (see Park, Abstract, where we propose a machine learning-based approach to select the most appropriate partitioning strategy for a given graph and processing algorithm; our approach enumerates viable partitioning strategies, predicts the execution time of the target algorithm for each, and selects the partitioning strategy with the fastest estimated execution time; see also 5.3.7, where random walk is a partitioning strategy that starts from a source vertex and selects a random vertex from neighbor vertices connected by out-edges); and
allocating, in accordance with the associated edge allocation strategy, edge data of associated edges of the primary graph nodes to corresponding graph data partitions (see Park, Abstract, where we propose a machine learning-based approach to select the most appropriate partitioning strategy for a given graph and processing algorithm; our approach enumerates viable partitioning strategies, predicts the execution time of the target algorithm for each, and selects the partitioning strategy with the fastest estimated execution time; see also 5.3.7, where random walk is a partitioning strategy that starts from a source vertex and selects a random vertex from neighbor vertices connected by out-edges), wherein the associated edges comprise at least one of outgoing edges or incoming edges (see Elyasi, Fig. 2, where edge data for partition 0 includes a plurality of out edges).
Both Elyasi and Park are directed to graph partitioning, therefore it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to combine Elyasi with Park as it amounts to combining prior art elements according to known methods to yield predictable results (see MPEP 2143(A)(I)).
Elyasi in view of Park does not disclose:
calculating a degree of each graph node in graph data based on a graph topology structure of the graph data;
allocating the graph nodes in the graph data to a plurality of graph data partitions based on the degrees of the graph nodes according to a computing load balancing algorithm, wherein a graph node with a higher calculated degree among unallocated graph nodes is allocated prior to a graph node with a lower calculated degree, such that the graph nodes are partitioned as primary graph nodes in the graph data partitions; and
storage of the replica as a mirror graph node in a graph data partition is for use in performing the downstream graph computing task.
Mell discloses:
calculating a degree of each graph node in graph data based on a graph topology structure of the graph data (see Mell, Section 2 Methods and Materials, where the heuristic we are using to perform vertex partitioning is to iteratively extract a highest degree vertex from a graph, G; we denote G as having n vertices and m non-loop edges with the degree of each node being calculated ignoring any self-loops(since self-loops have no bearing on the connectivity of G); we iteratively remove nodes until some set number, k, of vertices are extracted with k ≤ m/2 (were m/2 highest degree nodes removed, all remaining nodes would have degree 0); after extracting a vertex, we recalculate any affected node degrees (decrementing each of them); the rationale behind the approach is that removal of a highest degree node will remove the most number of edges and thus intuitively will have a better chance of disconnecting a graph compared to removing a lower degree node with fewer edges);
allocating the graph nodes in the graph data to a plurality of graph data partitions based on the degrees of the graph nodes, wherein a graph node with a higher calculated degree among unallocated graph nodes is allocated prior to a graph node with a lower calculated degree, such that the graph nodes are partitioned as primary graph nodes in the graph data partitions (see Mell, Section 2 Methods and Materials, where the heuristic we are using to perform vertex partitioning is to iteratively extract a highest degree vertex from a graph, G; we denote G as having n vertices and m non-loop edges with the degree of each node being calculated ignoring any self-loops(since self-loops have no bearing on the connectivity of G); we iteratively remove nodes until some set number, k, of vertices are extracted with k ≤ m/2 (were m/2 highest degree nodes removed, all remaining nodes would have degree 0); after extracting a vertex, we recalculate any affected node degrees (decrementing each of them); the rationale behind the approach is that removal of a highest degree node will remove the most number of edges and thus intuitively will have a better chance of disconnecting a graph compared to removing a lower degree node with fewer edges).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to substitute the greedy node selection algorithm in Elyasi and the task-based node allocation strategy in Park with the high degree node first selection algorithm in Mell for the benefit of intuitively will have a better chance of disconnecting a graph (see Mell, Section 2, Methods and Materials).
Elyasi in view of Park and Mell does not disclose the partitioning is according to a computing load balancing allocation algorithm. Moiseev discloses the partitioning is according to a computing load balancing allocation algorithm (see Moiseev, paragraph [0026], where graph partitioning is an important step in distributed computations; this task is essential for the analysis of large graphs due to large runtime … the way the graph is partitioned influences critically on the load balance).
Elyasi, Park, Mell, and Moiseev are directed to graph partitioning, therefore it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to combine Elyasi, Park, and Mell with Moiseev as it amounts to combining prior art elements according to known methods to yield predictable results (see MPEP 2143(A)(I)).
Regarding Claim 2, Elyasi in view of Park, Mell and Moiseev discloses the method according to Claim 1, wherein selecting the associated edge allocation strategy comprises selecting the associated edge allocation strategy from an outgoing edge allocation strategy, an incoming edge allocation strategy (see Elyasi, paragraph [0027], where embodiments disclosed herein … (ii) store the ‘in edges’ of destination vertices associated with each partition separately along with their indexing information), or a combined outgoing edge and income edge allocation strategy.
Regarding Claim 4, Elyasi in view of Park, Mell and Moiseev discloses the method according to Claim 1, wherein the allocating the edge data of the associated edges of the primary graph nodes to the corresponding graph data partitions comprises:
obtaining edge data of the associated edges from an edge list of the graph data based on edge list offsets of the associated edges (see Elyasi, Fig. 2, where edge data for partition 0 includes out-edges and accompanying offsets); and
allocating the edge data of the associated edges to the corresponding graph data partitions (see Elyasi, Fig. 2, where edge data for partition 0 includes out-edges and accompanying offsets).
Regarding Claim 5, Elyasi in view of Park, Mell and Moiseev discloses the method according to Claim 4, wherein the edge data is stored in the edge list in an order of node numbers of corresponding graph nodes, and the edge list offsets of the associated edges are determined based on out-degrees of the graph nodes (see Elyasi, Fig. 2, where edge data for partition 0 includes out-edges and accompanying offsets).
Regarding Claim 6, Elyasi in view of Park, Mell and Moiseev discloses the method according to Claim 1, further comprising at least one of:
allocating local node identifiers and global node identifiers to the primary graph node in the graph data partition and the mirror graph node; or
establishing a node mapping relationship between the mirror graph node and a corresponding primary graph node in another graph data partition (see Elyasi, paragraph [0038], where when all partitions have been processed, the graph data coordinator logic section 405 may read destination vertex data for each partition and update the corresponding mirrors on other partitions).
Regarding Claim 7, Elyasi in view of Park, Mell and Moiseev discloses the method according to Claim 1, wherein an edge list of the edge data is in a format of a sparse adjacency list (see Elyasi, paragraph [0052], where partitioning pre-processing step may further include: for each edge “→” of an edge list in which vertex “u” is associated with vertex “v” in a “u→v” relationship [it is the position of the Examiner that a list of edges that only contains existing edges is not patentably distinguishable from a sparse adjacency list]).
Regarding Claim 8, Elyasi in view of Park, Mell and Moiseev discloses the method according to Claim 1, further comprising generating partition offset information for the graph data partition and storing the partition offset information in the graph data partition, wherein the partition offset information comprises a number of primary graph nodes in the graph data partition (see Elyasi, paragraph [0040], where metadata 505 is maintained for the destination vertex (e.g., Vertex ‘0’ of Fig. 5) includes partition IDs (e.g., 520) of mirrors 480 of each vertex, and the offset (e.g., Offset A, Offset N, etc. of Fig. 5) for each partition).
Regarding Claim 9, Elyasi discloses a computer-implemented device, comprising:
one or more processors (see Elyasi, paragraph [0062], where embodiments of the inventive concept may include a non-transitory machine-readable medium comprising instructions executable by one or more processors, the instructions comprising instructions to perform the elements of the inventive concepts as described herein); and
one or more computer memory devices interoperatively coupled with the one or more processors and having tangible, non-transitory, machine readable media storing one or more instructions (see Elyasi, paragraph [0062], where embodiments of the inventive concept may include a non-transitory machine-readable medium comprising instructions executable by one or more processors, the instructions comprising instructions to perform the elements of the inventive concepts as described herein) that, when executed by the one or more processors, perform one or more operations comprising:
for an associated edge of a primary graph node, constructing a replica of another graph node that corresponds to the primary graph node for the associated edge and storing the replica as a mirror graph node in a graph data partition corresponding to the primary graph node (see Elyasi, paragraph [0024], where source vertices (e.g., Vertex ‘A’, Vertex ‘B’, etc.) for each partition (e.g., Partition 0, Partition 1, etc.) may be divided into mirror vertices (e.g., 225) and master vertices (e.g., 230) [it is the position of the Examiner that ‘master’ vertices are not patentably distinguishable from primary graph nodes).
Elyasi does not disclose:
selecting an associated edge allocation strategy based on a graph data acquisition path direction of a downstream graph computing task;
allocating, in accordance with the associated edge allocation strategy, edge data of associated edges of the primary graph nodes to corresponding graph data partitions, wherein the associated edges comprise at least one of outgoing edges or incoming edges;
calculating a degree of each graph node in graph data based on a graph topology structure of the graph data;
allocating the graph nodes in the graph data to a plurality of graph data partitions based on the degrees of the graph nodes according to a computing load balancing algorithm, wherein a graph node with a higher calculated degree among unallocated graph nodes is allocated prior to a graph node with a lower calculated degree, such that the graph nodes are partitioned as primary graph nodes in the graph data partitions; and
storage of the replica as a mirror graph node in a graph data partition is for use in performing the downstream graph computing task.
Elyasi in view of Park discloses:
selecting an associated edge allocation strategy based on a graph data acquisition path direction of a downstream graph computing task (see Park, Abstract, where we propose a machine learning-based approach to select the most appropriate partitioning strategy for a given graph and processing algorithm; our approach enumerates viable partitioning strategies, predicts the execution time of the target algorithm for each, and selects the partitioning strategy with the fastest estimated execution time; see also 5.3.7, where random walk is a partitioning strategy that starts from a source vertex and selects a random vertex from neighbor vertices connected by out-edges); and
allocating, in accordance with the associated edge allocation strategy, edge data of associated edges of the primary graph nodes to corresponding graph data partitions (see Park, Abstract, where we propose a machine learning-based approach to select the most appropriate partitioning strategy for a given graph and processing algorithm; our approach enumerates viable partitioning strategies, predicts the execution time of the target algorithm for each, and selects the partitioning strategy with the fastest estimated execution time; see also 5.3.7, where random walk is a partitioning strategy that starts from a source vertex and selects a random vertex from neighbor vertices connected by out-edges), wherein the associated edges comprise at least one of outgoing edges or incoming edges (see Elyasi, Fig. 2, where edge data for partition 0 includes a plurality of out edges).
Both Elyasi and Park are directed to graph partitioning, therefore it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to combine Elyasi with Park as it amounts to combining prior art elements according to known methods to yield predictable results (see MPEP 2143(A)(I)).
Elyasi in view of Park does not disclose:
calculating a degree of each graph node in graph data based on a graph topology structure of the graph data;
allocating the graph nodes in the graph data to a plurality of graph data partitions based on the degrees of the graph nodes according to a computing load balancing algorithm, wherein a graph node with a higher calculated degree among unallocated graph nodes is allocated prior to a graph node with a lower calculated degree, such that the graph nodes are partitioned as primary graph nodes in the graph data partitions; and
storage of the replica as a mirror graph node in a graph data partition is for use in performing the downstream graph computing task.
Mell discloses:
calculating a degree of each graph node in graph data based on a graph topology structure of the graph data (see Mell, Section 2 Methods and Materials, where the heuristic we are using to perform vertex partitioning is to iteratively extract a highest degree vertex from a graph, G; we denote G as having n vertices and m non-loop edges with the degree of each node being calculated ignoring any self-loops(since self-loops have no bearing on the connectivity of G); we iteratively remove nodes until some set number, k, of vertices are extracted with k ≤ m/2 (were m/2 highest degree nodes removed, all remaining nodes would have degree 0); after extracting a vertex, we recalculate any affected node degrees (decrementing each of them); the rationale behind the approach is that removal of a highest degree node will remove the most number of edges and thus intuitively will have a better chance of disconnecting a graph compared to removing a lower degree node with fewer edges);
allocating the graph nodes in the graph data to a plurality of graph data partitions based on the degrees of the graph nodes, wherein a graph node with a higher calculated degree among unallocated graph nodes is allocated prior to a graph node with a lower calculated degree, such that the graph nodes are partitioned as primary graph nodes in the graph data partitions (see Mell, Section 2 Methods and Materials, where the heuristic we are using to perform vertex partitioning is to iteratively extract a highest degree vertex from a graph, G; we denote G as having n vertices and m non-loop edges with the degree of each node being calculated ignoring any self-loops(since self-loops have no bearing on the connectivity of G); we iteratively remove nodes until some set number, k, of vertices are extracted with k ≤ m/2 (were m/2 highest degree nodes removed, all remaining nodes would have degree 0); after extracting a vertex, we recalculate any affected node degrees (decrementing each of them); the rationale behind the approach is that removal of a highest degree node will remove the most number of edges and thus intuitively will have a better chance of disconnecting a graph compared to removing a lower degree node with fewer edges).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to substitute the greedy node selection algorithm in Elyasi and the task-based node allocation strategy in Park with the high degree node first selection algorithm in Mell for the benefit of intuitively will have a better chance of disconnecting a graph (see Mell, Section 2, Methods and Materials).
Elyasi in view of Park and Mell does not disclose the partitioning is according to a computing load balancing allocation algorithm. Moiseev discloses the partitioning is according to a computing load balancing allocation algorithm (see Moiseev, paragraph [0026], where graph partitioning is an important step in distributed computations; this task is essential for the analysis of large graphs due to large runtime … the way the graph is partitioned influences critically on the load balance).
Elyasi, Park, Mell, and Moiseev are directed to graph partitioning, therefore it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to combine Elyasi, Park, and Mell with Moiseev as it amounts to combining prior art elements according to known methods to yield predictable results (see MPEP 2143(A)(I)).
Regarding Claim 10, Elyasi in view of Park, Mell and Moiseev discloses the computer-implemented device according to Claim 9, wherein selecting the associated edge allocation strategy comprises selecting the associated edge allocation strategy from an outgoing edge allocation strategy, an incoming edge allocation strategy (see Elyasi, paragraph [0027], where embodiments disclosed herein … (ii) store the ‘in edges’ of destination vertices associated with each partition separately along with their indexing information), or a combined outgoing edge and income edge allocation strategy.
Regarding Claim 11, Elyasi in view of Park, Mell and Moiseev discloses the computer-implemented device according to Claim 9, wherein the allocating the edge data of the associated edges of the primary graph nodes to the corresponding graph data partitions comprises:
obtaining edge data of the associated edges from an edge list of the graph data based on edge list offsets of the associated edges (see Elyasi, Fig. 2, where edge data for partition 0 includes out-edges and accompanying offsets); and
allocating the edge data of the associated edges to the corresponding graph data partitions (see Elyasi, Fig. 2, where edge data for partition 0 includes out-edges and accompanying offsets).
Regarding Claim 12, Elyasi in view of Park, Mell and Moiseev discloses the computer-implemented device according to Claim 9, wherein the one or more operations comprise at least one of:
allocating local node identifiers and global node identifiers to the primary graph node in the graph data partition and the mirror graph node; or
establishing a node mapping relationship between the mirror graph node and a corresponding primary graph node in another graph data partition (see Elyasi, paragraph [0038], where when all partitions have been processed, the graph data coordinator logic section 405 may read destination vertex data for each partition and update the corresponding mirrors on other partitions).
Regarding Claim 13, Elyasi in view of Park, Mell and Moiseev discloses the computer-implemented device according to Claim 9, wherein an edge list of the edge data is in a format of a sparse adjacency list (see Elyasi, paragraph [0052], where partitioning pre-processing step may further include: for each edge “→” of an edge list in which vertex “u” is associated with vertex “v” in a “u→v” relationship [it is the position of the Examiner that a list of edges that only contains existing edges is not patentably distinguishable from a sparse adjacency list]).
Regarding Claim 14, Elyasi in view of Park, Mell and Moiseev discloses the computer-implemented device according to Claim 9, wherein the one or more operations further comprise generating partition offset information for the graph data partition and storing the partition offset information in the graph data partition, wherein the partition offset information comprises a number of primary graph nodes in the graph data partition (see Elyasi, paragraph [0040], where metadata 505 is maintained for the destination vertex (e.g., Vertex ‘0’ of Fig. 5) includes partition IDs (e.g., 520) of mirrors 480 of each vertex, and the offset (e.g., Offset A, Offset N, etc. of Fig. 5) for each partition).
Regarding Claim 15, Elyasi discloses a non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising:
for an associated edge of a primary graph node, constructing a replica of another graph node that corresponds to the primary graph node for the associated edge and storing the replica as a mirror graph node in a graph data partition corresponding to the primary graph node (see Elyasi, paragraph [0024], where source vertices (e.g., Vertex ‘A’, Vertex ‘B’, etc.) for each partition (e.g., Partition 0, Partition 1, etc.) may be divided into mirror vertices (e.g., 225) and master vertices (e.g., 230) [it is the position of the Examiner that ‘master’ vertices are not patentably distinguishable from primary graph nodes).
Elyasi does not disclose:
selecting an associated edge allocation strategy based on a graph data acquisition path direction of a downstream graph computing task;
allocating, in accordance with the associated edge allocation strategy, edge data of associated edges of the primary graph nodes to corresponding graph data partitions, wherein the associated edges comprise at least one of outgoing edges or incoming edges;
calculating a degree of each graph node in graph data based on a graph topology structure of the graph data;
allocating the graph nodes in the graph data to a plurality of graph data partitions based on the degrees of the graph nodes according to a computing load balancing algorithm, wherein a graph node with a higher calculated degree among unallocated graph nodes is allocated prior to a graph node with a lower calculated degree, such that the graph nodes are partitioned as primary graph nodes in the graph data partitions; and
storage of the replica as a mirror graph node in a graph data partition is for use in performing the downstream graph computing task.
Elyasi in view of Park discloses:
selecting an associated edge allocation strategy based on a graph data acquisition path direction of a downstream graph computing task (see Park, Abstract, where we propose a machine learning-based approach to select the most appropriate partitioning strategy for a given graph and processing algorithm; our approach enumerates viable partitioning strategies, predicts the execution time of the target algorithm for each, and selects the partitioning strategy with the fastest estimated execution time; see also 5.3.7, where random walk is a partitioning strategy that starts from a source vertex and selects a random vertex from neighbor vertices connected by out-edges); and
allocating, in accordance with the associated edge allocation strategy, edge data of associated edges of the primary graph nodes to corresponding graph data partitions (see Park, Abstract, where we propose a machine learning-based approach to select the most appropriate partitioning strategy for a given graph and processing algorithm; our approach enumerates viable partitioning strategies, predicts the execution time of the target algorithm for each, and selects the partitioning strategy with the fastest estimated execution time; see also 5.3.7, where random walk is a partitioning strategy that starts from a source vertex and selects a random vertex from neighbor vertices connected by out-edges), wherein the associated edges comprise at least one of outgoing edges or incoming edges (see Elyasi, Fig. 2, where edge data for partition 0 includes a plurality of out edges).
Both Elyasi and Park are directed to graph partitioning, therefore it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to combine Elyasi with Park as it amounts to combining prior art elements according to known methods to yield predictable results (see MPEP 2143(A)(I)).
Elyasi in view of Park does not disclose:
calculating a degree of each graph node in graph data based on a graph topology structure of the graph data;
allocating the graph nodes in the graph data to a plurality of graph data partitions based on the degrees of the graph nodes according to a computing load balancing algorithm, wherein a graph node with a higher calculated degree among unallocated graph nodes is allocated prior to a graph node with a lower calculated degree, such that the graph nodes are partitioned as primary graph nodes in the graph data partitions; and
storage of the replica as a mirror graph node in a graph data partition is for use in performing the downstream graph computing task.
Mell discloses:
calculating a degree of each graph node in graph data based on a graph topology structure of the graph data (see Mell, Section 2 Methods and Materials, where the heuristic we are using to perform vertex partitioning is to iteratively extract a highest degree vertex from a graph, G; we denote G as having n vertices and m non-loop edges with the degree of each node being calculated ignoring any self-loops(since self-loops have no bearing on the connectivity of G); we iteratively remove nodes until some set number, k, of vertices are extracted with k ≤ m/2 (were m/2 highest degree nodes removed, all remaining nodes would have degree 0); after extracting a vertex, we recalculate any affected node degrees (decrementing each of them); the rationale behind the approach is that removal of a highest degree node will remove the most number of edges and thus intuitively will have a better chance of disconnecting a graph compared to removing a lower degree node with fewer edges);
allocating the graph nodes in the graph data to a plurality of graph data partitions based on the degrees of the graph nodes, wherein a graph node with a higher calculated degree among unallocated graph nodes is allocated prior to a graph node with a lower calculated degree, such that the graph nodes are partitioned as primary graph nodes in the graph data partitions (see Mell, Section 2 Methods and Materials, where the heuristic we are using to perform vertex partitioning is to iteratively extract a highest degree vertex from a graph, G; we denote G as having n vertices and m non-loop edges with the degree of each node being calculated ignoring any self-loops(since self-loops have no bearing on the connectivity of G); we iteratively remove nodes until some set number, k, of vertices are extracted with k ≤ m/2 (were m/2 highest degree nodes removed, all remaining nodes would have degree 0); after extracting a vertex, we recalculate any affected node degrees (decrementing each of them); the rationale behind the approach is that removal of a highest degree node will remove the most number of edges and thus intuitively will have a better chance of disconnecting a graph compared to removing a lower degree node with fewer edges).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to substitute the greedy node selection algorithm in Elyasi and the task-based node allocation strategy in Park with the high degree node first selection algorithm in Mell for the benefit of intuitively will have a better chance of disconnecting a graph (see Mell, Section 2, Methods and Materials).
Elyasi in view of Park and Mell does not disclose the partitioning is according to a computing load balancing allocation algorithm. Moiseev discloses the partitioning is according to a computing load balancing allocation algorithm (see Moiseev, paragraph [0026], where graph partitioning is an important step in distributed computations; this task is essential for the analysis of large graphs due to large runtime … the way the graph is partitioned influences critically on the load balance).
Elyasi, Park, Mell, and Moiseev are directed to graph partitioning, therefore it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to combine Elyasi, Park, and Mell with Moiseev as it amounts to combining prior art elements according to known methods to yield predictable results (see MPEP 2143(A)(I)).
Regarding Claim 16, Elyasi in view of Park, Mell and Moiseev discloses the non-transitory, computer-readable medium according to Claim 15, wherein selecting the associated edge allocation strategy comprises selecting the associated edge allocation strategy from an outgoing edge allocation strategy, an incoming edge allocation strategy (see Elyasi, paragraph [0027], where embodiments disclosed herein … (ii) store the ‘in edges’ of destination vertices associated with each partition separately along with their indexing information), or a combined outgoing edge and income edge allocation strategy.
Regarding Claim 17, Elyasi in view of Park, Mell and Moiseev discloses the non-transitory, computer-readable medium according to Claim 15, wherein the allocating the edge data of the associated edges of the primary graph nodes to the corresponding graph data partitions comprises:
obtaining edge data of the associated edges from an edge list of the graph data based on edge list offsets of the associated edges (see Elyasi, Fig. 2, where edge data for partition 0 includes out-edges and accompanying offsets); and
allocating the edge data of the associated edges to the corresponding graph data partitions (see Elyasi, Fig. 2, where edge data for partition 0 includes out-edges and accompanying offsets).
Regarding Claim 18, Elyasi in view of Park, Mell and Moiseev discloses the non-transitory, computer-readable medium according to Claim 15, wherein the one or more operations comprise at least one of:
allocating local node identifiers and global node identifiers to the primary graph node in the graph data partition and the mirror graph node; or
establishing a node mapping relationship between the mirror graph node and a corresponding primary graph node in another graph data partition (see Elyasi, paragraph [0038], where when all partitions have been processed, the graph data coordinator logic section 405 may read destination vertex data for each partition and update the corresponding mirrors on other partitions).
Regarding Claim 19, Elyasi in view of Park, Mell and Moiseev discloses the non-transitory, computer-readable medium according to Claim 15, wherein an edge list of the edge data is in a format of a sparse adjacency list (see Elyasi, paragraph [0052], where partitioning pre-processing step may further include: for each edge “→” of an edge list in which vertex “u” is associated with vertex “v” in a “u→v” relationship [it is the position of the Examiner that a list of edges that only contains existing edges is not patentably distinguishable from a sparse adjacency list]).
Regarding Claim 20, Elyasi in view of Park, Mell and Moiseev discloses the non-transitory, computer-readable medium according to Claim 15, wherein the one or more operations further comprise generating partition offset information for the graph data partition and storing the partition offset information in the graph data partition, wherein the partition offset information comprises a number of primary graph nodes in the graph data partition (see Elyasi, paragraph [0040], where metadata 505 is maintained for the destination vertex (e.g., Vertex ‘0’ of Fig. 5) includes partition IDs (e.g., 520) of mirrors 480 of each vertex, and the offset (e.g., Offset A, Offset N, etc. of Fig. 5) for each partition).
Response to Arguments
Applicant’s Arguments, filed June 8, 2026, have been fully considered, but they are not persuasive.
Applicant argues on page 8 of Applicant’s Remarks that Elyasi, alone, or in combination with Mell, Moiseev, and Park, does not teach, disclose, or fairly suggest, all of the elements of Independent Claims 1, 9, and 15 as amended with the subject matter of dependent Claim 3. Specifically, Applicant argues that the combination of references does not teach “selecting an associated edge allocation strategy based on a graph data acquisition path direction of a downstream graph computing task.” The Examiner respectfully disagrees.
Park explicitly discloses partitioning a graph and allocating both nodes and vertices to partitions in the graph (see Park, Section 1. Introduction, paragraph 2, where a partitioning strategy determines how vertices and edges are divided into clusters) based on how the graph data is to be used by a application or task (see Park, Abstract, where analyzing large graph data is an essential part of many modern applications, such as social networks; due to its large computational complexity, distributed processing is frequently employed; this requires graph data to be divided across nodes, and the choice of partitioning strategy has a great impact on the execution time of the task). It is the position of the Examiner that the cited task for which the graph data is to be used, of which a social network is given as an example, is not patentably distinguishable from a downstream computing task. Accordingly, it is the position of the Examiner that the combination of references disclose all of the elements of Independent Claims 1, 9, and 15.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to FARHAD AGHARAHIMI whose telephone number is (571)272-9864. The examiner can normally be reached M-F 9am - 5pm ET.
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, Apu Mofiz can be reached at 571-272-4080. 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.
/FARHAD AGHARAHIMI/Examiner, Art Unit 2161
/APU M MOFIZ/Supervisory Patent Examiner, Art Unit 2161
Prosecution Insights