5 ms·

I would be interested in knowing more about how the z-curve based indexing performs compared to R-trees, for example as used in PostGIS. Intuitively, if you lo

I would be interested in knowing more about how the z-curve based indexing performs compared to R-trees, for example as used in PostGIS. Intuitively, if you look at the z-curve map below, some parts of antarctica which are adjacent, are not close on the z-curve. http://www.geomesa.org/documentation/_images/Zcurve-HiRes.png http://www.geomesa.org/documentation/_images/Zcurve-HiRes.pn...

jandrewrogers 8y ago
They are used for different data models. Z-curve indexing only works well for point geometries, and in most quality implementations is effectively equivalent to a quad-tree; sequential locality is not a useful optimization in modern geospatial storage engines. R-tree indexing generalizes well to non-point geometries like polygons, but doesn't scale so you can only use it for small-ish data sets. The best indexing algorithms for geospatial are analogous to adaptive quad-trie (not quad-tree) algorithms, though usually in 3-space and with additional features to ensure uniform shard sizes given highly biased data. The most critical scalability feature of good geospatial stores has nothing to do with indexing algorithm per se: the ability to adaptively reshard and migrate data/load between cluster nodes. Geospatial data models are inherently prone to hot spotting which becomes worse as data models grow.
- GeoMesaJim 8y ago
  One thing I'd add about GeoMesa's use of space-filling curves is that most of the databases used are key-value stores. Given that, it is somewhat unwieldy to manage R-tree indexes. Also, GeoMesa implements an 'XZ'-curve schema which gets around a few of the problems just using a Z-order curve runs into. To the point about hot-spotting, there's a configurable sharding strategy that can help spread the data around more of the nodes in the cluster. I haven't seen an easy/obvious way to apply adaptive quad-tries on top of key-value stores like Accumulo and HBase. Managing complex data structures in a cloud seems to be rather difficult.

jandrewrogers 8y ago

They are used for different data models. Z-curve indexing only works well for point geometries, and in most quality implementations is effectively equivalent to a quad-tree; sequential locality is not a useful optimization in modern geospatial storage engines. R-tree indexing generalizes well to non-point geometries like polygons, but doesn't scale so you can only use it for small-ish data sets. The best indexing algorithms for geospatial are analogous to adaptive quad-trie (not quad-tree) algorithms, though usually in 3-space and with additional features to ensure uniform shard sizes given highly biased data. The most critical scalability feature of good geospatial stores has nothing to do with indexing algorithm per se: the ability to adaptively reshard and migrate data/load between cluster nodes. Geospatial data models are inherently prone to hot spotting which becomes worse as data models grow.

GeoMesaJim 8y ago
One thing I'd add about GeoMesa's use of space-filling curves is that most of the databases used are key-value stores. Given that, it is somewhat unwieldy to manage R-tree indexes. Also, GeoMesa implements an 'XZ'-curve schema which gets around a few of the problems just using a Z-order curve runs into. To the point about hot-spotting, there's a configurable sharding strategy that can help spread the data around more of the nodes in the cluster. I haven't seen an easy/obvious way to apply adaptive quad-tries on top of key-value stores like Accumulo and HBase. Managing complex data structures in a cloud seems to be rather difficult.