Re:Crit-bit Trees: the best way to store sets
by DanWaterworth on Tuesday September 20, 2011 @12:14AM
(#3016243)
I'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.
[ Parent
| on HN ]
Re:Crit-bit Trees: the best way to store sets
by gsg on Tuesday September 20, 2011 @03:22AM
(#3016675)
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
by DanWaterworth on Tuesday September 20, 2011 @06:36AM
(#3017028)
I know that thanks