Patent Document ID: 20130226885
Application ID: 13406549
Patent Status: 0

Claim One:
1. A data structure at a computing device the data structure comprising: a plurality of arrays and a bit vector together representing a path-decomposed trie, where a path-decomposed trie is a compressed tree structure having a root connected to a plurality of nodes by branches where terminal nodes are leaves, the tree structure representing a set of strings where prefixes common to two or more strings are represented by the same root-to-node path; and wherein each node has a degree being a number of child nodes branching from the node; and wherein each node has a label being either a set of characters of a string or a skip sequence interleaved with directions taken in a centroid path, where a skip is a length of a label, a skip sequence is a sequence of skips from the root to the node, and a centroid path is a root-to-node path in the tree structure which chooses heavy child nodes having sub-trees with the most nodes; the tree structure being compressed to form a path-decomposed trie by representing root-to-leaf paths of the tree by single nodes in the path-decomposed trie; a first one of the plurality of arrays storing the labels of the path-decomposed trie by interleaving the labels with either node degrees or path directions.