# US 11,113,313 B2 · Fast path traversal in a relational database-based graph structure > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,113,313 B2 - Document ID: US11113313B2 - Status: Granted - Kind: B2 - Application number: 16/038,498 - Filed: 2018-07-18 - Published: 2018-12-20 - Granted: 2021-09-07 - Earliest claimed: 2015-10-21 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Jinjun Xiong; Vladimir Zolotov - Web page: https://patentgrep.com/patent/US11113313B2 ## CPC - G06F 16/285: {Clustering or classification} - G06F 16/2228: {Indexing structures} - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A first plurality of relational tables is obtained from a relational database. Each table of the first plurality of relational tables stores connectivity information for a graph that comprises a plurality of nodes and a plurality of edges connecting the nodes, and each of the nodes is assigned an initial identifier. The nodes are clustered into a plurality of clusters. Each cluster contains a subset of the nodes, and all nodes in each subset are close to each other according to a metric. Each node is assigned a new identifier. The new identifier comprises a concatenation of an identifier associated with the cluster to which the node belongs and an identifier associated with the node. A second plurality of relational tables is constructed and stores connectivity information for the graph. The node is identified in the second plurality of relational tables by the new identifier. ## Claims ### Claim 1 A computer-implemented method, comprising: obtaining a first plurality of relational tables from a relational database, wherein each table of the first plurality of relational tables stores connectivity information for a graph that comprises a plurality of nodes and a plurality of edges connecting the plurality of nodes, wherein each node of the plurality of nodes represents a data item stored in the relational database, each edge represents a relationship between two data items represented by two nodes of the plurality of nodes, and wherein each node of the plurality of nodes is assigned an initial identifier; clustering the plurality of nodes into a plurality of clusters, wherein each cluster of the plurality of clusters contains a subset of the plurality of nodes; assigning to each node in the plurality of nodes a new identifier; and constructing a second plurality of relational tables, wherein each table of the second plurality of relational tables stores connectivity information for the graph, and wherein each node of the plurality of nodes is identified in the second plurality of relational tables by the new identifier, such that a number of data blocks that must be loaded to a computer memory to traverse a path through the graph is minimized by reading index records from a relational table of the second plurality of relational tables. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein all nodes in each subset of the plurality of nodes are close to each other according to a metric. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein the new identifier comprises a concatenation of an identifier associated with one of the plurality of clusters to which the node belongs and an identifier associated with the node. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, wherein each row of each relational table of the second plurality of relational tables comprises: a new identifier associated with a predecessor node from which an edge of the plurality of edges originates; and a new identifier associated with a successor node at which the edge of the plurality of edges terminates. ### Claim 5 (depends on 4) The computer-implemented method of claim 4, wherein the a new identifier associated with the predecessor node comprises a concatenation of an identifier associated with one of the plurality of clusters to which the predecessor node belongs and an identifier associated with the predecessor node, and wherein the a new identifier associated with the successor node comprises a concatenation of an identifier associated with one of the plurality of clusters to which the successor node belongs and an identifier associated with the successor node. ### Claim 6 (depends on 5) The computer-implemented method of claim 5, further comprising: creating an index for each relational table of the second plurality of relational tables, wherein the index comprises a concatenation of the new identifier associated with the predecessor node and the new identifier associated with the successor node. ### Claim 7 (depends on 6) The computer-implemented method of claim 6, wherein the index is organized so that at least some data blocks of index records contain empty space reserved for additions to the index records as a result of updates to the relational database. ### Claim 8 (depends on 6) The computer-implemented method of claim 6, wherein the relational database and the index are organized so that index records corresponding to those of the plurality of nodes that are within a threshold distance of each other are stored in a common data block in the relational database or in neighboring data blocks in the relational database. ### Claim 9 (depends on 6) The computer-implemented method of claim 6, wherein the index is sorted such that a given data block in memory contains entries for which associated predecessor nodes belong to a common cluster of the plurality of clusters. ### Claim 10 (depends on 5) The computer-implemented method of claim 5, wherein the subset of the plurality of nodes includes nodes that are separated from each other by no more than a threshold number of the plurality of edges. ### Claim 11 (depends on 5) The computer-implemented method of claim 5, wherein each row of each relational table of the second plurality of relational tables further comprises: an edge weight associated with the edge of the plurality of edges. ### Claim 12 (depends on 11) The computer-implemented method of claim 11, further comprising: creating an index for the relational table of the second plurality of relational tables, wherein each index comprises a concatenation of the new identifier associated with the predecessor node, the new identifier associated with the successor node, and the edge weight. ### Claim 13 (depends on 12) The computer-implemented method of claim 12, wherein the index is sorted such that a given data block in the relational database contains entries for which associated predecessor nodes belong to a common cluster of the plurality of clusters. ### Claim 14 (depends on 11) The computer-implemented method of claim 11, wherein the subset of the plurality of nodes includes nodes that are separated from each other by no more than a threshold sum of edge weights. ### Claim 15 (depends on 11) The computer-implemented method of claim 11, wherein the weight reflects a length of the edge of the plurality of edges. ### Claim 16 (depends on 1) The computer-implemented method of claim 1, wherein the identifier associated with the node is unique across all of the plurality of nodes in the relational database. ### Claim 17 (depends on 1) The computer-implemented method of claim 1, wherein the identifier associated with the node is unique across all of the subset of the plurality of nodes contained in the one of the plurality of clusters to which the node belongs. ### Claim 18 A machine-readable storage medium encoded with instructions executable by a processor, wherein the instructions cause the processor to perform operations comprising: obtaining a first plurality of relational tables from a relational database, wherein each table of the first plurality of relational tables stores connectivity information for a graph that comprises a plurality of nodes and a plurality of edges connecting the plurality of nodes, wherein each node of the plurality of nodes represents a data item stored in the relational database, each edge represents a relationship between two data items represented by two nodes of the plurality of nodes, and wherein each node of the plurality of nodes is assigned an initial identifier; clustering the plurality of nodes into a plurality of clusters, wherein each cluster of the plurality of clusters contains a subset of the plurality of nodes; assigning to each node in the plurality of nodes a new identifier; and constructing a second plurality of relational tables, wherein each table of the second plurality of relational tables stores connectivity information for the graph, and wherein each node of the plurality of nodes is identified in the second plurality of relational tables by the new identifier, such that a number of data blocks that must be loaded to a computer memory to traverse a path through the graph is minimized by reading index records from a relational table of the second plurality of relational tables. ### Claim 19 A computer-implemented method, comprising: obtaining a first set of nodes of a graph, wherein each node in the first set of nodes represents a data item stored in a relational database, each edge of the graph represents a relationship between two data items represented by two nodes of the first set of nodes, and wherein each node in the first set of nodes is identified by an initial identifier; for each node in the first set of nodes, obtaining an identifier of a cluster of nodes to which the node belongs, wherein the identifier of the cluster is obtained by consulting a connectivity table; constructing, for each node in the first set of nodes, a new identifier that is based on the initial identifier identifying the node and the identifier of the cluster to which the node belongs; and traversing a path through the graph that connects two nodes in the first set of nodes, wherein the traversing is performed by reading index records from a relational table that identifies each node in the first plurality of nodes by its respective new identifier, and wherein the reading minimizes a number of data blocks that must be loaded to a computer memory to traverse the path. ### Claim 20 (depends on 19) The computer-implemented method of claim 19, further comprising: recording a second set of nodes belonging to the path; and recording a weight assigned to each edge belonging to the path, wherein the traversing comprises: submitting a query to a sorted index of a relational table, wherein the relational table stores connectivity information for the graph, and wherein each node in the first set of nodes is identified in the relational table by an identifier that is a concatenation of an identifier of a cluster of connected nodes to which the node belongs and an identifier of the node.