# US 12,118,039 B2 · Visually exploring implicit features of hierarchical graphs based on attributes of nodes of the graphs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,118,039 B2 - Document ID: US12118039B2 - Status: Granted - Kind: B2 - Application number: 17/667,974 - Filed: 2022-02-09 - Published: 2023-08-10 - Granted: 2024-10-15 - Earliest claimed: 2022-02-09 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Maksym Lysak; Viktor Kuropiatnyk; Nikolaos Livathinos; Cesar Berrospi Ramis; Peter Willem Jan Staar; Abderrahim Labbi - Web page: https://patentgrep.com/patent/US12118039B2 ## CPC - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 16/28: Databases characterised by their database models, e.g. relational or object models - G06F 16/9027: {Trees} - G06N 5/022: Knowledge engineering; Knowledge acquisition - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract A computing system, program products and computer-implemented method of exploring data comprises accessing data structures and executing an interaction loop. Data structure captures connected graph nodes associated with attributes containing human-readable data. Interaction loop receives user-selected attributes associated with focal nodes and executes subroutines to determine layouts of an arborescence extending from focal nodes. The subroutines use starting nodes and pivot attributes as arguments. Identifying nodes of subroutines are connected to starting nodes by walking the graph and comparing pivot attributes with attributes associated with connected nodes, obtaining distance-dependent quantities. Subroutines compute layout data, including coordinates of the connected nodes. Coordinates are determined in accordance with the distance-dependent quantities. Interaction loop displays arborescence according to the layout data. Subroutines can be recursively executed, whereby, at each recursion level of execution, it is called with the selected attribute and each node of a selection of nodes, as a starting node. ## Claims ### Claim 1 A computer-implemented method comprising: accessing a data structure capturing a connected graph having nodes connected through edges, wherein the nodes are associated with attributes containing human-readable data; performing a subroutine comprising: receiving a user interaction of selecting a node from the connected graph and an attribute associated with the selected node, wherein the user interacts with a graphical user interface to select the node and the attribute; using the selected node as a focal node and the selected attribute as a pivot attribute to determine a layout of an arborescence extending from the focal node; identifying other nodes connected to the focal node by walking the connected graph; comparing the pivot attribute with attributes associated with the other nodes connected to the focal node to obtain corresponding distance-dependent quantities for each of the other nodes; comparing the distance-dependent quantities to a predetermined threshold, respectively, and assigning, based on the comparing to the predetermined threshold, each of the other nodes to one of two distinct regions relative to the starting node, wherein the two distinct regions are complementary three-dimensional regions; computing layout data that includes coordinates of the other nodes connected to the focal node, wherein the coordinates are determined in accordance with the distance-dependent quantities and based on the region assignment; and displaying, on the graphical user interface, the arborescence according to the layout data as a three-dimensional presentation; receiving a user interaction of selecting a new attribute associated with the focal node on the graphical user interface, wherein the user interacts with the graphical user interface to select the new attribute; updating the layout data by determining new distance-dependent quantities and new region assignments for the other nodes based on the new attribute; and displaying, on the graphical user interface, the arborescence according to the updated layout data. ### Claim 2 (depends on 1) The computer-implemented method according to claim 1, wherein the subroutine is recursively executed at recursion levels of the subroutine's execution, wherein the subroutine is respectively called with each newly selected node identified as the focal node and with the selected attribute. ### Claim 3 (depends on 2) The computer-implemented method according to claim 2, wherein the connected graph is a directed rooted tree, the connected nodes identified are child nodes of the focal node and the selected nodes are non-leaf nodes of the directed rooted tree. ### Claim 4 (depends on 1) The computer-implemented method according to claim 1, wherein the two distinct regions are defined as two complementary halves of a three-dimensional ball centered on the focal node. ### Claim 5 (depends on 4) The computer-implemented method according to claim 4, wherein a dimension of the three-dimensional ball is decreased at each recursion level of repeating the subroutine. ### Claim 6 (depends on 5) The computer-implemented method according to claim 5, wherein recursively executing the subroutine defines a number of spheres, the dimensions of which are determined according to said number, resolving clashes between nodes to be displayed as part of the arborescence. ### Claim 7 (depends on 6) The computer-implemented method according to claim 6, wherein computing the layout data comprises computing the coordinates of the selected nodes in a curvilinear coordinate system. ### Claim 8 (depends on 1) The computer-implemented method according to claim 1, further comprising wherein: the region assigned for each node of the other nodes identified is a port region if the respective one of the distance-dependent quantities obtained for said node is less than or equal to the predetermined threshold, otherwise the region assigned is a starboard region; and the port region and the starboard region correspond to a port side and a starboard side, respectively, of a direction extending from the focal node to which the identified other nodes are connected. ### Claim 9 (depends on 1) The computer-implemented method according to claim 1, wherein the coordinates are determined so that non-leaf nodes of the identified other nodes are arranged along a periphery of a respectively selected one of the two complementary three-dimensional regions. ### Claim 10 (depends on 1) The computer-implemented method according to claim 1, wherein the coordinates are determined so that leaf nodes of the identified other nodes are arranged in an inner portion of a respectively selected one of the two complementary three-dimensional regions. ### Claim 11 (depends on 10) The computer-implemented method according to claim 10, wherein the coordinates are further determined so that leaf nodes of the identified other nodes, which have a same parent node in said connected graph, form a distinct group of nodes in said inner portion of the respectively selected one of the two complementary three-dimensional regions. ### Claim 12 (depends on 11) The computer-implemented method according to claim 11, wherein the coordinates are further determined so that all leaf nodes in a same distinct group are arranged along a bow and joined by respective edges depicted as pedicels branching from an involucre of a peduncle connected to the same parent node. ### Claim 13 (depends on 2) The computer-implemented method according to claim 2, wherein, at computing the arborescence, the subroutine is recursively executed according to a maximal recursion depth, which is set to be less than a maximal depth of the directed tree from the focal node. ### Claim 14 (depends on 1) The computer-implemented method according to claim 1, wherein the pivot attribute is semantically, syntactically, or numerically compared with the attributes associated with the other nodes identified. ### Claim 15 (depends on 1) The computer-implemented method according to claim 1, wherein comparing the pivot attribute with attributes associated with the other nodes identified comprises testing, for each node of the identified other nodes, whether an associated attribute is equal to the pivot attribute or not. ### Claim 16 (depends on 1) The computer-implemented method according to claim 1, wherein the execution of the subroutine is at least partly off-loaded to a hardware accelerator specifically configured for execution of the subroutine. ### Claim 17 (depends on 1) The computer-implemented method according to claim 1, wherein the method further comprises, prior to executing the subroutine, computing a layout of an initial arborescence extending from a default focal node, by using the default focal node and a default pivot attribute. ### Claim 18 (depends on 1) The computer-implemented method according to claim 1, further comprising: receiving, via the graphical user interface, a user selection of one of the other nodes from the displayed layout; and computing a layout of a modified arborescence extending from the selected other node, by calling the subroutine with the selected other node as a new focal node. ### Claim 19 A computer program product comprising: one or more computer readable storage media having computer-readable program instructions stored on the one or more computer readable storage media, said program instructions executes a computer-implemented method comprising: accessing a data structure capturing a connected graph having nodes connected through edges, wherein the nodes are associated with attributes containing human-readable data; performing a subroutine comprising: receiving a user interaction of selecting a node from the connected graph and an attribute associated with the selected node, wherein the user interacts with a graphical user interface to select the node and the attribute; using the selected node as a focal node and the selected attribute as a pivot attribute to determine a layout of an arborescence extending from the focal node; identifying other nodes connected to the focal node by walking the connected graph; comparing the pivot attribute with attributes associated with the other nodes connected to the starting node to obtain corresponding distance-dependent quantities for each of the other nodes; comparing the distance-dependent quantities to a predetermined threshold, respectively, and assigning, based on the comparing to the predetermined threshold, each of the other nodes to one of two distinct regions relative to the starting node, wherein the two distinct regions are complementary three-dimensional regions; computing layout data that includes coordinates of the other nodes connected to the starting node, wherein the coordinates are determined in accordance with the distance-dependent quantities and based on the region assignment; and displaying, on the graphical user interface, the arborescence according to the layout data as a three-dimensional presentation; receiving a user interaction of selecting a new attribute associated with the focal node on the graphical user interface, wherein the user interacts with the graphical user interface to select the new attribute; updating the layout data by determining new distance-dependent quantities and new region assignments for the other nodes based on the new attribute; and displaying, on the graphical user interface, the arborescence according to the updated layout data. ### Claim 20 (depends on 19) The computer program product according to claim 19, wherein the subroutine is recursively executed at recursion levels of the subroutine's execution, wherein the subroutine is respectively called with each newly selected node identified as the focal node and with the selected attribute.