Distributed Space Partitioning Trees (was: Re: [p2p-hackers] Implementing distributed quadtree in Java)

[Dominic Heutelbeck]

Hello.

Günter Dannhäuser schrieb:
> IŽm looking into what could be summarized as "Geographic service
> discovery".
> The idea is to use a p2p distributed directory to register and look up
> services which provide information about spatial regions.

This is pretty exactly the topic I recently addressed in my PhD thesis [1] :-)

In my thesis I use something more resemling CAN than an quadtree (however, it is 
significantly different from CAN).

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.

In my thesis I describe a new general use P2P data structure similar to DHTs, 
the so-called distributed space partitioning trees (DSPTs).

The difference to DHTs is basically that instead of publishing (key,value) 
tuples you publish (location, object) tuples. Where the location can be an 
(almost) arbitrary subset of the n-dimensional search space.
You can also update the locations (e.g., modeling mobile entities).
Instead of supporting exact matches or simple range queries, the DSPT supports
geometrical queries, e.g., "return all objects whose location itersect area A", 
where A can again be an (almost) arbitrary subset of the search space.

 > For efficient search, spatial information is hierarchically organized
 > in a virtual, distributed quadtree/octree.
 > This was already done in [1][2][3] and implemented based on the Open
 > Peer-to-peer Network (C-) library OPeN [4] using the Chord protocol.

Thanks for these references. I didn't know them so far.

 > Since this is part of a bigger project using Java, I'm now looking for
 > suitable Java-P2P-middleware to base the implementation on.

While I do have a Java prototype of my protocols, I would not consider it
sable enough for general release.

 > Any suggestions or recommendations would be very welcome, especially
 > opinions on using Bamboo or JXTA (Accord?, JDHT?) for this.
 >

Anyway,  I would like to use the opportunity to present my work here on the 
mailinglist. If anybody of you would like to discuss this topic or DSPTs please 
go ahead. :-)

Regards,
Dominic

[1] Dominic Heutelbeck (2005): PhD thesis Distributed Space Partitioning Trees 
and their Application in Mobile Computing. - Informatik Bericht 327 der 
Fernuniversität Hagen, Hagen, Germany.
http://www.informatik.fernuni-hagen.de/ia/de/staff/heutelbeck/heutelbeck05thesis.pdf

[2] Dominic Heutelbeck, Reinhold Räth, Claus Unger (2003): Fault Tolerant 
Geographical Addressing. In: Proc. of Innovative Internet Community Systems 2003 
(I2CS'03), Leipzig, Germany.
http://www.informatik.fernuni-hagen.de/ia/de/staff/heutelbeck/heutelbeck03fault_tolerant.pdf

[3] Dominic Heutelbeck (2002): Context Spaces - Self-Structuring Distributed 
Networks for Contextual Messaging and Resource Discovery. In: Proc. of Tenth 
International Conference on Cooperative Information Systems 2002 (CoopIS'02), 
University of California Irvine, USA.
http://www.informatik.fernuni-hagen.de/ia/de/staff/heutelbeck/heutelbeck02context.pdf

-- 
---------------------------------------------------------------------------
FernUniversität Hagen    Phone: +49-2331-987-2923
Dominic Heutelbeck       Fax:   +49-2331-987-4487
Universitätsstrasse 1    Email: Dominic.Heutelbeck at fernuni-hagen.de
D-58097 Hagen, Germany   Web:   http://www.informatik.fernuni-hagen.de/ia/
---------------------------------------------------------------------------