[p2p-hackers] DHT and complex queries

[Sean C. Rhea]

On Jul 4, 2005, at 5:23 AM, Davide Carboni wrote:
> author equal "foo"
> and
> publicationDate is between "12 12 1999" and "12 12 2000"
> andnot
> distributor startswith "galax"

What you need is a range query operation, and yes, you can do that on a 
DHT.  See

   "A Case Study in Building Layered DHT Applications."  Yatin Chawathe,
   Sriram Ramabhadran, Sylvia Ratnasamy, Anthony LaMarca, Joseph
   Hellerstein, Scott Shenker.  SIGCOMM 2005.

and

   "Brief Announcement: Prefix Hash Tree."  Sriram Ramabhadran, Sylvia
   Ratnasamy, Joseph M. Hellerstein, Scott Shenker.  Proceedings of ACM
   PODC, St. Johns, Canada, July 2004.

It takes O(log^2 n) time in a network of n nodes, which is pretty 
efficient compared to a flooding-like search for rare items (or when 
you need to guarantee you find all the matching data).  For non-rare 
items (and where you just want _any_ matching item) flooding works 
fine.

There's an implementation of this out there for OpenDHT (built by the 
above authors), but I don't have the code for it.

There are also other range query algorithms for DHTs.  See the 
citations in the above papers for a starting point.

Sean
-- 
                    Boredom is always counterrevolutionary.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://zgp.org/pipermail/p2p-hackers/attachments/20050704/63ba810a/PGP.pgp