Spatial indexing in mnesia

[Ulf Wiger]

On Wed, 3 Jan 2001, David Gould wrote:

>On Wed, Jan 03, 2001 at 06:44:40PM -0500, Shawn Pearce wrote:
>> Has anyone ever considered storing spatial data in mnesia?  It requires
>> creating a different style of indexing than dets must use for lookup of
>> records....
>> 
>> Oracle implements their spatial indexes as an auxiliary table that
>> stores each node of the spatial index tree as a row in the table.  This
>> table is then indexed using traditional b*-tree indexes for performance.
>
>Informix and Illustra before it, and Postgresql before that (and I
>think maybe also DB2) do this using multidimensional indexes,
>usually based on R-trees.

I wrote a user contrib called gridfile-1.0 which could handle spatial
data. I'm pretty sure that noone's been using it, because I've found
out that it doesn't work. /-: I'm working on a new version, which
hopefully will both be correct and have better scalability.

The idea was taken from the article "The Grid File: An Adaptable,
Symmetric Multikey File Structure", by L. Nievergelt, H. Hinterberger,
published in "Readings in Database Systems", 2nd Ed, pp 108-24.

The really nice property was that you could do range matching in time
proportional to the number of objects found -- not to the size of the
table.

The main reason why I failed to make it work, of course, was hybris.
Being warped on Erlang, I naturally wanted it to be able to operate on
any type of key (not just integers, as in the article). This makes
splitting and merging more of a challenge. I also wanted to support
walking the grid in any dimension, with perfectly well defined
semantics (user-configurable, naturally). This proved rather
complicated.

If somebody else is really interested, I could finish my new version.
I could also try to make rdbms support derived indeces (difficult, due
to problems with atomicity in trigger actions, but I have at least an
approach to tackle that - still, hacking mnesia might be the better
option.)

/Uffe
-- 
Ulf Wiger                                    tfn: +46  8 719 81 95
Senior System Architect                      mob: +46 70 519 81 95
Strategic Product & System Management    ATM Multiservice Networks
Data Backbone & Optical Services Division      Ericsson Telecom AB