Spatial indexing in mnesia
Thu Jan 4 10:18:42 CET 2001
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
>> 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
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
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
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
More information about the erlang-questions