[p2p-hackers] DHT and complex queries

[Ian Clarke]

You should take a look at FASD:

    http://freenet.sourceforge.net/kronfol_final_thesis.pdf

It uses a generalisation of Freenet's search algorithm to support  
"fuzzy" searching (in the case of FASD, using a series of keywords).

Essentially, any query where you can determine, for a given key,  
whether one key is a closer match to the query than another key, or  
whether it is equally matched, can be searched for.

So, for example, if the query is 'key is equal to numeric value 5',  
then the key '6' would be a closer match than the key '8'.

If the query is 'key is equal to string value "hello"', then the key  
'heppo' would be a closer match than the key 'fdfdf' (perhaps using  
the Levenshtein distance algorithm).

Of course, keys can be anything, not just integers and strings.  For  
example, a single key could be a set of key-value tuples (apologies  
for the overloaded use of 'key').  You can also combine queries using  
boolean operators to form new queries, provided you maintain a way to  
evaluate the relative closeness of two keys to the query.

The FASD paper doesn't really go into these more complex queries, but  
it does demonstrate that Freenet's search algorithm generalises well,  
while maintaining its small-world scalability characteristics.

Ian.

On 4 Jul 2005, at 05:23, Davide Carboni wrote:

> Hi, I'm developing a P2P system where clients must be able to send
> complex queries such as:
>
> author equal "foo"
> and
> publicationDate is between "12 12 1999" and "12 12 2000"
> andnot
> distributor startswith "galax"
>
> etc. etc.
>
> I'm reading some papers about DHT and I wonder whether or not DHT is a
> viable solution for these requirements. I know that with DHT you can
> map a key onto a piece of data, but I cannot see how to manage complex
> query like the one in the example. Probably DHT is not the "good"
> solution for this...but never know,
>
> Any hints?
> Bye.
> Davide
>
>
> -- 
> I have made this letter longer than usual because I lack the time to
> make it shorter.
> B. Pascal
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers at zgp.org
> http://zgp.org/mailman/listinfo/p2p-hackers
> _______________________________________________
> Here is a web page listing P2P Conferences:
> http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
>
>