[p2p-hackers] DHT and complex queries

[Jacek Sieka]

http://www.eecs.harvard.edu/~mema/courses/cs264/papers/mercury-sigcomm2004.pdf

Suggests a statistic sampling based approach to support load balancing and range & multi-attribute queries, you might find that interesting source of inspiration as well.

Regards /Jacek


Sean C. Rhea wrote:
> 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
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> 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