Trees, Hash Tables and Tries
benlynn.blogspot.com
Trees, Hash Tables and Tries
1–10 of 24 posts
Re: Trees, Hash Tables and Tries
#2I have also been getting into tries recently (last 6 months) and if you are interested in learning about them I recommend Sedgewick's Algorithms in C (parts 1-4) for a good introduction to the subject. Available on Safari if you have access to that.
Re: Trees, Hash Tables and Tries
#3I will argue that a properly implemented tries are more compact but not necessarily faster than hash table. The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption. Also, I'd like to point out the actually trie implementation may not have a fix k child node. I most often use k = 256 or 512 for the first few layers and 4~8 for the last few one in order to get "hash table" like performance for the first few layers and "tree" like performance for a deeper lookup.
Re: Trees, Hash Tables and Tries
#4In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve moving from node to node, each of which will require an unpredictable retrieval from non-sequential memory. Memory latency is pretty high these days (~200 cycles), so hash tables will almost always be quicker.
This is not to say that radix tries aren't extremely useful - they're compact and fast - but they're unlikely to match a hash table for raw performance.
Re: Trees, Hash Tables and Tries
#5In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve moving from node to node, each of which will require an unpredictable retrieval from non-sequential memory. Memory latency is pretty high these days (~200 cycles), so hash tables will almost always be quicker. This is not to say that radix tries aren't extremel…
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...
Re: Trees, Hash Tables and Tries
#6I will argue that a properly implemented tries are more compact but not necessarily faster than hash table. The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption. Also, I'd like to point out the actually trie implementation may not have a fix k child node. I most often use k = 256 or 512 for the first few layers and 4~8 for the last few one in order to get…
I will argue that a properly implemented tries are more compact but not necessarily faster than hash table.
Where do you argue this?
The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption.
Any data structure can be badly implemented. What use is comparing a badly implemented data structure to a well-implemented one?
Re: Trees, Hash Tables and Tries
#7In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve moving from node to node, each of which will require an unpredictable retrieval from non-sequential memory. Memory latency is pretty high these days (~200 cycles), so hash tables will almost always be quicker. This is not to say that radix tries aren't extremel…
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
Thanks for the link! I'll be interested to take a look.
Re: Trees, Hash Tables and Tries
#8In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve moving from node to node, each of which will require an unpredictable retrieval from non-sequential memory. Memory latency is pretty high these days (~200 cycles), so hash tables will almost always be quicker. This is not to say that radix tries aren't extremel…
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
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.
Re: Trees, Hash Tables and Tries
#9Earlier quoted context omitted.
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
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 wor…
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).
Re: Trees, Hash Tables and Tries
#10In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve moving from node to node, each of which will require an unpredictable retrieval from non-sequential memory. Memory latency is pretty high these days (~200 cycles), so hash tables will almost always be quicker. This is not to say that radix tries aren't extremel…
I've done a bit of work with tries and hash functions and found that in-memory tries are almost universally faster than in-memory hashes, no matter how good the hash function is.
The difference though is on average around 20-30% faster if both implementations are well optimized. But they come with lots of downsides that need to managed well, tries explode into memory very quickly requiring all kinds of memory optimizations to the naive tries to keep the tree depth short (usually with a small hash on the leaves). I remember building an in-memory trie library once in Perl that outperformed a native C hash library by 70%. The development team's jaws dropped when my code was running, they were insisting it wasn't actually doing anything at all and I was faking the output. "There is no way Perl code can outperform our C." It was an interesting learning experience all around. Suffix trees likewise are insane for full text searching.
Hashes on the other hand have a few benefits, they are more compact in memory, on average have fast lookups (though if you try and constrain the hash table growth algorithm too much the can spend a lot of time on both collisions and on table growth operations) and have many many more high quality implementations in most standard libraries, including many very good and very fast on-disk hashes that only consume another few percentage points (single digits usually) off of speed.
The problem with tries is not that they are fast, there really isn't anything faster (in memory) that I'm aware of for lookup and retrieval problems. But tries are like sports cars, really fast, but lots of downsides. Hashes are like an upper end practical family car.
If you try and put the trie on disk, you end up with all sorts of problems that you don't really see in modern on-disk hash implementations. Coming off of disk, hashes tend to be the better option (in fact many of the on-disk trie interfaces I've seen actually just use hashes for the on-disk portion and optimize for tree depth in memory to keep things small).
So it depends, if the set of things you want to use for lookups is relatively small and you can cram it all into memory in a raw trie, it'll be a bit faster. If the set is big, and you want to use it off of disk, go with a hash.
Also, if the values you wish to store don't map well to a trie, like floating point numbers, you pretty much have to go with a hash. Fortunately, the hash function in that case is really easy ;)