[ZODB-Dev] Spatial indices

[Laurence Rowe]

It really depends on what you are trying to achieve.

The simplest solution would probably be to use a geohash string within
an OOBTree.

If you need a full geospatial solution, postgis is featureful and easy
to use, and simple to integrate transactionally with ZODB.

Reinventing the wheel is rarely the right option, though it might be more fun ;)

Laurence

On 16 June 2010 16:45, Nitro <nitro at dr-code.org> wrote:
> Hello,
>
> I tried to find a spatial index which integrates seamlessly into the ZODB.
> Unfortunately I did not find a satisfying solution anywhere. So I came up
> with three solutions how this could be implemented:
>
> 1) Write a native r-tree package, just like the current BTrees. Would
> likely have to be written in C for performance.
>
> 2) Make use of the existing B+ Trees by using a space filling curve such
> as the Z-curve or Hilbert curve to transform higher-dimensional data into
> 1D data which can then be stored in a BTree. Since B+ trees also provide
> range querying capabilities this should give good query performance.
> Unsure how much speed-up a C implementation of the insert/query functions
> would give. More info:
> http://www.scholarpedia.org/article/B-tree_and_UB-tree and
> http://www.drdobbs.com/184410998 .
>
> 3) Use the already existing Rtree package from
> http://pypi.python.org/pypi/Rtree . It's a thin wrapper of a C library, so
> it should be very fast. I can see two methods to make this work:
>
> 3a)
> - Create an rtree.RTree (stored in a separate file) and an OOTreeSet.
> - inserting: insert item into BTree. Then insert item's oid into Rtree.
> - querying: user supplies bounding box, rtree is queried, oids are
> returned. look up objects by oid in BTree.
> - zeo: does not work out-of-the-box with zeo since the Rtrees on different
> machines are not synchronized.
>
> 3b)
> - Create an rtree.RTree, a OOTreeSet and an IOTree. Difference to 3a):
> Create RTree with a custom storage manager (example:
> http://svn.gispython.org/svn/spatialindex/spatialindex/trunk/src/storagemanager/MemoryStorageManager.h
> and
> http://trac.gispython.org/spatialindex/browser/spatialindex/trunk/README#storage-manager
> ). This storage manager stores each page into the IOTree (key: pageId,
> value: pageData).
> - inserting: insert item into BTree. Then insert item's oid into Rtree.
> Causes storage manager to write out changed rtree pages to IOTree.
> - querying: user supplies bounding box, rtree is queried, pages for rtree
> returned from IOTree, oids finally returned from query. look up objects by
> oid in BTree.
> - zeo: works out-of-the-box with zeo since the rtree pulls its data from a
> btree (which is hooked up with zeo).
>
> Conclusion:
>
> 1) Native r-tree package: It is a lot of work which has already been done
> before. Bug-prone. Ruled out.
> 2) Spatial index on top of current BTrees: Looks interesting, could be
> done in python. Disadvantages: unclear UB tree patent situation, unclear
> how much work this really is.
> 3a) Does not work with zeo out-of-the-box. Ruled out.
> 3b) Requires writing a custom storage manager for the rtree package
> (likely in C). Provides different trees. Basic technology (rtrees +
> btrees) is tested.
>
> Would it make sense to add a default spatial index to ZODB? Does anybody
> of you have any experience with one of the mentioned solutions? Is anybody
> else interested in having a zodb spatial index?
>
> -Matthias
> _______________________________________________
> For more information about ZODB, see the ZODB Wiki:
> http://www.zope.org/Wikis/ZODB/
>
> ZODB-Dev mailing list  -  ZODB-Dev at zope.org
> https://mail.zope.org/mailman/listinfo/zodb-dev
>