Efficient storage and utilization of a hierarchical data set

Patent metadata

Field	Value
Publication number	US-11036797-B2
Application number	US-201816123124-A
Country	US
Kind code	B2
Filing date	Sep 6, 2018
Priority date	Oct 12, 2017
Publication date	Jun 15, 2021
Grant date	Jun 15, 2021

Abstract

First data of a hierarchical data structure is accessed. A directed graph is generated based on the first data. Generating the directed graph includes creating multiple nodes representing the first data and linking first nodes representing data at a particular level of the hierarchical data structure to second nodes representing data at a lower level of the hierarchical data structure. A query requesting information from the hierarchical data structure is received. A particular node, that is a starting point for searching the directed graph based on the query, is identified within the directed graph. Out-links, that link the particular node to other nodes of the directed graph, are identified. Each of the other nodes, that is connected to the particular node by the out-links, is inspected to determine which of the other nodes represents responsive data matching the query. The query is responded with the responsive data.

First claim

What is claimed is:

1. A method comprising:
accessing first data of a hierarchical data structure;
generating a directed graph based on the first data, including:
creating a plurality of nodes representing the first data; and
linking first nodes representing data at a particular level of the hierarchical data structure to second nodes representing data at a lower level of the hierarchical data structure;

generating an adjacency table representing the directed graph;
receiving a query requesting information from the hierarchical data structure;
identifying, within the adjacency table representing the directed graph, a particular node that is a starting point for searching based on the query;
identifying, based on the adjacency table representing the directed graph, out-links that link the particular node to other nodes of the directed graph;
loading, in memory, only a portion of the adjacency table that represents the particular node and the other nodes to which the particular node is linked by the out-links;
processing the query using the portion of the adjacency table loaded in memory, including inspecting data from each of the other nodes that is connected to the particular node by the out-links to determine which of the other nodes represents responsive data matching the query;
generating, based on the inspecting and using the portion of the adjacency table loaded in memory, a sub-graph that matches the query;
serializing the sub-graph that matches the query and was generated using the portion of the adjacency table loaded in memory; and
responding to the query with the serialized sub-graph.

2. The method of claim 1 , further comprising:
after responding to the query:
maintaining, in memory, the portion of the adjacency table that represents the particular node and the other nodes to which the particular node is linked by the out-links;
receiving a subsequent query;
determining that a starting point for the subsequent query is included in the portion of the adjacency table that is maintained in memory; and
responding to the subsequent query using the portion of the adjacency table that is maintained in memory and without reloading, in memory, that portion of the adjacency table.

3. The method of claim 1 , wherein the first data is network configuration data.

4. The method of claim 3 , wherein the network configuration data is YANG modeled data.

5. The method of claim 4 , further comprising:
providing an application program interface (API) for a user to query the YANG modeled network configuration data of the directed graph.

6. The method of claim 5 , wherein receiving a query comprises receiving, from the API, a query for data of the YANG modeled network configuration data; and
responding to the query comprises providing configuration data corresponding to the data of the YANG modeled network configuration data requested by the query.

7. A telecommunications device, comprising:
a memory; and
one or more processors coupled to the memory, wherein the one or more processors are configured to perform operations comprising:
accessing first data of a hierarchical data structure;
generating a directed graph based on the first data, including:
creating a plurality of nodes representing the first data; and
linking first nodes representing data at a particular level of the hierarchical data structure to second nodes representing data at a lower level of the hierarchical data structure;

generating an adjacency table representing the directed graph;
receiving a query requesting information from the hierarchical data structure;
identifying, within the adjacency table representing the directed graph, a particular node that is a starting point for searching based on the query;
identifying, based on the adjacency table representing the directed graph, out-links that link the particular node to other nodes of the directed graph;
loading, in memory, only a portion of the adjacency table that represents the particular node and the other nodes to which the particular node is linked by the out-links;
processing the query using the portion of the adjacency table loaded in memory, including inspecting data from each of the other nodes that is connected to the particular node by the out-links to determine which of the other nodes represents responsive data matching the query;
generating, based on the inspecting and using the portion of the adjacency table loaded in memory, a sub-graph that matches the query;
serializing the sub-graph that matches the query and was generated using the portion of the adjacency table loaded in memory; and
responding to the query with the serialized sub-graph.

8. The telecommunications device of claim 7 , the operations further comprising:
after responding to the query:
maintaining, in memory, the portion of the adjacency table that represents the particular node and the other nodes to which the particular node is linked by the out-links;
receiving a subsequent query;
determining that a starting point for the subsequent query is included in the portion of the adjacency table that is maintained in memory; and
responding to the subsequent query using the portion of the adjacency table that is maintained in memory and without reloading, in memory, that portion of the adjacency table.

9. The telecommunications device of claim 7 , wherein the first data is network configuration data.

10. The telecommunications device of claim 9 , wherein the network configuration data is YANG modeled data.

11. The telecommunications device of claim 10 , the operations further comprising:
providing an application program interface (API) for a user to query the YANG modeled network configuration data of the directed graph.

12. The telecommunications device of claim 11 , wherein receiving a query comprises receiving, from the API, a query for data of the YANG modeled network configuration data; and
responding to the query comprises providing configuration data corresponding to the data of the YANG modeled network configuration data requested by the query.

13. A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising:
accessing first data of a hierarchical data structure;
generating a directed graph based on the first data, including:
creating a plurality of nodes representing the first data; and
linking first nodes representing data at a particular level of the hierarchical data structure to second nodes representing data at a lower level of the hierarchical data structure;

generating an adjacency table representing the directed graph;
receiving a query requesting information from the hierarchical data structure;
identifying, within the adjacency table representing the directed graph, a particular node that is a starting point for searching based on the query;
identifying, based on the adjacency table representing the directed graph, out-links that link the particular node to other nodes of the directed graph;
loading, in memory, only a portion of the adjacency table that represents the particular node and the other nodes to which the particular node is linked by the out-links;
processing the query using the portion of the adjacency table loaded in memory, including inspecting data from each of the other nodes that is connected to the particular node by the out-links to determine which of the other nodes represents responsive data matching the query;
generating, based on the inspecting and using the portion of the adjacency table loaded in memory, a sub-graph that matches the query;
se

Assignees

• Adtran Inc

Inventors

• Hood Jonathan

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/8373

  Query execution · CPC title

• G06F16/835 Primary

  Query processing · CPC title

• G06F16/9027

  Trees · CPC title

• G06F9/54

  Interprogram communication · CPC title