[p2p-hackers] Implementing distributed quadtree in Java

[Günter Dannhäuser]

Aaron Harwood wrote:
> Another thing to consider, though it doesn't really help you for a
> pure Java implementation, is that our OPeN library allows Chord to
> be replaced with other protocols, while a p2p distributed directory
> service implementation at the higher layer would remain unchanged.

Sean Rhea wrote:
> Also check out, "A Case Study in Building Layered DHT Applications"
> by Yatin Chawathe et al.:
> 
>    http://www.acm.org/sigs/sigcomm/sigcomm2005/paper-ChaRam.pdf
> 
> The code for this is available from the authors, and it works well  
> from what they tell me.  The performance should be a lot better now,  
> too, as OpenDHT is much faster since they ran their evaluation.

I didn't know that one, thanks for the reference. Though, contrary to
their scenario, we're interested in point-queries on objects with
spatial extent, the ideas of Prefix Hash Trees and
space-filling-curves for indexing could certainly be adapted.

Moreover, using an abstraction layer like the OPeN lib or completely
decoupling deployment and management of the underlying DHT, using e.g.
OpenDHT, is quite appealing - I'm now thinking of evaluating an
iterative variant of the mentioned distributed quadtree algorithm
using the OpenDHT service (someone mentioned improved performance? ;-)


Dominic Heutelbeck wrote:
> However in my early work I tried to use a quadtree like structure [2][3],
> however I found it to be notwell suided to problems where the distribution of 
> hot-spots is as dynamic as when managing objects with mobile spatial locations.

Service-offers and their locations are expected to be not very dynamic
in our case. Load-balancing could become a more limiting problem with
hot-spots, when limiting the depth of the tree becomes necessary,
especially for an iterative solution.


Thanks+cheers,
Günter.