Also known as a radix tree, I believe.
Years ago we used this at Singshot to evenly distribute numerical assets across subdirectories. Very useful these days for shardy cloudbucket applications.
Crit-bit Trees: the best way to store sets
11–20 of 42 posts
Re: Crit-bit Trees: the best way to store sets
#12Also known as a radix tree, I believe.
[deleted]
Re: Crit-bit Trees: the best way to store sets
#13> A crit-bit tree for a nonempty prefix-free set S of bit strings has an external node for each string in S; an internal node for each bit string x such that x0 and x1 are prefixes of strings in S; and ancestors defined by prefixes. And that's a perfect (missing) example for "a picture is worth a thousand words". Then again... this coming from DJB - I should be surprised the description is as verbose as it is.
Yeah, I gotta say, I knew exactly how it worked the moment I looked at the radix tree picture on wikipedia. After reading more than half the linked article though I still had very little understanding of what it really did.
Re: Crit-bit Trees: the best way to store sets
#14> A crit-bit tree for a nonempty prefix-free set S of bit strings has an external node for each string in S; an internal node for each bit string x such that x0 and x1 are prefixes of strings in S; and ancestors defined by prefixes. And that's a perfect (missing) example for "a picture is worth a thousand words". Then again... this coming from DJB - I should be surprised the description is as verbose as it is.
The particular words you've quoted have managed to condense a thousand pictures — an infinite number, really — into 45 words. It's kind of a counterexample.
Some examples would certainly help, and probably diagrams would help understanding the examples.
Re: Crit-bit Trees: the best way to store sets
#15I'm not sure it's the best way to store sets. It's seems like potentially doing a pointer dereference per bit is quite an overhead. It would be 8 times faster (for dense sets) to have a crit-byte tree. Though then obviously if you did that naively, there would be a huge associated storage cost. To mitigate that, you can do what AMTs do and have a bitmap per node followed by an array of pointers.
Re: Crit-bit Trees: the best way to store sets
#16> Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data.
Consider a crit-bit tree over variable-length bit strings. The set 1, 11, 111, ... (with n bit strings) has depth n.
Depending on how you count, it can be argued that this is still substantially better than the worst-case of hash tables, but in all of the ways I think of counting, a crit-bit tree is worse on this input than a balanced search tree.
Re: Crit-bit Trees: the best way to store sets
#17> Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data. Consider a crit-bit tree over variable-length bit strings. The set 1, 11, 111, ... (with n bit strings) has depth n. Depending on how you count, it can be argued that this is still substantially better than the worst-case of hash tables, but in all of the ways I think of count…
Isn't the set supposed to be prefix-free, though?
Re: Crit-bit Trees: the best way to store sets
#18Also known as a radix tree, I believe.
Crit-bit trees are not radix trees.
A crit-bit tree stores next-different-bit positions at branches and entire values at the leaves, and is searched by following branches depending on the value of the relevant bit in the search key (the "critical bit" which gives the data structure its name). Once a leaf is reached the entire search key is compared to the value at the leaf, which is necessary because a key that is not in the tree might differ at bit positions that are non-critical and would not have been tested during the tree descent.
This is a very different arrangement to a radix tree, which is essentially a form of trie.
Re: Crit-bit Trees: the best way to store sets
#19I'm not sure it's the best way to store sets. It's seems like potentially doing a pointer dereference per bit is quite an overhead. It would be 8 times faster (for dense sets) to have a crit-byte tree. Though then obviously if you did that naively, there would be a huge associated storage cost. To mitigate that, you can do what AMTs do and have a bitmap per node followed by an array of pointers.
Crit-bit trees don't branch per bit, they branch per differing bit. Much more efficient for most data sets.
Re: Crit-bit Trees: the best way to store sets
#20> Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data. Consider a crit-bit tree over variable-length bit strings. The set 1, 11, 111, ... (with n bit strings) has depth n. Depending on how you count, it can be argued that this is still substantially better than the worst-case of hash tables, but in all of the ways I think of count…
Isn't the set supposed to be prefix-free, though?
Yes but you can do the same example with 0, 10, 110, 1110, ...