Archive for the ‘Hilbert Curve’ Category

Using Hilbert curves and Polyhedrons for Geo-Indexing

Thursday, April 5th, 2012

Using Hilbert curves and Polyhedrons for Geo-Indexing

From the AvocadoDB blog:

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

Basic premise is that points that are “near” on the line are also “near” on the Earth’s surface.

Interesting rhetoric but I think the “near” on the Earth’s surface is unnecessary.

More important to observe that a Hilbert curve when “straightened” and indexed, each point cuts across multiple dimensions of “nearness.”

Enables the isolation of “near” points in another representation, say global coordinates, quickly.

Points to consider/research:

  • Basis for indexing/sharding a graph database? An particular n-dimensional Hilbert curve is used for indexing/sharding. Not all queries created equal.
  • How do characteristics of the distances that compose the curve impact particular use cases?