From: Douglas Baskins <dougbaskins@...>
Date: 2002-08-27T06:04:38+09:00
Subject: Re: Ruby and Judy

> Judy looks cool: http://www.sourcejudy.com/ docs at:
> http://www.sourcejudy.com/application/

Group:        I should of called JudySL something else.  

Judy1 and JudyL is ONE technology (word [32/64 bits] keys) and JudySL
(null terminated string keys - NTSK) is ANOTHER.  I get confused about
which people are talking about in these discussions.

Lately, JudySL seems to be the popular one people are interested in.
Perhaps, I should spend some time tuning it.  I admit that its
performance could be improved for short strings (an ascii word v.s a
sentence).

About 99% of my design effort was spent on Judy1/L.  Hashing was about
the only known technology that performed well in this problem space.
However, hashing has scalability problems, is machine dependent (hash
algorithms), does not sort, and has numerous pitfalls that everybody
seems to fall into sooner or later (when the data changes).  I designed
Judy1/L to be as near a complete solution as I could think of.

JudySL is an APPLICATION that uses JudyL.  It demonstrates how
scalability can be used to "think outside the box" -- to overuse an old
cliche.  At least that's how the experiment started.  When we tested the
performance of JudySL, it measured very memory efficient and only
hashing was able to beat its speed -- sometimes.  JudySL does not have
scalability problems and seems to sort at a remarkable speeds (USA
telephone book in a minute or two).

Actually, I considered the state of the art for storing and retrieving
NTSK fairly mature and it should be, considering how easy it is to do.
JudySL was just an accident -- nobody would begin a design with that
approach.  <See www.sourcejudy.com/application/judysl.pdf>

I wrote a program (actually borrowed) to compare JudySL with its
competition, called SLcompare.c.  See <www.sourcejudy.com/benchmarks/>.

Please welcome/challenge/invite anybody to to add a faster/cheaper
method than the 4 included in this program.  (Also I will be updating 
it to output more detailed data soon -- to begin investigating JudySL
with short strings and/or at small populations).

Doug Baskins <doug@sourcejudy.com>