[core-dev] Re: [codepatch] PATRICIA

What is ardverk going to be?

Thanks
-greg
Quoting Roger Kapsi <[email protected]>:
> Thanks for the link and Gaston Gonnet for "Figure 4". Prefix
> searching is significantly faster now (altogether about 20% compared
> to a standard Trie).
>
> Well, to prevent confusion. PAT Tree and PATRICIA Trie (and sometimes
> also called Radix Tree) are all the same. PATRICIA was discovered by
> D. R. Morrision.
>
> Gonnet is using the entire String as a whole to build the PAT Trie by
> storing only the starting position of a word rather than splitting
> the String into separate words and storing the words in the Nodes.
> The idea for regex searching seems to be very interesting and has
> maybe potential in LimeWire; PAT Arrays seem to be his invention!?
>
> Hmm, the idea to store only the indices rather than the actual
> objects in the Nodes is also supported by my implementation. Only a
> slightly different KeyCreator model is needed and you could store for
> example pointers to a file rather than loading all records from a
> file into the Trie. Abstracted through ByteBuffers + Memory Mapped I/
> O and you have a nice DB. :)
>
> Anyway, should I continue posting PATRICIA stuff here or is it too
> off-topic? I wrote it originally for my small sideproject
> (ardverk.com) where I need auto-completion functionality on a much
> larger set keys (>800k).
>
> Cheers
>   Roger
>
>
>
> On May 7, 2005, at 1:55 AM, [email protected] wrote:
>
> > That's interesting because I always asked Chris Rohrs who built the
> > Tries the
> > difference between them and PATRICIA trees.  I used those back
> > pre-1990 at the
> > Center for the new Oxford English Dictionary with SGML.  Only
> > relevant ref to
> > this work I found was this:
> > http://citeseer.ist.psu.edu/gonnet91lexicographical.html
> >
> > Gaston Gonnet built Pat as well as Maple (I believe).
> >
> > Thanks
> > -greg
> >
> > Quoting Roger Kapsi <[email protected]>:
> >
> >> Hi all,
> >>
> >> I have something for you here. I dunno if it is of any use for you
> >> but here we go...
> >>
> >> PATRICIA is an acronym for "Practical Algorithm To Retrieve
> >> Information Coded In Alphanumeric". It is essentially a Digital
> >> Search Tree without the flaws of standard Tries, namely the one-way
> >> branching. More info can be found in the JavaDoc!
> >>
> >> Prefix searching is only slightly faster than LimeWire's current Trie
> >> but iterating over all values is more than twice as fast and it needs
> >> about 40% less memory than the current Trie! The actual highlight is
> >> the remove operator b/c it is somewhat tricky (I believe people who
> >> know how it works try to keep it for them self but I'm breaking with
> >> this tradition :)).
> >>
> >> Besides the ability to search for strings and prefixes there are
> >> other very interesting aspects of the PATRICIA Trie. Google a bit for
> >> Patricia, Route Table, Radix Tree...
> >>
> >> cu
> >>   Roger
> >>
> >>
> >>
> >
> >
> >
> >
>
>



_______________________________________________
core-dev mailing list
[email protected]
http://www.limewire.org/mailman/listinfo/core-dev