m-Bonsai: a Practical Compact Dynamic Trie∗

arXiv:1704.05682v1 [] 19 Apr 2017

Andreas Poyias
Department of Informatics, University of Leicester
University Road, Leicester, LE1 7RH, United Kingdom.
ap480@leicester.ac.uk
Simon J. Puglisi
Helsinki Institute of Information Technology,
Department of Computer Science, University of Helsinki,
P. O. Box 68, FI-00014, Finland.
puglisi@cs.helsinki.fi
Rajeev Raman
Department of Informatics, University of Leicester
University Road, Leicester, LE1 7RH, United Kingdom.
r.raman@leicester.ac.uk
April 20, 2017

Abstract
We consider the problem of implementing a space-efficient dynamic trie, with an emphasis on
good practical performance. For a trie with n nodes with an alphabet of size σ, the informationtheoretic lower bound is n log σ + O(n) bits. The Bonsai data structure is a compact trie
proposed by Darragh et al. (Softw., Pract. Exper. 23(3), 1993, pp. 277–291). Its disadvantages
include the user having to specify an upper bound M on the trie size in advance (which cannot
be changed easily after initalization), a space usage of M log σ + O(M log log M ) (which is
asymptotically non-optimal for smaller σ or if n ≪ M ) and a lack of support for deletions. It
supports traversal and update operations in O(1/ǫ) expected time (based on assumptions about
the behaviour of hash functions), where ǫ = (M − n)/M and has excellent speed performance in
practice. We propose an alternative, m-Bonsai, that addresses the above problems, obtaining
a trie that uses (1 + β)n(log σ + O(1)) bits in expectation, and supports traversal and update
operations in O(1/β) expected time and O(1/β 2 ) amortized expected time, for any user-specified
parameter β > 0 (again based on assumptions about the behaviour of hash functions). We give
an implementation of m-Bonsai which uses considerably less memory and is slightly faster than
the original Bonsai.

1

Introduction

In this paper, we consider practical approaches to the problem of implementing a dynamic trie
in a highly space-efficient manner. A dynamic trie (also known as a dynamic cardinal tree [3])
∗

This research was supported in part by the Academy of Finland via grant 294143.

1

is a rooted tree, where each child of a node is labelled with a distinct symbol from an alphabet
Σ = {0, . . . , σ − 1}. We consider dynamic tries that support the following operations:
create(): create a new empty tree.
getRoot(): return the root of the current tree.
getChild (v, c): return child node of node v having symbol c, if any (and return −1 if no such child
exists).
getParent(v): return the parent of node v.
getLabel (v): return the label (i.e. symbol) of node v.
addLeaf (v, c): add a new child of v with symbol c and return the newly created node.
delLeaf (v, c): delete the child of v with symbol c, provided that the child indicated is a leaf (if
the user asks to delete a child that is not a leaf, the subsequent operations may not execute
correctly).
The trie is a classic data structure (the name dates back to 1959 [8]) that has numerous applications
in string processing. A naive implementation of tries uses pointers. Using this approach, each node
in an n-node binary trie uses 3 pointers for the navigational operations. A popular alternative
for larger alphabets is the ternary search tree (TST) [4], which uses 4 pointers (3 plus a parent
pointer), in addition to the space for a symbol. Other approaches include the double-array trie
(DAT) [1], which uses a minimum of two integers per node, each of magnitude O(n). Since a
pointer must asymptotically use Ω(log n) bits of memory, the asymptotic space bound of TST
(or DAT) is O(n(log n + log σ)) bits1 . However, the information-theoretic space lower bound of
n log σ + O(n) bits (see e.g. [3]) corresponds to one symbol and O(1) bits per node, so the space
usage of both TST and DAT is asymptotically non-optimal. In practice, log σ is a few bits, or one
or two bytes at most. An overhead of 4 pointers per node, or 32n bytes on today’s machines, makes
it impossible to hold tries with even moderately many nodes in main memory. Although tries can
be path-compressed by deleting nodes with just one child and storing paths explicitly, this approach
(or more elaborate ones [23]) cannot guarantee a small space bound.
Motivated by this, a number of space-efficient solutions were proposed [18, 3, 28, 11, 12], which
represent static tries in information-theoretically optimal space, and support a wide range of operations. A number of asymptotic worst-case results for dynamic tries are given in [22, 29, 2, 20]. As
our focus is on practical performance, we do not discuss all previous results in detail and refer the
reader to, e.g., [2], for a comparison. For completeness, we give a summary of some of the results of
[2, 20]. These results, use the standard word RAM model with word size Θ(log n) bits, as do ours.
The first uses almost optimal 2n+n log σ +o(n log σ) bits, and supports trie operations in O(1) time
if σ = polylog(n) and in O(log σ/ log log σ) time otherwise. The second [20] uses O(n log σ) bits
and supports individual dynamic trie operations in O(log log n) amortized expected time, although
finding the longest prefix of a string in the trie can be done in O(log k/ logσ n + log log n) expected
time. Neither of these methods has been fully implemented, although a preliminary attempt (without memory usage measurements) was presented in [30]. Finally, we mention the wavelet trie [17],
1

Logarithms are to base 2 unless stated otherwise.

2

which is a data structure for a sequence of strings, and in principle can replace tries in many applications. Although in theory it is dynamic, we are not aware of any implementation of a dynamic
wavelet trie.
Predating most of this work, Darragh et al. [7] proposed the Bonsai data structure, which uses
a different approach to support the above dynamic trie operations in O(1) expected time (based
on assumptions about the behaviour of hash functions, which we will describe later). The Bonsai
data structure, although displaying excellent practical performance in terms of run-time, has some
deficiencies as a dynamic trie data structure. It is expressed in terms of a parameter M , which we
will refer to as the capacity of the trie. In what follows, unless stated explicitly otherwise, M will
be used to refer to this parameter, n (which must satisfy n < M ) will refer to the current number
of nodes in the trie, ǫ will be used to denote (M − n)/M (i.e. ǫ satisfies n = (1 − ǫ)M ), and α will
be used to denote 1 − ǫ.
The Bonsai data structure allows a trie to be grown from empty to a theoretical maximum of
M nodes, uses M log σ + O(M log log M ) bits of space and performs the above set of operations in
O(1) expected time. However:
• It is clear that, to perform operations in O(1) expected time and use space that is not too far
from optimal, n must lie between (1−c1 )M and (1−c2 )M , for small constants 0 < c2 < c1 < 1.
The standard way to maintain the above invariant is by periodically rebuilding the trie with
a new smaller or larger value of M , depending on whether n is smaller than (1 − c1 )M or
larger than (1 − c2 )M , respectively.

To keep the expected (amortized) cost of rebuilding down to O(1), the rebuilding must take
O(n) expected time. We are not aware of any way to achieve this without using Θ(n log n)
additional bits—an unacceptably high cost. The natural approach to rebuilding, to traverse
the old tree and copy it node-by-node to the new data structure, requires the old tree to
be traversed in O(n) time. Unfortunately, in a Bonsai tree only root-to-leaf and leaf-to-root
paths can be traversed efficiently. While a Bonsai tree can be traversed in O(nσ) time, this
is too slow if σ is large.

• Even if the above relationship between n and M is maintained, the space is non-optimal due
to the additive O(M log log M ) bits term in the space usage of Bonsai, which can dominate
the remaining terms of M (log σ + O(1)) bits when σ is small.
In addition, the Bonsai data structure also has a certain chance of failure: if it fails then the data
structure may need to be rebuilt, and its not clear how to do this without affecting the space and
time complexities. Finally, it is not clear how to support delLeaf (Darragh et al. do not claim to
support this operation).
In this paper, we introduce m-Bonsai2 , a variant of Bonsai. The advantages of m-Bonsai include:
• Based upon the same assumptions about the behaviour of hash functions as in Darragh et al.
[7], our variant uses M (log σ + O(1)) bits of memory in expectation, and supports getChild
in O(1/ǫ) expected time, and getParent, getRoot , and getLabel in O(1) time.
• Using O(M log σ) additional bits of space, we are able to traverse a Bonsai tree in O(n + M )
time (in fact, we can traverse it in sorted order within these bounds).
2

This could be read as mame-bonsai (豆盆栽) a kind of small bonsai plant, or mini-bonsai.

3

• addLeaf and delLeaf can be supported in O((1/ǫ)2 ) amortized expected time. Note that in
delLeaf the application needs to ensure that a deleted node is indeed a leaf3 .
As a consequence, we obtain a trie representation that, for any given constant β > 0, uses at most
(1+ β)(n log σ + O(n)) bits of space, and supports the operations addLeaf and delLeaf in O((1/β)2 )
expected amortized time, getChild in O(1/β) expected time, and getLabel and getParent in O(1)
worst-case time. This trie representation, however, periodically uses O(n log σ) bits of temporary
additional working memory to traverse and rebuild the trie.
We give two practical variants of m-Bonsai. Our implementations and experimental evaluations
show our first variant to be consistently faster, and significantly more space-efficient, than the
original Bonsai. The second variant is even more space-efficient but rather slower. Of course, all
Bonsai variants use at least 20 times less space than TSTs for small alphabets and compare well in
terms of speed with TSTs. We also note that our experiments show that the hash functions used
in Bonsai appear to behave in line with the assumptions about their behaviour.
The rest of this paper is organized as follows. In Section 2, we summarize the Bonsai data
structure [7], focussing on asymptotics. Section 3 summarizes the m-Bonsai approach. In Section
4 we give practical approaches to implementing the data structure described in Section 3, and give
details of the implementation and experimental evaluation.

2

Preliminaries

2.1

Bit-vectors.

Given a bit string x1 , . . . , xn , we define the following operations:
select1 (x, i): Given an index i, return the location of ith 1 in x.
rank1 (x, i): Return the number of 1s upto and including location i in x.
Lemma 1 (Pǎtraşcu [25]) A bit string can be represented in n + O(n/(log n)2 ) bits such that
select1 and rank1 can be supported in O(1) time.
The above data structure can be dynamized by adding the following operation:
flip(x, i): Given an index i, set xi to 1 − xi .
It can be shown that for bit-strings that are polynomial in the word size, all the above operations
can be supported in O(1) time:
Lemma 2 ([27]) A bit string of length m = wO(1) bits can be represented in m + o(m) bits such
that select1 , rank1 and flip can be supported in O(1) time, where w is the word size of the machine.
3

If the application cannot ensure this, one can use the CDRW array data structure [19, 26] to maintain the number
of children of each node (as it changes with insertions and deletions) with no asymptotic slowdown in time complexity
and an additional space cost of O(n log log n) bits.

4

2.2

Compact hash tables

We now sketch the compact hash table (CHT) described by Cleary [6]. The objective is to store a
set X of key-value pairs, where the keys are from U = {0, . . . , u − 1} and the values (also referred
to as satellite data) are from Σ = {0, . . . , σ − 1}, and to support insertion and deletion of key-value
pairs, checking membership of a given key in X, and retrieval of the value associated with a given
key.
Assuming that |X| = n, we let M > n be the capacity of the CHT. The CHT is comprised
of two arrays, Q and F and two bit-strings of length M . To be notationally consistent with the
introduction, we take ǫ = (M − n)/M . The description below assumes that n does not change
significantly due to insertions and deletions into X—standard techniques such as rebuilding can be
used to avoid this assumption. Keys are stored in Q using open addressing and linear probing4 . In
normal implementations of hashing with open addressing, the keys would be stored in Q so that
they can be compared with a key that is the argument to a given operation. Q would then take
M ⌈log U ⌉ bits, which is excessive. To reduce the space usage of Q, Cleary uses quotienting [21].
In rough terms, the aim of quotienting is the following: given a hash function h : U → M , a good
hash function h will have O(u/M ) elements of U that map to any given i ∈ M . Let x ∈ U be a key
that already exists in the hash table, such that h(x) = i. For x, it should suffice to use a quotient
value q(x) of log(u/M ) + O(1) bits to distinguish x from any other keys that may map to i. To
represent x in in the CHT, we store q(x) in Q, and during any operation, given q(x) and h(x), we
should be able to reconstruct x in O(1) time. If a hash function h supports this functionality, we
say that it supports quotienting.
While checking for membership of x in X, one needs to know h(y) for all keys y encountered
during the search. As keys may not be stored at their initial addresses due to collisions, the idea is
to keep all keys with the same initial address in consecutive locations in Q (this means that keys
may be moved after they have been inserted) and to use the two bit-strings to effect the mapping
from a key’s initial address to the position in Q containing its quotient (for details of the bit-strings
see [6]). The satellite data is stored in an array F that has entries of size ⌈log σ⌉. The entry
F [i] stores the data associated with the key whose quotient is stored in Q[i] (if any). Thus, the
overall space usage is M (log(u/n) + log σ + O(1)),
which is within a small constant factor of the

information-theoretic minimum space of log nu + n log σ = n log(u/n) + n log σn log e − Θ(n2 /u)
bits. To summarize:
Theorem 3 ([6]) There is a data structure that stores a set X of n keys from {0, . . . , u − 1} and
associated satellite data from {0, . . . , σ − 1} in at most M (log(u/n) + log σ + O(1)) bits, for any
value M > n and supports insertion, deletion, membership testing of keys in X and retrieval of
associated satellite data in O(1/ǫ) time, where ǫ = (M − n)/M . This assumes the existence of a
hash function that supports quotienting and satisfies the full randomness assumption.
Remark 4 The full randomness assumption [9] states that for every x ∈ U , h(x) is a random
variable that is (essentially) uniformly distributed over {0, . . . , M − 1} and is independent of the
random variable h(y) for all y 6= x.
We now give an example of a hash function that supports quotienting that was used by Cleary.
The hash function has the form h(x) = (ax mod p) mod M for some prime p > u and multiplier a,
1 ≤ a ≤ p − 1. For this h we set q(x) = ⌊(ax mod p)/M ⌋ corresponding to x. Given h(x) and q(x),
4

A variant, bidirectional probing, is used in [6], but we simplify this to linear probing.

5

it is possible to reconstruct x to check for membership. Thus, h supports quotienting. Observe that
q(x) is at most ⌈log⌊(p − 1)/M ⌋. In addition, hash the table needs to store one additional value to
indicate an empty (unused) location. Thus, the values in Q are at most ⌈log⌊(p − 1)/M ⌋ + 2⌉ bits.
Since we can always find a p ≤ 2u, the values in Q are at most log(u/n)+3 bits. Although this family
of hash functions is known not to satisfy the full randomness assumption, our implementation uses
this family as well, and it performs well in practice in the applications that we consider.

2.3

Asymptotics of Bonsai

We now sketch the Bonsai data structure, focussing on asymptotics. Let M be the capacity of
the Bonsai data structure, n the current number of nodes in the Bonsai data structure, and let
ǫ = (M − n)/M and α = (1 − ǫ) be as defined in the Introduction. The Bonsai data structure uses
a CHT with capacity M , and refers to nodes via a unique node ID, which is a pair hi, ji where
0 ≤ i < M and 0 ≤ j < λ, where λ is an integer parameter that we discuss in greater detail below.
If we wish to add a child w with symbol c ∈ Σ to a node v with node ID hi, ji, then w’s node ID
is obtained as follows: We create the key of w using the node ID of v, which is a triple hi, j, ci.
We insert the key into the CHT. Letting h : {0, . . . , M · λ · σ − 1} 7→ {0, . . . , M − 1} be the hash
function used in the CHT. We evaluate h on the key of w. If i′ = h(hi, j, ci), the node ID of w is
hi′ , j ′ i where j ′ ≥ 0 is the lowest integer such that there is no existing node with a node ID hi′ , j ′ i;
i′ is called the initial address of w.
Given the ID of a node, we can search for the key of any potential child in the CHT, which
allows us to check if that child is present or not. However, to get the node ID of the child, we
need to recall that all keys with the same initial hash address in the CHT are stored consecutively.
The node ID of the child is obtained by checking its position within the set of keys with the same
initial address as itself. This explains how to support the operations getChild and addLeaf ; for
getParent(v) note that the key of v encodes the node ID of its parent. There are, however, two
weaknesses in the functionality of the Bonsai tree.
• It is not clear how to support delLeaf in this data structure without affecting the time and
space complexities (indeed, as stated earlier, Darragh et al. [7] do not claim support for
delLeaf ). If a leaf v with node ID hi, ji is deleted, we may not be able to handle this deletion
explicitly by moving keys to close the gap, as any other keys with the same initial address
cannot be moved without changing their node IDs (and hence the node IDs of all their
descendants). Leaving a gap by marking the location previously occupied by v as “deleted”
has the problem that the newly-vacated location can only store keys that have the same initial
address i (in contrast to normal open address hashing). To the best of our knowledge, there
is no analysis of the space usage of open hashing under this constraint.
• As noted in the Introduction, is not obvious how to traverse an n-node tree in better than
O((nσ)/ǫ) time. This also means that the Bonsai tree cannot be resized if n falls well below
(or comes too close to) M without affecting the overall time complexity of addLeaf and
delLeaf .
Asymptotic space usage. In addition to the two bit-vectors of M bits each, the main space
usage of the Bonsai structure is Q. Since a prime p can be found that is < 2 · M · λ · σ, it follows
that the values in Q are at most ⌈log(2σλ + 1)⌉ bits. The space usage of Bonsai is therefore
M (log σ + log λ + O(1)) bits.
6

Since the choice of the prime p depends on λ, λ must be fixed in advance. However, if more
than λ keys are hashed to any value in {0, . . . , M − 1}, the algorithm is unable to continue and
must spend O((nσ)/ǫ) time to traverse and possibly re-hash the tree. Thus, λ should be chosen
large enough to reduce the probability of more than λ keys hashing to the same initial address
to acceptable levels. In [7] the authors, assuming the hash function satisfies the full randomness
assumption argue that choosing λ = O(log M/ log log M ) reduces the probability of error to at most
M −c for any constant c (choosing asymptotically smaller λ causes the algorithm almost certainly
to fail). As the optimal space usage for an n-node trie on an alphabet of size σ is O(n log σ) bits,
the additive term of O(M log λ) = O(n log log n) makes the space usage of Bonsai non-optimal for
small alphabets.
However, even this choice of λ is not well-justified from a formal perspective, since the hash
function used is quite weak—it is only 2-universal [5]. For 2-universal hash functions, the maximum
√
number of collisions can only be bounded to O( n) [13] (note that it is not obvious how to use
more robust hash functions, since quotienting may not be possible). Choosing λ to be this large
would make the space usage of the Bonsai structure asymptotically uninteresting.
Practical analysis. In practice, we note that choosing λ = 16 as suggested in [7] gives a relatively
high failure probability for M = 256 and α = 0.8, using the formula in [7]. Choosing choosing
λ = 32, and assuming the hash function satisfies full randomness, the error probability for M up
to 264 is about 10−19 for α = 0.8 Also, in practice, the prime p is not significantly larger than M λσ
[24, Lemma 5.1]. As a result (see the paragraph following 3) the space usage of Bonsai is typically
well approximated by M (⌈log σ⌉ + 7) bits for the tree sizes under consideration in this paper (for
alphabet sizes that are powers of 2, we should replace the 7 by 8).

3
3.1

m-Bonsai
Collision handling using O(M) bits

In our approach, each node again has an associated key that needs to be searched for in a hash table,
again implemented using open addressing with linear probing and quotienting. However, the ID of
a node x in our case is a number from {0, . . . , M − 1} that refers to the index in Q that contains
the quotient corresponding to x. If a node with ID i has a child with symbol c ∈ Σ, the child’s key,
which is hi, ci, is hashed using a multiplicative hash function h : {0, . . . , M ·σ −1} 7→ {0, . . . , M −1},
and an initial address i′ is computed. If i′′ is the smallest index ≥ i′ such that Q[i′′ ] is vacant, then
we store q(x) in Q[i′′ ]. Observe that q(x) ≤ ⌈2σ⌉, so Q takes M log σ + O(M ) bits. In addition, we
have a displacement array D, and set D[i′′ ] = i′′ − i′ . From the pair Q[l] and D[l], we can obtain
both the initial hash address of the key stored there and its quotient, and thus reconstruct the key.
The key idea is that in expectation, the average value in D is small:
Proposition
5 Assuming h is fully independent and uniformly random, the expected value of
PM −1
α2
i=0 D[i] after all n = αM nodes have been inserted is ≈ M · 2(1−α) .
Proof. The average number of probes, over all keys in the table, made in a successful search is
1
) [21]. Multiplying this by n = αM gives the total average number of probes. However,
≈ 12 (1 + 1−α
the number of probes for a key is one more than its displacement value. Subtracting αM from the
above and simplifying gives the result.
✷ Thus, encoding
7

Table 1: Average number of bits per entry needed to encode the displacement array using the
unary, Elias-γ and Golomb encodings. For the unary encoding, Proposition 5 predicts 1.816̇, 2.6
and 5.05 bits per value. For file details see Table 2.
unary
γ
Golomb
Load Factor
0.7
0.8
0.9
0.7
0.8
0.9
0.7
0.8
0.9
Pumsb 1.81 2.58 5.05 1.74 2.11 2.65 2.32 2.69 3.64
Accidents 1.81 2.58 5.06 1.74 2.11 2.69 2.33 2.69 3.91
Webdocs 1.82 2.61 5.05 1.75 2.11 2.70 2.33 2.70 3.92
D using variable-length
encoding could be very beneficial. For example, coding D in unary would
PM
take M + i=1 D[i] bits; by Proposition 5, and plugging in α = 0.8, the expected space usage of
D, encoded in unary, should be about 2.6M bits, which is smaller than the overhead of 7M bits
of the original Bonsai. As shown in Table 1, predictions made using Proposition 5 are generally
quite accurate. Table 1 also suggests that encoding each D[i] using the Elias-γ-code [10] (hereafter
abbreviated to just γ-code), we would come down to about 2.1M bits for the D, for α = 0.8.

3.2

Representing the displacement array

We now describe how to represent the displacement array. A compact dynamic rewriteable array
(CDRW array) is a data structure for a sequence of non-negative integers that supports the following
operations:
create(n): Create an array A of size n with all entries initialized to zero.
set(A, i, v): Set A[i] to v where v ≥ 0 and v = nO(1) .
get (A, i): Return A[i].
The following lemma shows how to implement such a data structure. Note that the apparently slow
running time of set is enough to represent the displacement array without asymptotic slowdown:
setting D[i] = v means that O(v) time has already been spent in the hash table finding an empty
slot for the key.
P
Lemma 6 A CDRW array A of size n can be represented in ni=1 |γ(A[i] + 1)| + n + o(n) bits,
supporting get in O(1) time and set(A, i, v) in O(v) amortized time.
Proof. We divide A into contiguous blocks of size b = (log n)3/2 . The i-th block Bi = A[bi..bi +
b − 1] will be stored in one or two contiguous sequences of memory locations. There will be a
pointer pointing to the start each of these contiguous sequences of memory locations.
We first give a naive representation of a block. All values in a block are encoded using γ-codes
and (in essence) concatenated into a single bit-string. A set operation is performed by decoding all
the γ-codes in the block, and re-encoding the new sequence of γ-codes. Since each γ-code is O(log n)
bits, or O(1) words, long, it can be decoded in O(1) time. Decoding and re-encoding an entire block
therefore takes O(b) time, which is also the time for the set operation. A get operation can be
realized in O(1) time using the standard idea of to concatenating the unary and binary portions
of the γ-codes separately into two bit-strings, and to use select1 operations on the unary bit-string
8

Pbi+b−1
to obtain, in O(1) time, the binary portion of the i-th γ-code. Let Gi = j=bi
|γ(A[j] + 1)|.
2
The space usage of a single block is therefore Gi + O(Gi /(log n) + log n) bits, where the second
term comes from Lemma 1 applied to the unary part of the γ-codes and the third accounts for
the pointers to the block and any unused space in the “last”
The
P word ofPa block representation.
2 )+(n log n)/b)
overall space usage of the
naive
representation
is
therefore
G
+O((
G
)/(log
n)
i i
i i
P
bits: this adds up to
i Gi + o(n) bits as required. The problem, however, is that set takes
O(b) = O((log n)3/2 ) time, regardless of the value being set.
To improve the speed of the set operation, we first make the observation that by a standard
amortization argument, we can assume that the amortized time allowed for set(A, i, v) is O(v + v ′ ),
where v ′ is the current value of A[i]. Next, we classify the values in a block as being either large
or small, depending on whether or not they are ≥ b. Each block is now stored as two bit-strings,
one each for small and large values. An additional bit-string, of length exactly b bits, indicates
whether a value in a block is large or small. By performing rank1 and flip operations in O(1) time
on this bit-string using Lemma 2 we can reduce a set or get operation on the block to a set or get
operation on either the large or the small bit-strings.
The bit-string for large values (the large bit-string) is represented as in the naive representation.
l
l
2
The space
P usage for the large bit-string for the i-th block is Gi + O(G′ i /(log n) + log n) bits, where
l
Gi = {bi≤j<bi+b|A[j] is large} |γ(A[j] + 1)|. Observe that if either v or v is large, then the O(b)
time needed to update the large bit-string is in fact O(v + v ′ ) as required.
We now consider the representation of the small bit-string. Note that all γ-codes in the
small bit-string are O(log b) = O(log log n) bits long. We divide a block into segments of λ =
⌈c log n/ log log n⌉ values for some sufficiently small constant c > 0. All small values in a segment
are stored as a concatenation
their γ-codes, followed by an overflow zone of between o/2 and 2o
√
bits, where o = ⌈ log n log log n⌉ bits (initially, all overflow zones are of size o bits). All segments,
and their overflow zones, are concatenated into a single bit-string. The small bit-string of the i-th
block,P
also denoted Bi , has length at most Gsi + (b/λ) · (2o) = Gsi + O(log n(log log n)2 ), where
s
Gi = {bi≤j<bi+b|A[j] is small} |γ(A[j] + 1)|. We now discuss how to support operations on Bi .

• Firstly, we need to be able to find the starting and ending points of individual segments in
a block. As the size of a segment
and its overflow zone is an integer of at most O(log log n)
√
bits, and there are only O( log n log log n) segments in a block, we can store the sizes of the
segments and overflow blocks in a block in a single word and perform the appropriate prefix
sum operations in O(1) time using table lookup.

• As we can ensure that a segment is of size at most (log n)/2 by choosing c small enough,
we can support a set operation on a segment in O(1) time, by overwriting the sub-string of
Bi that represents this segment (note that if v, new value, is large, then we would need to
excise the γ-code from the small bit-string, i.e. replace its old γ-code by an empty string). If
the overflow zone exceeds 2o or goes below
√ o/2 bits, the number of set operations that have
taken place in this segment
alone
is
Ω(
log n log log n). Since the length of Bi is at most
√
O(b log log n) bits or O( log n log log n) words, when any segment overflows, we can simply
copy Bi to a new sequence of memory words, and while copying, use table lookup again to
rewrite Bi , ensuring that each segment has an overflow zone of exactly o bits following it.
Note that an overflow zone can only change in size by a constant factor, so rewriting a section
of c log n bits in Bi will give a new bit-string which is also O(log n) bits long, and the rewriting
takes O(1) time as a result. The amortized cost of rewriting is clearly O(1), so the case where
9

a large value is replaced by a small one, thus necessitating a change in Bi even though the
update is to the large bit-string is also covered.
• To support a get in O(1) time is straightforward. After finding the start of a segment, we
extract the appropriate segment in O(1) time and read and decode the appropriate γ-code
using table lookup.
Adding up the space usages for the large and small blocks and the bit-string that distinguishes
between large and small values gives Lemma 6.
✷

3.3

An alternative representation of the displacement array

A quick inspection of the proof of Lemma 6 shows that the data structure is not especially practical.
We now give an alternative approach that is, asymptotically speaking, slightly less space-efficient.
In this approach, we choose two integer parameters 1 < ∆0 < ∆1 , and the displacement array D is
split into three layers:
• The first layer consists of an array D0 of equal-length entries of ∆0 bits each, which has size
M0 = M . All displacement values ≤ 2∆0 − 2 are stored as is in D0 . If D[i] > 2∆0 − 2, then
we set D0 [i] = 2∆0 − 1.
• The second layer consists of a CHT with maximum size M0 ≤ M . If 2∆0 − 1 ≤ D1 [i] ≤ 2∆0 + 2∆1 − 2,
then we store the value D[i] − 2∆0 + 1 as satellite data associated with the key i in the second
layer. Note that the satellite data has value between 0 and 2∆1 − 1 and so fits into ∆1 bits.
• The third layer consists of a standard hash table. If D[i] > 2∆0 + 2∆1 − 2, we store D[i] in
this hash table as satellite date associated with the key i.
Clearly, D[i] can be accessed in O(1) expected time. We now describe how to choose the
parameters ∆0 and ∆1 . We use the following theorem, which is an adaptation of a textbook proof
of the expected search cost of linear probing [16]:
Theorem 7 Given an open-address hash table with load factor α = n/M < 1, assuming full
randomness, the probability that an unsuccessful search makes ≥ k probes is at most bα · ckα for
some constants bα and cα < 1 that depend only on α.
Proof. Let A[0..M − 1] be the hash table. Let x be a key that is not in the hash table, and let
h(x) = i. If the search for x makes ≥ k probes then the locations A[i], A[i + 1], . . . , A[i + k − 1]
must be occupied.5 A necessary condition for this to happen is that there must exist a k′ ≥ k such
that k′ keys are mapped to A[i − k′ + k], . . . , A[i + k − 1], and the remaining keys are mapped to
A[0..i − k′ + k − 1] or A[i + k..M − 1]. Under the assumption of full randomness, the number of keys
mapped to A[i − k′ + k], . . . , A[i + k − 1] is binomially distributed with parameters k′ /M and n,
and the expected number of keys mapped to this region is k′ n/M = αk ′ . Using the multiplicative
form of the Chernoff bound, we get that the probability of ≥ k′ keys being hashed to this region is
at most:
 1−α k′
′
e
= ckα ,
1/α
(1/α)
5

To simplify notation we ignore wrapping around the ends of A.

10

where cα < 1 is a constant that depends only on α. Summing over k ′ = k, k + 1, . . . , n we get that
✷
the probability of an unsuccessful search taking over k probes is at most bα · ckα , as desired.
We now analyze the space usage:
• The space usage of the first layer is M ∆0 . We will choose ∆0 = O(log(5) n) so the space usage
of this layer is O(n log(5) n) bits.
• Let the expected number of displacement values stored in the second layer be n1 . Only
displacement values ≥ θ1 = 2∆0 − 1 will be stored in the second layer, so by Theorem 7,
log(4) n
n1 ≤ αθ1 n. We choose ∆0 so that n1 = O(n/ log(3) n), so θ1 = log
2 . It follows that
∆0 = O(log

(5)

1/cα

n), as promised above.

We now discuss the asymptotic space usage of the CHT. By Theorem 3, the space usage of this
CHT is M1 (log(M/M1 ) + ∆1 + O(1)) bits, where M = n/α is the universe and M1 = n1 /α
is the size of the CHT6 . Since n1 = O(n/ log(3) n), we see that M/M1 = O(log(3) n), and
n
hence the asymptotic space usage of the CHT is O( (3) (log(4) n + ∆1 + O(1))) bits. We
log n
(3)
will choose ∆1 = O(log n), so the space usage of the CHT is O(n) bits.
• Finally, we discuss the asymptotic space usage of the third layer. Let n2 be the expected
number of keys stored in the third layer. By Theorem 7, n2 ≤ αθ2 n, where θ2 = 2∆1 − 3. We
log(2) n
(3)
n), as
choose ∆1 so that n2 = O(n/ log n), so θ2 = log
2 . It follows that ∆1 = O(log
1/cα

promised above. Since the expected space usage of the third layer is O(n2 log n) bits, this is
also O(n) bits as required.

3.4

Traversing the Bonsai tree

In this section, we discuss how to traverse a Bonsai tree with n nodes stored in a hash table array
of size M in O(M + n) expected time. We first give an approach that uses O(M log σ) additional
bits. This is then refined in the next section to an approach that uses only n log σ + O(M + n)
additional bits. Finally, we show how to traverse the Bonsai tree in sorted order.
3.4.1

Simple traversal

Traversal involves a preprocessing step to build three simple support data structures. The first of
these is an array A of M log σ-bit integers. The preprocessing begins by scanning array Q left to
right. For each non-empty entry Q[i] encountered in the scan, we increment A[getParent (i)]. At
the end of the scan, a non-zero entry A[j] is the number of children of node j. We then create
bitvector B, a unary encoding of A, which requires M + n + o(M + n) bits of space. Observe
A[i] = select1 (B, i) − select1 (B, i − 1) and rank0 (select1 (B, i)) is the prefex sum of A[1..i]. We next
allocate an array C, of size n to hold the labels for the children of each node. To fill C, we scan
Q a second time, and for each non-zero entry Q[i] encountered, we set C[select1 (B, getParent (i)) −
getP arent(i) − A[getParent (i)]] ← getLabel (i) and decrement A[getParent (i)]. At the end of the
scan, C[rank0 (select1 (B, i))..rank0 (select1 (B, i + 1))] contains precisely the labels of the children
of node i, and A contains all zeroes. Note that the child labels in C for a given node are not
6

For simplicity, we choose the same load factor for m-Bonsai and the CHT.

11

necessarily in lexicographical order. Preprocessing time is dominated by the scans of Q, which take
O(M ) time. Space usage is (M + n)(log σ + 1 + o(1)) bits.
With A, B and C we are able to affect a depth first traversal of the trie, as follows. B allows
us to determine the label of the first child of an arbitrary node i in constant time: specifically,
it is C[rank0 (select1 (B, i))]. Before we visit the child of i with label C[rank0 (select1 (B, i))], we
increment A[i], which allows us, when we return to node i having visited its children, to determine
the label of the next child of node i to visit: it is C[rank0 (select1 (B, i)) + A[i]]. Traversal, excluding
preprocessing, clearly takes O(n) time.
3.4.2

Reducing space

We can reduce the space used by the simple traversal algorithm described above by exploiting the
fact that the M values in A sum to n and so can be represented in n bits, in such a way that they
can be accessed and updated in constant time with the help of B. Essentially, we will reuse the
M log σ bits initially allocated for A to store the C array and a compressed version of A.
We allocate min(M log σ, M + n(1 + log σ))i bits for A, compute it in the manner described
in the simple traversal algorithms, and then use it to compute B. The space allocated for A
is sufficient to store C, which is of size n log σ bits, and at least another n + M bits. Denote
these n + M bits A′ . We will use B to divide A′ into variable length counters. Specifically, bits
A′ [select1 (B, i − 1)) + 1..select1 (B, i))] will be used to store a counter that ranges from 0 to the
degree of node i. A′ replaces the use of A above during the traversal phase.
3.4.3

Sorted traversal

We now describe a traversal that can be used to output the strings present in the trie in lexicographical order. In addition to the data structures used in simple traversal, we store L, a set of σ
lists of integers, one for each symbol of the alphabet.
We begin by scanning Q left to right, and for each non-empty entry Q[i] encountered in the
scan, we increment A[getParent (i)] (as in the simple traversal algorithm) and append i to the list
for symbol getLabel (i). At the end of the scan the lists contain n elements in total. Note also that
the positions in the list for a given symbol are strictly increasing, and so we store them differentially
encoded as Elias-γ codes to reduce their overall space to n log σ bits.
We then compute B as in the simple traversal algorithm, and allocate space for C. Now,
however, where in the simple algorithm we would make a second scan of Q, we scan the lists of L
in lexicographical order of symbol, starting with the lexicographically smallest symbol. For each
position j encountered in the scan, we access Q[j] and add getLabel(j) to the next available position
in the region of C containing the child labels for node getParent (j) (which we can access as before
with B and A. The child labels in C for a given node now appear in lexicgraphical order, allowing
us to affect a lexicographic traversal of the trie.

3.5

Conclusion

Theorem 8 For any given integer σ and β > 0, there is a data structure that represents a trie on
an alphabet of size σ with n nodes, using (1 + β)(n log σ + O(1)) bits of memory in expectation, and
supporting getRoot, getParent, and getLabel in O(1) time, getChild in O(1/β) expected time, and
addChild and delLeaf in O((1/β)2 ) amortized expected time. The data structure uses O(n log σ)

12

additional bits of temporary memory in order to periodically restructure. The expected time bounds
are based upon the existence of a hash function that supports quotienting and satisfies the full
randomness assumption.
Proof. We represent the tree using the m-Bonsai data structure, representing the D-array using
Lemma 6. Let M be the current capacity of the hash table representing the trie. We choose an
arbitrary location r ∈ {0, . . . , M − 1} as the root of the tree, and set Q[r] = 0 (or indeed any value
that indicates that r is an occupied location) and D[r] = 0 as well. We store r, which is the ID of
the root node, in the data structure. The operations are implemented as follows:
getRoot: We return the stored ID of the root node.
getChild (v, c): We create the key hv, ci and search for it in the CHT. When searching for a key,
we use the quotients stored in Q and O(1)-time access to the D array to recover the keys of
the nodes we encounter during linear probing.
addChild (v, c): We create the key hv, ci and insert it into the CHT. Let i = h(h< v, ci) and
suppose that Q[j] is empty for some j ≥ i. We set D[j] = j − i – this takes O(j − i + 1) time,
but can be subsumed by the cost of probing locations i, . . . , j.
getParent(v): If v is not the root, we use Q[v] and D[v] (both accessed in O(1) time) to reconstruct
the key hv ′ , ci of v, where v ′ is the parent of v and c is the label of v.
getLabel (v): Works in the same way as getParent.
delLeaf (v, c): We create the key hv, ci and search f or it in the CHT as before. When we find
the location v ′ that is the ID of the leaf, we store a “deleted” value that is distinct from any
quotient or from the “unoccupied” value (clearly, if an insertion into the CHT encounters
a “deleted” value during linear probing, this is treated as an empty location and the key is
inserted into it.
We now discuss the time complexity of the operations. If n is the current number of trie
nodes, we ensure that the current value of M satisfies (1 + β/2)n ≤ M ≤ (1 + β)n which means
that ǫ = (M − n)/n varies between (β/2)/(1 + β/2) and β/(1 + β). Under this assumption, the
value of ǫ = (M − n)/M is Θ((1 + β)/β), and the operations addChild , getChild and delLeaf take
O(1/ǫ) = O(1/β) (expected) time. If an addChild causes n to go above M/(1 + β/2), we create
a new hash table with capacity M ′ = (1+3β/4)
(1+β/2) M . We traverse the old tree in O((M + n)/β) time
and copy it to the new hash table. However, at least Omega(βn) addChild operations must have
occurred since last time that the tree was copied to its current hash table, so the amortized cost
of copying is O((1/β)2 ). The case of a delLeaf operation causing n to go below M/(1 + β) is
similar. The space complexity, by the previous discussions, is clearly M (log σ + O(1)) bits. Since
M ≤ (1 + β)n, the result is as claimed.
✷

4

Implementation and experimental evaluation

In this section, we first discuss details of our implementations. Next we describe the implementation
of a naive approach for traversal and the simple linear-time traversal explained in Section 3.4.1. All
13

implementations are in C++ and use some components from the sdsl-lite library [15]. Finally
we describe our machine’s specifications, our datasets, our benchmarks, and the performance of
our implementations in these benchmarks.

4.1

Cleary’s CHT and original Bonsai

We implemented our own version of Cleary’s CHT, which mainly comprises three sdsl containers:
firstly, the int vector<> class, which uses a fixed number of bits for each entry, is used for the Q
array. In addition, we have two instance of the bit vector container to represent the bit-strings
used by [6, 7] to map a key’s initial address to the position in Q that contains its quotient. The
original Bonsai trie is implemented essentially on top of this implementation of the CHT.

4.2

Representation of the displacement array

As noted earlier, the data structure of Lemma 6 appears to be too complex for implementation.
We therefore implemented two practical alternatives, one based on the naive approach outlined in
Lemma 6 and one that is based on Section 3.3.
4.2.1

m-Bonsai (γ)

We now describe m-Bonsai (γ) which is is based on representing the D-array using the naive
approach of Lemma 6. D is split into M/b consecutive blocks of b displacement values each. The
displacement values are stored as a concatenation of their γ-codes. Since γ-codes are only defined
for values > 1, and there will be some zero displacement values, we add 1 to all displacement values.
In contrast to the description in Lemma 6, to perform a get(i), we find the block containing D[i],
decode all the γ-codes in the block up to position i, and return the value. To perform set(i, v), we
decode the block containing i, change the appropriate value and re-encode the entire block.
In our experiments, we choose b = 256. We have an array of pointers to the blocks. We used
sdsl’s encode and decode functions to encode and decode each block for the set and get operations.
4.2.2

m-Bonsai (recursive)

We now discuss the implementation of the alternate representation of the displacement array discussed in Section 3.3, which we call m-Bonsai (recursive). D0 is has equal-length entries of ∆0 -bits
and is implemented as an int vector<>. The second layer is a CHT, implemented as discussed
above. The third layer is implemented using the C++ std::map.
We now discuss the choice of parameters ∆0 and ∆1 . The description in Section 3.3 is clearly
aimed at asymptotic analysis: the threshold θ1 above which values end up in the second or third
layers, for n = 265,536 and α = 0.8, is about 2/9. As a result the values of ∆0 and ∆1 are currently
chosen numerically. Specifically, we compute the probability of a displacement value exceeding k for
load factors α = 0.7, 0.8, and 0.9 using the exact analysis in [21] (however, since we are not aware
of a closed-form formula for this probability, the calculation is done numerically). This numerical
analysis shows, for example, that for α = 0.8, choosing∆0 = 2 or 3 and ∆1 = 6, 7, or8 give roughly
the same expected space usage. Clearly, choosing ∆0 = 3 would give superior performance as more
displacement values would be stored in D0 which is just an array, so we chose ∆0 = 3. Given
this choice, even choosing ∆1 = 7 (which means displacement values ≥ 134 are stored in the third
layer), the probability of a displacement value being stored in the third layer is at most 0.000058.
14

Since storing a value in the stl::map takes 384 bits on a 64-bit machine, the space usage of the
third layer is negligible for a 64-bit machine.

4.3

m-Bonsai traversal

We now discuss the implementation of traversals. As discussed, the difficulty with both Bonsai
data structures is that the getChild and getParent operations only support leaf-to-root traversal.
One approach to traversing a tree with this set of operations is as follows. Suppose that we are
at a node v. For i = 0, . . . , σ − 1, we can perform getChild (v, i) to check if v has a child labelled
i; if a child is found, we recursively traverse this child and its descendants. This approach takes
O(nσ) time.
The algorithm described in Section 3.4.1 was implemented using sdsl containers as follows.
The arrays A and C are implemented as sdsl int-vectors of length M and n respectively, with
width ⌈log σ⌉. The bit-vector was implemented as a select support mcl class over a bit vector
of length M + n.

4.4
4.4.1

Experimental evaluation
Datasets

We use benchmark datasets arising in frequent pattern mining [14], where each “string” is a subset
of a large alphabet (up to tens of thousands). We also used sets of short read genome strings given
in the standard FASTQ format. These datasets have a relatively small alphabet σ = 5. Details of
the datasets can be found in Table 2.
4.4.2

Experimental setup

All the code was compiled using g++ 4.7.3 with optimization level 6. The machine used for the
experimental analysis is an Intel Pentium 64-bit machine with 8GB of main memory and a G6950
CPU clocked at 2.80GHz with 3MB L2 cache, running Ubuntu 12.04.5 LTS Linux. To measure the
resident memory (RES), /proc/self/stat was used. For the speed tests we measured wall clock
time using std::chrono::duration cast.
4.4.3

Tests and results

We now give the results of our experiments, divided into tests on the memory usage, benchmarks
for build, traverse and successful search operations. Our m-Bonsai approaches where compared
with Bonsai and Bentley’s C++ TST implementation [4]. The DAT implementation of [31] was
not tested since it apparently uses 32-bit integers, limiting the maximum trie size to 232 nodes,
which is not a limitation for the Bonsai or TST approaches. The tests of [31] suggest that even
with this “shortcut”, the space usage is only a factor of 3 smaller than TST (albeit it is ∼ 2 times
faster).
Memory usage. We compare the aforementioned data structures in terms of memory usage. For
this experiments we set α = 0.8 for all Bonsai data structures. Then, we insert the strings of each
dataset in the trees and we measure the resident memory. Table 2 shows the space per node (in

15

bits). We note that m-Bonsai (γ) consistently uses the least memory, followed by m-Bonsai (r).
Both m-Bonsai variants used less memory than the original Bonsai.
Since the improvement of m-Bonsai over Bonsai is a reduction in space usage from O(n log σ +
n log log n) to O(n log σ + n), the difference will be greatest when σ is small. This can be observed
in our experimental results, where the difference in space usage between m-Bonsai and the original
Bonsai is greatest when σ is small. In the FASTQ data sets, where original Bonsai uses 85% more
space than m-Bonsai (r) while the advantage is reduced to 23% for webdocs. Of course, all Bonsai
variants are significantly more space-efficient than the TST: on the FASTQ datasets, by a factor
of nearly 60. Indeed, the TST could not even load the larger datasets (FASTQ and webdocs) on
our machine.
Table 2: Characteristics of datasets and memory usage (bits per node) for all data structures. TST
was not able to complete the process for larger datasets.
Datasets
n
σ
m-Bonsai (r) m-Bonsai(γ) Bonsai TST
Chess
38610
75
13.99
11.94
17.51 389.56
Accidents
4242318
442
16.45
14.42
19.99 388.01
Pumsb
1125375
1734
18.95
16.93
22.51 387.52
Retail
1125376
8919
22.71
20.69
26.25 384.91
Webdocs8
63985704
364
16.45
14.44
19.99 386.75
Webdocs
231232676 59717
25.20
23.19
28.72
—
SRR034939
3095560
5
8.94
6.78
12.51 385.88
SRR034944
21005059
5
8.93
6.74
12.51 385.76
SRR034940 1556235309
5
8.93
6.77
12.51
—
SRR034945 1728553810
5
8.93
6.79
12.51
—
Tree construction speed. In Table 3 we show the wall clock time in seconds for the construction
of the tree. Of the three Bonsai implementations, m-Bonsai (r) is always the fastest and beats the
original Bonsai by 25% for the bigger datasets and about 40% for the smaller ones.
We believe m-Bonsai (r) may be faster because Bonsai requires moving elements in Q and one
of the bit-vectors with each insertion. When inserting a node in m-Bonsai (r) each D[i] location
is written to once and D and Q are not rearranged after that. Finally, m-Bonsai (γ) is an order
of magnitude slower than ther other Bonsai variants. It would appear that this is due to the time
required to access and decode concatenated γ-encodings of a block, append the value and then
encode the whole block back with the new value.
Comparing to the TST, m-Bonsai (r) was comparably fast even on small datasets which fit
comfortably into main memory and often faster (e.g. m-Bonsai is 30% faster on webdocs). The
difference appears to be smaller on the FASTQ datasets, which have small alphabets. However,
the TST did not complete loading some of the FASTQ datasets.
Traversal speed. In Table 4 we show compare the simple linear-time and naive traversals, using
m-Bonsai (r) as the underlying Bonsai representation. After we construct the trees for the given
datasets, we traverse and measure the performance of the two approaches in seconds. The simple
linear-time traversal includes both the preparation and the traversal phase. Since the naive traversal
takes O(nσ) time and the simple traversal takes O(n) time, one would expect the difference to be
greater for large σ. For example, Retail is a relatively small dataset with large σ, the difference

16

Table 3: The wall clock time in seconds for the construction of the Trie. TST was not able to
complete the process for larger datasets.
Datasets
Chess
Accidents
Pumsb
Retail
Webdocs8
Webdocs
SRR034939
SRR034944
SRR034940
SRR034945

m-Bonsai (r)
0.02
2.18
0.43
0.22
26.07
96.38
0.61
5.72
730.55
841.87

m-Bonsai(γ)
0.21
21.46
5.85
2.27
252.59
869.22
10.25
70.83
6,192.14
7,199.11

Bonsai
0.08
3.01
0.69
0.25
32.75
130.92
0.79
7.34
970.81
1,106.39

TST
0.02
2.31
0.57
0.31
18.25
—
0.61
4.31
—
—

in speed is nearly two orders of magnitude. Whereas all FASTQ datasets are consistently only 2
times slower.
Surprisingly, even for datasets with small σ like the FASTQ, naive approach does worse than
the simple linear-time approach. This may be because the simple linear-time traversal makes fewer
random memory accesses (approximately 3n) during traversal, while the naive approach makes
nσ = 5n random memory accesses for this datasets. In addition, note that most searches in
the hash table for the naive traversal are unsuccessful searches, which are slower than successful
searches.
Table 4: The wall clock time in seconds for traversing the tree using simple and naive approach.
Datasets
Chess
Accidents
Pumsb
Retail
Webdocs8
Webdocs
SRR034939
SRR034944
SRR034940
SRR034945

Simple traversal
0.02
4.82
1.01
1.04
104.92
150.81
2.61
24.78
3,352.81
4,216.82

Naive traversal
0.38
228.92
233.11
788.36
6,617.39
—
4.52
41.94
7,662.37
8,026.94

Successful search speed. Now we explain the experiment for the runtime speed for successful
search operations. For this experiment we designed our own search-datasets, where we randomly
picked 10% of the strings from each dataset, shown in Table 5. After the tree construction, we
measured the time needed in nanoseconds per successful search operation. It is obvious that
TST is the fastest approach. However, m-Bonsai (recursive) remains competitive with TST and
consistently faster than Bonsai by at least 1.5 times, whereas m-Bonsai (γ) in the slowest. Note
that there is an increase in runtime speed per search operation for all Bonsai data structures as the
datasets get bigger, since there are more cache misses. For TST, we see that Retail with high σ is
affecting the runtime speed, as TST can search for a child of a node in O(log σ) time.
‘

17

Table 5: The wall clock time in nanoseconds per successful search operations.
Datasets
m-Bonsai (r) m-Bonsai(γ) Bonsai TST
Chess
Accidents
Pumsb
Retail
Webdocs8
Webdocs
SRR034939
SRR034944
SRR034940
SRR034945

5

130
187
134
407
296
352
173
247
451
511

1240
1342
1204
1244
1573
1705
1472
1682
1946
1953

288
399
301
418
586
795
350
498
709
718

59
60
55
102
61
—
65
66
—
—

Conclusion

We have demonstrated a new variant of the Bonsai approach to store large tries in a very spaceefficient manner. Not only have we (re)-confirmed that the original Bonsai approach is very fast
and space-efficient on modern architectures, both m-Bonsai variants we propose are significantly
smaller (both asymptotically and in practice) and and one of them is a bit faster than the original
Bonsai. In the near future we intend to investigate other variants, to give a less ad-hoc approach
to m-Bonsai (recursive), and to compare with other trie implementations.
Neither of our approaches is very close to the information-theoretic lower bound of (σ log σ −
(σ − 1) log(σ − 1))n − O(log(kn)) bits [3]. For example, for σ = 5, the lower bound is 3.61n bits,
while m-Bonsai (γ) takes ∼ 5.6M ∼ 7n bits. Closing this gap would be an interesting future
direction. Another interesting open question is to obtain a practical compact dynamic trie that has
a wider range of operations, e.g. being able to navigate directly to the sibling of a node.
Acknowledgements. We thank Gonzalo Navarro for helpful comments and in particular suggesting an asymptotic analysis of the D-array representation used in m-Bonsai (r).

References
[1] Jun-Ichi Aoe. An efficient digital search algorithm by using a double-array structure. IEEE
Trans. Software Eng., 15(9):1066–1077, 1989.
[2] Diego Arroyuelo, Pooya Davoodi, and SrinivasaRao Satti. Succinct dynamic cardinal trees.
Algorithmica, 74:1–36, 2015. Online first.
[3] David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Representing trees of higher degree. Algorithmica, 43(4):275–292, 2005.
[4] Jon
Bentley
and
Bob
Sedgewick.
Ternary
http://www.drdobbs.com/database/ternary-search-trees/184410528, 1998.

18

search

trees.

[5] Larry Carter and Mark N. Wegman. Universal classes of hash functions. J. Comput. Syst.
Sci., 18(2):143–154, 1979.
[6] John G. Cleary. Compact hash tables using bidirectional linear probing. IEEE Trans. Computers, 33(9):828–834, 1984.
[7] John J. Darragh, John G. Cleary, and Ian H. Witten. Bonsai: a compact representation of
trees. Softw., Pract. Exper., 23(3):277–291, 1993.
[8] René de la Briandais. File searching using variable length keys. In Proc. Western J. Computer
Conf., pages 295—-298, 1959.
[9] Martin Dietzfelbinger. On randomness in hash functions (invited talk). In Christoph Dürr
and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer
Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, volume 14 of LIPIcs,
pages 25–28. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012.
[10] Peter Elias. Universal codeword sets and representations of the integers. IEEE Trans. Information Theory, 21(2):194–203, 1975.
[11] Arash Farzan and J. Ian Munro. A uniform paradigm to succinctly encode various families of
trees. Algorithmica, 68(1):16–40, 2014.
[12] Arash Farzan, Rajeev Raman, and S. Srinivasa Rao. Universal succinct representations of
trees? In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas,
and Wolfgang Thomas, editors, Automata, Languages and Programming, 36th International
Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, volume 5555
of Lecture Notes in Computer Science, pages 451–462. Springer, 2009.
[13] Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with 0(1)
worst case access time. J. ACM, 31(3):538–544, 1984.
[14] Bart Goethals. Frequent itemset mining implementations repository. http://fimi.ua.ac.be/.
[15] Simon Gog, Timo Beller, Alistair Moffat, and Matthias Petri. From theory to practice: Plug
and play with succinct data structures. In Experimental Algorithms - 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proceedings, pages 326–337,
2014.
[16] Michael T. Goodrich and Roberto Tamassia. Algorithm Design and Applications. Wiley, 2015.
[17] Roberto Grossi and Giuseppe Ottaviano. The wavelet trie: maintaining an indexed sequence
of strings in compressed space. In PODS, pages 203–214, 2012.
[18] Guy Jacobson. Space-efficient static trees and graphs. In Proc. 30th Annual Symposium on
Foundations of Computer Science, pages 549–554. IEEE Computer Society, 1989.
[19] Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung. CRAM: compressed random access
memory. In Automata, Languages, and Programming - 39th International Colloquium, ICALP
2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in
Computer Science, pages 510–521. Springer, 2012.
19

[20] Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung. Linked dynamic tries with applications to lz-compression in sublinear time and space. Algorithmica, 71(4):969–988, 2015.
[21] Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd
ed.). Addison Wesley Longman, 1998.
[22] J. Ian Munro, Venkatesh Raman, and Adam J. Storm. Representing dynamic binary trees
succinctly. In S. Rao Kosaraju, editor, Proc. 12th Annual Symposium on Discrete Algorithms,
pages 529–536. ACM/SIAM, 2001.
[23] Stefan Nilsson and Matti Tikkanen. An experimental study of compression methods for dynamic tries. Algorithmica, 33(1):19–33, 2002.
[24] Rasmus Pagh. Low redundancy in static dictionaries with constant query time. SIAM J.
Comput., 31(2):353–363, 2001.
[25] Mihai Patrascu. Succincter. In 49th Annual IEEE Symp. Foundations of Computer Science,
pages 305–313. IEEE Computer Society, 2008.
[26] Andreas Poyias, Simon J. Puglisi, and Rajeev Raman. Compact dynamic rewritable (CDRW)
arrays. In Sándor P. Fekete and Vijaya Ramachandran, editors, Proceedings of the Ninteenth
Workshop on Algorithm Engineering and Experiments, ALENEX 2017, Barcelona, Spain, Hotel Porta Fira, January 17-18, 2017., pages 109–119. SIAM, 2017.
[27] Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct dynamic data structures.
In Frank K. H. A. Dehne, Jörg-Rüdiger Sack, and Roberto Tamassia, editors, Algorithms and
Data Structures, 7th International Workshop, WADS 2001, Providence, RI, USA, August 810, 2001, Proceedings, volume 2125 of Lecture Notes in Computer Science, pages 426–437.
Springer, 2001.
[28] Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries
with applications to encoding k -ary trees, prefix sums and multisets. ACM Transactions on
Algorithms, 3(4), 2007.
[29] Rajeev Raman and S. Srinivasa Rao. Succinct dynamic dictionaries and trees. In Jos C. M.
Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata,
Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The
Netherlands, June 30 - July 4, 2003. Proceedings, volume 2719 of Lecture Notes in Computer
Science, pages 357–368. Springer, 2003.
[30] Takuya Takagi, Takashi Uemura, Shunsuke Inenaga, Kunihiko Sadakane, and Hiroki
Arimura.
Applications of succinct dynamic compact tries to some string problems.
http://www-ikn.ist.hokudai.ac.jp/∼arim/papers/waac13takagi.pdf . Presented at WAAC’13.
[31] Naoki Yoshinaga and Masaru Kitsuregawa. A self-adaptive classifier for efficient text-stream
processing. In Jan Hajic and Junichi Tsujii, editors, COLING 2014, 25th International Conference on Computational Linguistics, Proceedings of the Conference: Technical Papers, August
23-29, 2014, Dublin, Ireland, pages 1091–1102. ACL, 2014.

20

