Sign up for ArangoGraph Insights Platform

Before signing up, please accept our terms & conditions and privacy policy.

What to expect after you signup
You can try out ArangoDB Cloud FREE for 14 days. No credit card required and you are not obligated to keep using ArangoDB Cloud.

At the end of your free trial, enter your credit card details to continue using ArangoDB Cloud.

If you decide that ArangoDB Cloud is not (yet) for you, you can simply leave and come back later.

Using Hilbert curves and Polyhedrons for Geo-Indexing

March 31, 201206GeneralTags: geo

Cambridge mathematician Richard R. Parker presents a novel algorithm he has developed using a Hilbert curve and Polyhedrons to efficiently implement geo-indexing.

March 31, 2012 Frank Celler

Frank is both entrepreneur and backend developer, developing mostly memory databases for two decades. He is the CTO and co-founder of ArangoDB. Try to challenge Frank asking him questions on C, C++ and MRuby. Besides Frank organizes Cologne’s NoSQL group & is an active member of NoSQL community.

6 Comments

Posted by Karussell on April 4, 2012 at 8:57 pm | |

Who was earlier? Mr Parker or this guy here:

http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
Posted by Karussell on April 4, 2012 at 9:00 pm | |

BTW: geostrings (called spatial key from me) are implemented in Java here:

https://github.com/karussell/GraphHopper/blob/master/src/main/java/de/jetsli/graph/geohash/SpatialKeyAlgo.java

resulting in Z curves … here is a quadtree implemented with this

https://github.com/karussell/GraphHopper/blob/master/src/main/java/de/jetsli/graph/trees/QuadTreeSimple.java
Posted by Richpark on April 5, 2012 at 6:48 am | |

Apologies if you felt I was claiming that using Hilbert Curves for indexing on the Earth’s surface was original. Of course it was not. Martin Schoenert suggested I look at it, as it might be better than the Z-curve I originally proposed to use. It was use of the observation that one can store, in each node of a binary search tree, the maximum distance to some fixed points and thereby effectively make “rectangles” even on the curved surface of a sphere that I though might be new.
Posted by Karussell on April 5, 2012 at 10:40 am | |

I see, I probably misinterpreted the title and in the video.

One question: do you need to store this ‘maximum distances’ information into the pots? In my implementation I’m not using this trick (+ I’m not sure I’ve understood it properly) but I’m using a bounding box calculated on the fly while searching – is this the same idea?

I can calculate the bounding box of a branch-node easily derived from the current geo string
Posted by Richpark on April 5, 2012 at 12:42 pm | |

Calculating the bounding box on the fly is not so good for three reasons. Firstly you must compute the maximum box of all points within the Hilbert Curve bounds, so that the bounds are not so tight – it is better to compute them for the points you actually have, not the curve. Secondly to reverse-engineer the Hilbert Curve into distances is very time consuming in itself. Thirdly I found five points were rather better, so that the bounding “box” was in fact a pentagon.
Pingback: Using Hilbert curves and Polyhedrons for Geo-Indexing « Another Word For It

Sign up for ArangoGraph Insights Platform

Using Hilbert curves and Polyhedrons for Geo-Indexing

6 Comments

Leave a Reply