4 ms·
Your conclusion is likely correct given your data, but did you happen to evaluate HAT-tries as well? http://crpit.com/confpapers/CRPITV62Askitis.pdf http://crp
by rch 11y ago
Your conclusion is likely correct given your data, but did you happen to evaluate HAT-tries as well?
http://crpit.com/confpapers/CRPITV62Askitis.pdf http://crpit.com/confpapers/CRPITV62Askitis.pdf
- nostrademons 11y agoNope 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