Quantcast

hilbert rtree

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

hilbert rtree

mbedward
Hi folks,

I wonder if anyone here has played with Hilbert RTrees ?

After a recent exchange on the Geotools users' list I became
interested in the topic and have been reading some recent papers on
efficient calculation of Hilbert indices and handling non-square
areas.  As a learning exercise (and avoidance behaviour from other
work that I should be doing) I'm writing some code to implement such a
Hilbert tree.

I'd be interested to know if anyone has compared the performance of
Hilbert trees with, say, the STRtree and Quadtree classes in JTS.

In the event that any of my code is useful I'll be happy to contribute it.

Michael
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: hilbert rtree

Rory Plaire
Hi Michael,
 
I don't have a great deal of experience with various R-Trees, and the main reason for this is the paper on STR R-Trees which shows that they outperform Hilbert trees by a small but significant margin on a variety of spatial datasets. (http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970016975_1997026099.pdf) After reading this, I just didn't have interest in them anymore. In my experience, I've never really seen a Hilbert R-Tree, and I just assumed that STR trees were the state of the art, and reading the paper cemented this concept.
 
I would be interested in revisiting this, if my assumptions are wrong...
 
-rory

On Mon, Dec 15, 2008 at 8:48 PM, Michael Bedward <[hidden email]> wrote:
Hi folks,

I wonder if anyone here has played with Hilbert RTrees ?

After a recent exchange on the Geotools users' list I became
interested in the topic and have been reading some recent papers on
efficient calculation of Hilbert indices and handling non-square
areas.  As a learning exercise (and avoidance behaviour from other
work that I should be doing) I'm writing some code to implement such a
Hilbert tree.

I'd be interested to know if anyone has compared the performance of
Hilbert trees with, say, the STRtree and Quadtree classes in JTS.

In the event that any of my code is useful I'll be happy to contribute it.

Michael
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel


_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: hilbert rtree

mbedward
Many thanks for the paper Rory.

On first skim it looks very interesting and I'll enjoy studying it further.

cheers
Michael

2008/12/16 Rory Plaire <[hidden email]>:

> Hi Michael,
>
> I don't have a great deal of experience with various R-Trees, and the main
> reason for this is the paper on STR R-Trees which shows that they outperform
> Hilbert trees by a small but significant margin on a variety of spatial
> datasets.
> (http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970016975_1997026099.pdf)
> After reading this, I just didn't have interest in them anymore. In my
> experience, I've never really seen a Hilbert R-Tree, and I just assumed that
> STR trees were the state of the art, and reading the paper cemented this
> concept.
>
> I would be interested in revisiting this, if my assumptions are wrong...
>
> -rory
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: hilbert rtree

mbedward
PS. one recent paper worth looking at is:

Chris H. Hamilton, Andrew Rau-Chaplin (2008) Compact Hilbert indices:
Space-filling curves for domains
with unequal side lengths. Information Processing Letters 105: 155–163.

I have a PDF that I can send off-list if anyone is interested.

Michael

2008/12/16 Michael Bedward <[hidden email]>:
> Many thanks for the paper Rory.
>
> On first skim it looks very interesting and I'll enjoy studying it further.
>
> cheers
> Michael
>

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: hilbert rtree

Tuure Laurinolli
In reply to this post by Rory Plaire
Rory Plaire wrote:
> I don't have a great deal of experience with various R-Trees, and the main
> reason for this is the paper on STR R-Trees which shows that they outperform
<snip>
> experience, I've never really seen a Hilbert R-Tree, and I just assumed that
> STR trees were the state of the art, and reading the paper cemented this
> concept.

STR trees are very simple to implement, and produce rather good indexes.
I read through the R-tree literature sometime around two years ago, and
ended up implementing an STR tree because of its simplicity and expected
performance.

The state of the art in R-Trees however is (and was back when I read up
on the subject) the Priority R-Tree (PR tree), which is supposedly
practical and worst-case optimal. I was enticed away from it by the
near-trivial simplicity of STR.

There is a recent Java implementation available of in-memory PRTree at
http://khelekore.org/prtree/. It would be interesting to see how it
compares with the STR tree currently in JTS in terms of performance.
Alas I don't seem to have the time to actually do any tests on them -
perhaps someone else does?

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...