home shape

Using Hilbert curves and Polyhedrons for Geo-Indexing

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

Frank Celler

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

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

      • 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

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

  1. Karussell on April 4, 2012 at 9:00 pm
  2. […] Using Hilbert curves and Polyhedrons for Geo-Indexing […]

Leave a Comment





Get the latest tutorials, blog posts and news: