n-dimensional r-tree opclasses ... - Mailing list pgsql-hackers

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

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

---------- Forwarded message ----------
Date: Fri, 19 May 2000 11:56:59 -0700
From: Joe Hellerstein <jmh@cs.berkeley.edu>
To: fmaps-devel@lists.sourceforge.net, gist@db.cs.berkeley.edu, scrappy@hub.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@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