Lambda the Ultimate

Hey, while tutoring a student for a University of Toronto course, I was linked to a paper on Burst Tries. (A mirror is available here)

They're basically the same as tries except that they use containers to store keys/values before creating branches. When the containers are full, they "burst" and are turned into branches. The point of this is that a more efficient data structure for small sets of keys/values can be used in the container, making it faster than a traditional trie.

The paper is by Steffen Heinz, Justin Zobel, and Hugh E. Williams of RMIT University (Australian university it looks like). They have included benchmarks in the paper along with descriptions of alternatives (binary trees, splay trees, hash tables) with the burst trie being discussed beginning at page 5. The benchmarks/experiments are page 13 and on.