n-dimensional r-tree opclasses ...

Hi folks:
Tim Keitt contacted my group and brought your open source GIS
project to our attention. Sounds great.

A couple of notes that may be of use:

- PostgreSQL ships with GiST as a built-in access method, though I
doubt anybody has tested it much. I wrote that code, and with the help
of Marc Fournier got it patched into the PostgreSQL release. As
somebody mentioned, at http://gist.cs.berkeley.edu/pggist/ you can
download code for various initial prototype GiST "functions" (as in
"create function"), as well as DDL scripts. To be honest, this was the
very first attempt at delivering a GiST implementation, and it's not
wonderfully pretty. I don't think any PostgreSQL users have exercised
it either, because it's kind of exotic to try out new index types. I
also haven't tested the latest versions of PostgreSQL to see if this
stuff still works with it.

- Yes, R-trees generalize trivially to >2 dimensions. Andy Dong, a
student in my grad DB class some years ago, wrote "opclass" code for
Illustra (commercial version of postgres available from Informix) that
extended its R-trees to multiple dimensions. "Back-porting" these
opclasses to Postgres should be pretty easy. This is my recommendation
to you as the simplest -- if not the highest-performance -- way to go
for your project.

- My students did a much more involved standalone C++ implementation
called libgist, which is available at
http://gist.cs.berkeley.edu/libgist-2.0/index.html. This does not
integrate with PostgreSQL -- it's a standalone gist library that runs
over a file system, and can be linked into applications. It includes
many new features though, including better interfaces, support for
near-neighbor searches, as well as more efficient variants of R-trees
(e.g. R*-trees, and better variants) that generalize to however many
dimensions you want. It also comes with a powerful, graphical index
tuning tool called amdb.

- None of us here have the bandwidth to follow your discussion list,
and we do not support the PostgreSQL gist implementation. I'm willing to
answer general design questions about it, but since I haven't touched
the code in about 4 years, I won't be able to help with bugs.

- We do support libgist and amdb.

- We've done a bunch of research on indexing multiple dimensions.
Please see http://gist.cs.berkeley.edu for papers, discussion, the
freeware, etc. Please email gist@db.cs.berkeley.edu with specific
questions.

Regards,

Joe Hellerstein

--

Joseph M. Hellerstein
Associate Professor
Computer Science Division
UC Berkeley
http://www.cs.berkeley.edu/~jmh