Spatial Indexes in mnesia

[Joachim Durchholz]

You can fake spatial indexes via "bit interleaving". Assuming four-bit 
X, Y, and Z coordinates XXXX, YYYY, and ZZZZ, construct a bit vector 
XYZXYZXYZXYZ. When traversing the records in the order imposed by that 
index, you'll retrieve them in the order that you'd visit them if they 
were stored in an octree.
For example, if you have the interleaved coordinates 00101xxxxxxx (where 
the "x" indicate don't-care bits), this will give the XYZ coordinates 
(00xx,01xx,1xxx), which is exactly the area that a specific octree node 
covers.

To actually find those records within the space indicated by the query, 
the following algorithm is in order:
* The algorithm takes two parameters, one of them an interleaved 
coordinate with don't cares TV (the "test vector"), and a set of test 
vectors IN, containing ranges that are known to be entirely within the 
area described by the query.
* If the coordinate range indicated by TV contains no records, return IN.
* If the range indicated by TV is entirely within the space described by 
the query, return IN + {TV}.
* If the range indicated by TV is entirely outside the space described 
by the query, return IN.
* Otherwise, create two new test vectors from TV: one by replacing the 
first don't-care bit of TV with a 0, and one by replacing it with 1, 
giving the new test vectors TV0 and TV1. Return
   ALG (TV0, ALG (TV1, IN))
where ALG is this algorithm.

This will give a set of ranges that contain the records within the space 
indicated by the query, ready for retrieving them from mnesia.

This is a useful framework.
For one, set operations are easy to do on this representation. 
Intersection and union of range lists are nearly trivial, set difference 
requires a bit of thinking and care but is rather straightforward as well.
Another question might be how to set up a view. The algorithm doesn't 
return a Mnesia view, it returns lists of coordinate ranges. To convert 
them to a view without doing extensive changes to Mnesia, you'd have to 
construct a temporary table with the (primary keys of) the records that 
are selected by the spatial query. I'm not sure how attractive 
efficiency-wise that would be, but it might save your neck if you need 
to postprocess the result set with further queries.

A general note: the above algorithm leaves open how the intersection 
test between coordinate ranges and geometric figures can be done. In the 
most general case, the intersection-testing code would be passed in as a 
function or as a fun.
However, such testing can be tricky for complicated geometric queries. 
It might be better to write a test function for simple queries ("inside 
a rectangular range", "inside an ellipsoid", "to the right of a plane" 
etc.), run the algorithm for each simple query that's in the complex 
query, and then do set operations.
Note that for this to work, you need every simple query in two forms: 
one for the inside and one for the outside. It might save a few lines of 
code and a few hours of testing to make three-valued functions that 
return "inside", "outside", or "intersects", and adapt the base 
algorithm accordingly.

Hope this all is useful to somebody.

Regards,
Jo