Spatial Indexes in mnesia

Hal Snyder hal@REDACTED
Fri Oct 17 22:11:22 CEST 2003

Joachim Durchholz <joachim.durchholz@REDACTED> writes:

> 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.


> Hope this all is useful to somebody.


We have used the above approach in two dimensions for sorting inputs
prior to batch-loading of an rtree-indexed table (PostgreSQL). It was
for a telephony app in which a person calls in, platform gets long/lat
based on ANI, then it looks in 2-d indexed database to find nearest
service provider.

IIRC the ordering is what you would get doing a traversal of the space
with a Hilbert curve of sufficiently high order.

This was all before we saw the (Erlang) light.

More information about the erlang-questions mailing list