[core-dev] Re: [codepatch] PATRICIA

Ardverk will be a GPS management tool with some features known from  
GIS applications. It is not related to P2P.

cu
  Roger


On May 8, 2005, at 2:41 AM, [email protected] wrote:

> 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