From: MikkelFJ <mikkelfj-anti-spam@...>
Date: 2002-08-26T00:21:50+09:00
Subject: Re: Ruby and Judy

> This (Judy in general) is a very interesting concept to
> me, partly because I find it hard to imagine this kind
> of thing coded with the kind of efficiency we seem to
> talking about, and yet presumably in a platform-independent
> manner.
>
> I'm not knocking it, I'm just surprised that Judy exists.

I have been working with some similar concept using B-Trees:
Having an efficient in-memory tree with a reduced level of branching
compared to typically page sized trees does work quite efficiently. However,
you have to have very large hash tables before the B-tree it outperforms a
hashed 32 bit key.

I implented a variant called I-Tree  (I later learned they are also know as
ordered B-Trees or OB-trees). An I-Tree uses the size of the sub-tree for
indexing. At leaf level there is no key. Hence a space efficient dynamic
array.

I was actually considering making Ruby running on this indexing principle,
but also realize it is a lot of work.

I need to study Judy more, but it seems like it used a trie where I use
B-tree keys. I'm worried the Judy may consume too much memory on some cases
(especially smaller trees) which is why I chose B-Tree keys instead of using
a trie lookup. If Judy does handle this efficiently it's interesting. I
noticed the use of "widening" also know as path compression. I've also been
working with this in relation to statically indexed trees, but it is not
good for dynamic behavior. Jucy seem to have abanded the use of key
widening. The cost for not widening the key is more levels in the tree.

The I-Tree is very space efficient. The B-Tree requires a key for each entry
which effectively becomes 64 bit per entry and the inherent space overhead
in B-Trees for not fully using all nodes.

The downside of in-memory B-Trees is that entries must be moved during
insertion into node. It is generally faster to do linear scan than using
binary search of node up to a certain size (which is too large due to cache
considerations).

Ordinary Red-black trees (STL map) are not very space efficient. But for
small collections they are fast and has little additional overhead.

Also note the 3-Trie posted in DDJ a few years back. I implemented a variant
using multi-level B-Trees. It branches on 32bit (or 64) bits instead of
Judy's 8 bit. I haven't measured it but I expect it to be a very efficient
suffix tree string indexing method. I store runs of strings to avoid
excessive number of sub-trees.

Mikkel