n-dimensional r-tree opclasses ...

Just a heads up, in case anyone is interested ...

Marc G. Fournier ICQ#7615664 IRC Nick: Scrappy
Systems Administrator @ hub.org
primary: scrappy(at)hub(dot)org secondary: scrappy(at){freebsd|postgresql}.org

---------- Forwarded message ----------
Date: Fri, 19 May 2000 11:56:59 -0700
From: Joe Hellerstein <jmh(at)cs(dot)berkeley(dot)edu>
To: fmaps-devel(at)lists(dot)sourceforge(dot)net, gist(at)db(dot)cs(dot)berkeley(dot)edu, scrappy(at)hub(dot)org
Subject: Re: GiST, PostgreSQL, etc.

PS: Andy Dong's n-dimensional R-tree opclasses are available at
http://best.me.berkeley.edu/~adong/rtree/.

Joe Hellerstein

Joe Hellerstein wrote:

> 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(at)db(dot)cs(dot)berkeley(dot)edu with specific
> questions.
>
> Regards,
>
> Joe Hellerstein
>
> --
>
> Joseph M. Hellerstein
> Associate Professor
> Computer Science Division
> UC Berkeley
> http://www.cs.berkeley.edu/~jmh