Paper relevant to building spatial index on top of B-tree

[Martin Davis]

http://doesen0.informatik.uni-leipzig.de/proceedings/paper/33.pdf

This paper seems to provide a model for implementing a spatial index
using an existing B-tree access method in an RDB. Maybe it has some
useful information for the H2 spatial project.

Martin

[Thomas Mueller]

Hi,

Thanks for the link! Maybe I have already read this paper, I don't
fully remember. I think there are two solutions:

A) Write a mechanism that uses the regular b-tree index (for example
something like the MultiDimension tool that is included in H2).

B) Implement an R-Tree indexing mechanism. Probably it makes sense to
write a first implementation first outside the database in pure Java
(maybe there are some free implementations available, I didn't check),
and if this is done integrate that into H2.

Some code will have to be written for both scenarios (helper
functions, test cases and so on). Just now, I think we should do both
A) and B) up to some point, and decide later which way to go, for
example based on performance or based on problems found or
implementation complexity.

Regards,
Thomas

[Martin Davis]

On May 5, 11:03 am, "Thomas Mueller" <thomas.tom.muel...@gmail.com>
wrote:

> Hi,
>
> Thanks for the link! Maybe I have already read this paper, I don't
> fully remember.

It seems like the Kriegel et al team have some very clever ideas for
building MD indexes using existing RDB B-trees. Here's a paper by
them that is maybe even more relevant:

http://citeseer.ist.psu.edu/cache/papers/cs/22231/http:zSzzSzwww.dbs.informatik.uni-muenchen.dezSz~seidlzSzpaperszSzSSTD01-Sequences.pdf/interval-sequences-an-object.pdf

> I think there are two solutions:

I agree with your A and B solutions, and I'd be happy to see both of
them implemented and run off against one another 8^)

There's all kinds of Java Rtree impls - just Google for "rtree java".
This one is popular (and its C version being used to add a spatial
index to SQLite by the SpatialLite project):

http://research.att.com/~marioh/spatialindex/index.html

[Martin Davis]

By the way, I am still clinging to my belief that adding an R-tree
index is the cleanest, most performant way of adding spatial index
capabilty to H2 ;^)

But I realize that this will be a non-trivial piece of work
(especially after dipping into the codebase for the existing
index!).

And it would be interesting to see a direct comparison between these
two approaches - if it's possible to find the development cycles to do
both.

On May 5, 11:03 am, "Thomas Mueller" <thomas.tom.muel...@gmail.com>
wrote:

> Hi,
>
> Thanks for the link! Maybe I have already read this paper, I don't
> fully remember. I think there are two solutions:
>
> A) Write a mechanism that uses the regular b-tree index (for example
> something like the MultiDimension tool that is included in H2).
>
> B) Implement an R-Tree indexing mechanism. Probably it makes sense to
> write a first implementation first outside the database in pure Java
> (maybe there are some free implementations available, I didn't check),
> and if this is done integrate that into H2.
>
> Some code will have to be written for both scenarios (helper
> functions, test cases and so on). Just now, I think we should do both
> A) and B) up to some point, and decide later which way to go, for
> example based on performance or based on problems found or
> implementation complexity.
>
> Regards,
> Thomas
>