Data Structures

#####A burst trie consists of three distinct components, a set of records, a set of containers, and an access trie:

###Records A record contains a string; information as required by the application using the burst trie (that is, for information such as statistics or word locations); and pointers as required to maintain the container holding the record. Each string is unique.

###Containers A container is a small set of records, maintained as a simple data structure such as a list or a BST. For a container at depth k in a burst trie (depth is discussed below), all strings have length at least k, and the first k characters of all strings are identical. It is not necessary to store these first k characters. Each container also has a header, for storing the statistics used by heuristics for bursting.

Thus a particular container at depth 3 containing "author" and "automated" could also contain "autopsy" but not "auger". Choice of data structure for representing containers is considered later.

###Access trie An access trie is a trie whose leaves are containers. Each node consists of an array p, of length |A|, of pointers, each of which may point to either a trie node or a container, and a single empty-string pointer to a record. The |A| array locations are indexed by the characters c in the set of A. The remaining pointer is indexed by the empty string.

The depth of the root is defined to be 1. Leaves are at varying depths.

As discussed in Section 6, there are more compact forms of trie, designed to alleviate the space wasted by sparse nodes. However, by design the nodes in an access trie should rarely be sparse, and compact nodes are more costly to traverse and maintain. As we show, for small alphabets the use of simple arrays does not lead to excessive space usage; for large alphabets, other strategies-- such as dividing symbols into bytes-- have to be explored, as is true for tries in general.