Data structure using a tree bitmap and method for rapid classification of data in a database

A method for searching through a prefix-type data structure stored in trie elements having predefined strides of size greater than one, a stride being a number of levels in a tree grouped together, the prefix structure having a first level trie element and a plurality of second level trie elements, each trie element being a description of data in one of the strides, the method comprising:

• a) providing a first code of the first level trie element, the first code representing each of a plurality of nodes within a corresponding stride of the first level trie element, the first code identifying each of the plurality of nodes of the corresponding stride as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the corresponding stride, the lowest-level subset including a plurality of said plurality of nodes;
• b) providing a second code identifying which trie paths emanate and which trie paths do not emanate from the lowest-level subset of the plurality of nodes;
• and
• c) providing a single pointer linking the first level trie element with the plurality of second level trie elements,
• the method further comprising:
• d) examining the first code and the second code to extract parameters indicative of termination at a leaf or indicative of a second level trie element;
• e) if termination is indicated, fetching a result value;
• f) if a second level trie element is indicated, proceeding according to the corresponding pointer and parameters to an indicated child element;
• and
• g) repeating steps a) though f) at a next lower level until termination.

A computer-readable medium having stored thereon a data structure for identifying prefixes based on a trie representation of said prefixes, the trie representation being grouped in to strides of a number of tree levels greater than one, the data structure comprising:

• a first trie element,
• a tree bitmap element;
• a result array element;
• and
• a child array element;
• wherein the tree bitmap element includes:
• a first code field for storing a tree bitmap representing each of a plurality of nodes within the stride corresponding to the first trie element, and the tree bitmap identifying each of the plurality of nodes as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the stride corresponding to the first trie element, the lowest-level subset including a plurality of said plurality of nodes;
• and
• a result array pointer field for storing a result array element link to the result array element;
• wherein the first trie element includes:
• a second field for storing a child bitmap for identifying which extending trie paths exist between the lowest-level subset of the plurality of nodes and one or more strides identified in the child array element and which extending trie paths do not emanate from the lowest-level subset of the plurality of nodes;
• a tree bitmap pointer field for storing a tree bitmap element link to the tree bitmap element;
• and
• a child array pointer field for storing a child array link to the child array element;
• wherein the result array element is configured for storing prefix matching results corresponding to prefix nodes identified in the tree bitmap;
• and
• wherein the child array element is configured for storing children elements of the lowest-level subset of the plurality of nodes having an extending trie path identified in the child bitmap.

computer-readable medium having stored thereon a data structure for identifying prefixes based on a trie representation of said prefixes, the trie representation being grouped in to strides of a number of tree levels greater than one, the data structure comprising:

• a first trie element;
• a tree bitmap element;
• a result array element;
• and
• a child array element;
• wherein the tree bitmap element includes a tree bitmap field for storing a tree bitmap representing each of a plurality of nodes within the stride corresponding to the first trie element, and the tree bitmap identifying each of the plurality of nodes as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the stride corresponding to the first trie element, the lowest-level subset including a plurality of said plurality of nodes;
• wherein the first trie element includes:
• a second field for storing a child bitmap for identifying which extending trie paths exist between the lowest-level subset of the plurality of nodes and one or more strides identified in the child array element and which extending trie paths do not emanate from the lowest-level subset of the plurality of nodes;
• a result array pointer field for storing a result array link to the result array element;
• a tree bitmap pointer field for storing a tree bitmap link to the tree bitmap;
• and
• a child array pointer field for storing a child array element link to the child array element;
• wherein the result array element is configured for storing prefix matching results corresponding to prefix nodes identified in the tree bitmap element;
• and
• wherein the child array element is configured for storing children elements of the lowest-level subset of the plurality of nodes having an extending trie path identified in the child bitmap.

A method performed using a tree data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one, each of the plurality of strides represented by a tree bitmap and indications of child paths represented by a child bitmap, said method comprising:

• (a) retrieving a current-level data structure element corresponding to a current-level stride, the current-level data structure element including a current-level tree bitmap, a current-level child bitmap, and a single link to a next-level data structure element;
• the current-level tree bitmap corresponding to a current level stride in the tree data structure, the current-level tree bitmap including a plurality of tree bitmap bits, each of the plurality of tree bitmap bits corresponding to a particular one of a plurality of nodes, the value of a bit of the plurality of tree bitmap bits indicating a corresponding node as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the current level stride, the lowest-level subset including a plurality of said plurality of nodes;
• the current-level child bitmap corresponding to the current level stride, the current-level tree child including a plurality of child bitmap bits, each of the plurality of child bitmap bits corresponding to a particular child path of one of the lowest-level subset of the plurality of nodes, the value of a bit of the plurality of child bits indicating a presence or absence of the corresponding child path;
• (b) evaluating the current-level tree bitmap against a current-level portion of a search string to determine a longest matching prefix node or a no longest prefix match, and updating an indication of the longest matching prefix node in response to said determination of the longest matching prefix node;
• (c) evaluating the current-level child bitmap against the current-level portion of the search string to determine a child stride for a next-level or a no child indication;
• (d) in response to said determination of the child stride, repeating steps (a), (b), and (c) with the current-level stride corresponding to the child stride with the current-level data structure for this next iteration identified based on the single link in the current iteration;
• and
• (e) in response to said determination of the no child indication, retrieving a result based on the indication of the longest matching prefix node.

A computer-readable medium containing computer-executable instructions for performing steps manipulating a tree data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one, each of the plurality of strides represented by a tree bitmap and indications of child paths represented by a child bitmap, said steps comprising:

• (a) retrieving a current-level data structure element corresponding to a current-level stride, the current-level data structure element including a current-level tree bitmap, a current-level child bitmap, and a single link to a next-level data structure element;
• the current-level tree bitmap corresponding to a current level stride in the tree data structure, the current-level tree bitmap including a plurality of tree bitmap bits, each of the plurality of tree bitmap bits corresponding to a particular one of a plurality of nodes, the value of a bit of the plurality of tree bitmap bits indicating a corresponding node as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the current level stride, the lowest-level subset including a plurality of said plurality of nodes;
• the current-level child bitmap corresponding to the current level stride, the current-level tree child including a plurality of child bitmap bits, each of the plurality of child bitmap bits corresponding to a particular child path of one of the lowest-level subset of the plurality of nodes, the value of a bit of the plurality of child bits indicating a presence or absence of the corresponding child path;
• (b) evaluating the current-level tree bitmap against a current-level portion of a search string to determine a longest matching prefix node or a no longest prefix match, and updating an indication of the longest matching prefix node in response to said determination of the longest matching prefix node;
• (c) evaluating the current-level child bitmap against the current-level portion of the search string to determine a child stride for a next-level or a no child indication;
• (d) in response to said determination of the child stride, repeating steps (a), (b), and (c) with the current-level stride corresponding to the child stride with the current-level data structure for this next iteration identified based on the single link in the current iteration;
• and
• (e) in response to said determination of the no child indication, retrieving a result based on the indication of the longest matching prefix node.

An apparatus for manipulating a tree data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one, each of the plurality of strides represented by a tree bitmap and indications of child paths represented by a child bitmap, said apparatus comprising:

• means for retrieving a current-level data structure element corresponding to a current-level stride, the current-level data structure element including a current-level tree bitmap, a current-level child bitmap, and a single link to a next-level data structure element;
• the current-level tree bitmap corresponding to a current level stride in the tree data structure, the current-level tree bitmap including a plurality of tree bitmap bits, each of the plurality of tree bitmap bits corresponding to a particular one of a plurality of nodes, the value of a bit of the plurality of tree bitmap bits indicating a corresponding node as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the current level stride, the lowest-level subset including a plurality of said plurality of nodes;
• the current-level child bitmap corresponding to the current level stride, the current-level tree child including a plurality of child bitmap bits, each of the plurality of child bitmap bits corresponding to a particular child path of one of the lowest-level subset of the plurality of nodes, the value of a bit of the plurality of child bits indicating a presence or absence of the corresponding child path;
• means for evaluating the current-level tree bitmap against a current-level portion of a search string to determine a longest matching prefix node or a no longest prefix match, and updating an indication of the longest matching prefix node in response to said determination of the longest matching prefix node;
• means for evaluating the current-level child bitmap against the current-level portion of the search string to determine a child stride for a next-level or a no child indication;
• and
• means for retrieving a result based on the indication of the longest matching prefix node in response to said determination of the no child indication.