[p2p-hackers] DHT and complex queries

[cefn.hoile at bt.com]

Davide,

Where you are using an 'equals' condition, then a DHT is a reasonable
tool to use to find data. 

It's likely to be more efficient than an alternative, since you can take
advantage of the DHT to limit the propagation of the query to only a
limited subset of participating peers, (the ones you know are likely to
have matching data, or links to others who have matching data).

It is much harder to make search efficient if you cannot make any
assumptions about the type of query, since each query may to be
evaluated across all peer data (even if super-peers help to pre-index
and concentrate this querying load  to limit network traffic).

In DHT-like technologies where you can select the metric space in which
identities are embedded (and hence the space in which the neighbourhood
and successor lists are embedded), then it is in  principle possible to
retrieve data efficiently using a bounded query of the kind you use in
your example.

However, most systems deliberately distribute data as uniformly as
possible in order to achive the load-balancing characteristics, so
rarely is this kind of information preserved in the identities used in
the DHT space, and successors will rarely be successors in a
semantically meaningful way (like also being successors in time series
data).

We designed flexibility about the nature of the metric space employed
into some of our distributed lookup algorithms, in order to allow this
kind of bounded query in principle, but we have not used it in anger. 

Perhaps others looking into DHTs have exploited this further, for
example where they achieve favourable load-balancing characteristics in
other ways.

Cefn
http://cefn.com


-----Original Message-----
From: p2p-hackers-bounces at zgp.org [mailto:p2p-hackers-bounces at zgp.org]
On Behalf Of Davide Carboni
Sent: 04 July 2005 13:24
To: Peer-to-peer development.
Subject: [p2p-hackers] DHT and complex queries


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