Method and apparatus for generating a shape graph from a binary trie
View Patent ↗A capability is provided for representing a set of data values using data structures, including converting a binary trie data structure representing the set of data values to a shape graph data structure representing the set of data values. The shape graph data structure is generated from the binary trie data structure based on the shapes of the sub-trees rooted at the nodes of the binary trie data structure. The shape graph includes vertices representing shapes of the sub-trees of the binary trie data structure. A shape graph data structure permits operations similar to the operations that may be performed on the binary trie data structure for performing lookups for data values from the set of data values, while at the same time reducing the structural redundancy of the binary trie data structure such that the shape graph data structure provides significant improvements in memory usage over the binary trie data structure.
1. A method for representing a binary trie, the binary trie representing a set of values and comprising a plurality of leaf node and a plurality of non-leaf nodes, the method comprising:
using a processor and a memory for:
determining, for each of the plurality of non-leaf nodes of the binary trie, a shape of a respective sub-tree rooted at the non-leaf node of the binary trie;
constructing a shape graph from the binary trie based on the shapes of the sub-trees rooted at the non-leaf nodes of the binary trie, wherein the shape graph represents the set of values, wherein the shape graph comprises:
a terminating vertex that represents the plurality of leaf nodes of the binary trie; and
a plurality of vertices that represent a respective plurality of unique shapes of the sub-trees rooted at the non-leaf nodes of the binary trie, wherein the plurality of vertices comprises a first vertex, and wherein the first vertex represents a first shape of at least a first sub-tree rooted at a first non-leaf node of the binary trie and a second sub-tree rooted at a second non-leaf node of the binary trie; and
storing the shape graph.
2. The method of claim 1 , wherein the shape graph further comprises a plurality of edges indicative of transitions between the vertices for use in traversing the shape graph for performing value lookups.
3. The method of claim 1 , further comprising:
for each non-leaf node of the binary trie, labeling the non-leaf node of the binary trie using a respective shape label indicating the shape of the sub-tree rooted at the non-leaf node.
4. The method of claim 3 , wherein the determining and the labeling are performed in a single-pass traversal of the binary trie.
5. The method of claim 4 , wherein the single-pass traversal of the binary trie is a post-order traversal.
6. The method of claim 4 , wherein the single-pass traversal of the binary trie is performed in a direction from the leaf nodes toward a root node of the binary trie, wherein performing the determining and the labeling in the single-pass traversal of the binary trie comprises:
assigning a first shape identifier for the leaf nodes and labeling the leaf nodes using a respective plurality of shape labels indicating the first shape identifier; and
for each of the non-leaf nodes of the binary trie:
determining a pair of labels assigned to the two child nodes of the non-leaf node; and
querying a table using the pair of labels, wherein:
based on a determination that the pair of labels is not identified in the table, assigning an unused shape identifier to the non-leaf node, storing the pair of labels and the unused shape identifier associated with the pair of labels in the table, and labeling the non-leaf node with the assigned shape identifier; or
based on a determination that the pair of labels is identified in the table, retrieving from the table a shape identifier associated with the pair of labels, and labeling the non-leaf node with the retrieved shape identifier.
7. The method of claim 6 , wherein, when determining the pair of labels assigned to the two child nodes of a non-leaf node, a non-existent child node is assumed to have a null shape identifier.
8. The method of claim 1 , further comprising:
labeling the leaf nodes and the non-leaf nodes of the binary trie to form thereby a labeled binary trie, where each non-leaf node of the labeled binary trie has associated therewith a respective shape label indicative of the shape of the sub-tree rooted thereat;
wherein constructing the shape graph for the binary trie comprises:
allocating the vertices for the shape graph; and
traversing the labeled binary trie in a manner for determining a plurality of edges to be set between the vertices of the shape graph.
9. The method of claim 8 , wherein allocating the vertices for the shape graph comprises:
allocating k vertices for the shape graph, wherein k is a number of unique sub-tree shapes determined from the binary trie.
10. The method of claim 9 , wherein k is determined from a shape label of the root node of the labeled binary trie.
11. The method of claim 8 , wherein the binary trie is traversed in any order.
12. The method of claim 8 , wherein traversing the labeled binary trie in a manner for determining a plurality of edges to be set between the vertices of the shape graph comprises:
traversing the labeled binary trie in a manner for visiting at least a portion of the nodes of the labeled binary trie, wherein, for a visited one of the nodes of the labeled binary trie:
based on a determination that a shape label of the visited one of the nodes has been encountered already, continuing to a next one of the nodes of the labeled binary trie; or
based on a determination that a shape label of the visited one of the nodes has not been encountered already:
determining a shape label of a 0-branch child node of the visited one of the nodes and determining a shape label of a 1-branch child node of the visited one of the nodes (t); and
setting, in the directed shape graph, a directed 0-edge from a vertex associated with the shape label of the visited one of the nodes to a vertex associated with the shape label of the 0-branch child node of the visited one of the nodes; and
setting, in the directed shape graph, a directed 1-edge from a vertex associated with the shape label of the visited one of the nodes to a vertex associated with the shape label of the 1-branch child node of the visited one of the nodes.
13. The method of claim 1 , wherein the set of values is a subset of a full set of values representable by a full binary trie, wherein the binary trie is a full binary trie including all nodes independent of whether the values indicated by the nodes of the full binary trie are included within the set of values.
14. The method of claim 1 , further comprising:
modifying the binary trie, prior to constructing the shape graph, using leaf pushing.
15. The method of claim 1 , further comprising:
modifying the shape graph to form a multi-bit shape graph.
16. The method of claim 1 , wherein the set of values is a set of IP prefixes for use in performing IP lookups.
17. The method of claim 16 , further comprising:
traversing the shape graph, using at least a portion of an IP address, for determining a matching IP prefix associated with the IP address.
18. The method of claim 17 , further comprising:
determining next hop information for the IP address based on the matching IP prefix of the IP address.
19. An apparatus for representing a binary trie, the binary trie representing a set of values and comprising a plurality of leaf node and a plurality of non-leaf nodes, the apparatus comprising:
a processor and a memory communicatively connected to the processor, the processor configured to:
determine, for each of the plurality of non-leaf nodes of the binary trie, a shape of a respective sub-tree rooted at the non-leaf node of the binary trie;
construct a shape graph from the binary trie based on the shapes of the sub-trees rooted at the non-leaf nodes of the binary trie, wherein the shape graph represents the set of values, wherein the shape graph comprises:
a terminating vertex that represents the plurality of leaf nodes of the binary trie; and
a plurality of vertices that represent a respective plurality of unique shapes of the sub-trees rooted at the non-leaf nodes of the binary trie, wherein the plurality of vertices comprises a first vertex, and wherein the first vertex represents a first shape of at least a first sub-tree rooted at a first non-leaf node of the binary trie and a second sub-tree rooted at a second non-leaf node of the binary trie; and
store the shape graph.
20. A method for performing a lookup for identifying a matching value from a set of values represented using a binary trie, the method comprising:
using a processor and a memory for:
traversing a shape graph for identifying the matching value, wherein the shape graph represents the set of values, wherein the shape graph comprises:
a terminating vertex that represents the plurality of leaf nodes of the binary trie; and
a plurality of vertices that represent a respective plurality of unique shapes of the sub-trees rooted at the non-leaf nodes of the binary trie, wherein the plurality of vertices comprises a first vertex, and wherein the first vertex represents a first shape of at least a first sub-tree rooted at a first non-leaf node of the binary trie and a second sub-tree rooted at a second non-leaf node of the binary trie; and
determining the matching value based at least in part on traversal of the shape graph.