Burst Tries paper

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.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


This may be a very nice paper, but I can't see why it's appropriate for LtU... Do you see some connection?

Perhaps as a suggested

Perhaps as a suggested representation for various lookup tables? In practice, most lookups get compiled away, even in dynamic languages (thank you, Self)...

I too don't see the

I too don't see the connection to LtU. But thanks for the link anyway.