2 ms·
Nope I didn't - I did this work in 2006, and the HAT trie didn't come out until 2007. I did try a number of different variations on how to do the internal stor
by nostrademons 11y ago
Nope I didn't - I did this work in 2006, and the HAT trie didn't come out until 2007. I did try a number of different variations on how to do the internal storage of nodes though - the fastest was what the paper described as a burst-trie - as well as other binary search tree structures. The speed difference was well over 5x though (IIRC, it was something like 17x from best string trie vs. binary search), so if the paper's conclusions hold it probably wouldn't have mattered.
- srean 11y agoYour comment provoked a quick search on pointer-less encoding of tries. It turns out one such implementation was patented in 2006 http://www.google.com/patents/US20060020638 http://www.google.com/patents/US20060020638