Trees, Hash Tables and Tries

Re:Trees, Hash Tables and Tries by jules on Sunday April 04, 2010 @07:17AM (#1240036)

Here's an interesting paper. It describes a cross between a trie and a hash table. Instead of storing the string itself in the trie, it first hashes the string and then stores that in a trie (in a smart way). The memory usage is claimed to be very good, and the benchmarks in the paper seem to show that it's faster than a hash table for lookup...

http://lampwww.epfl.ch/papers/idealhashtrees.pdf

[ Parent | on HN ]

Re:Trees, Hash Tables and Tries by angstrom on Sunday April 04, 2010 @10:18AM (#1240184)

Another good example that can be more performant than a hash or a trie on a given alphabet is a directed acyclic word graph. Think of it as a trie that reuses edges, but has no cycles. This makes it very compact.

There's an implementation of one here that I've messed with, but it's a little expensive on the setup side.

http://www.pathcom.com/~vadco/dawg.html

The final result is that each node is stored in a 32bit word with the possible characters limited to a 5 bit field. 1 bit flag for word endings and I believe he employed offsets with the rest of the bits to perform the directed lookups of the other characters in a limited A-Z uppercase only alphabet. These types of graphs tend to extremely fast at runtime, but like I mentioned, the setup is costly. However, if you were embedding this in a device this would definitely be a worthwhile investigation. This is one of those cases where a data structure fits a very constrained, but well defined requirement.

[ Parent | on HN ]

Re:Trees, Hash Tables and Tries by jules on Sunday April 04, 2010 @11:06AM (#1240251)

Interesting. How much space saving do you see? DAWGs work for sets, but can it work for key-value maps? (I don't see how, because a final leaf can belong to multiple key prefixes, and therefore multiple associated values).

[ Parent | on HN ]

Re:Trees, Hash Tables and Tries by AlisdairO on Sunday April 04, 2010 @09:35AM (#1240137)

Thanks for the link! I'll be interested to take a look.

[ Parent | on HN ]