How Space Filling Curves accelerate ingest and query of Geospatial data
Geowave is an open source software project developed at the National Geospatial-Intelligence Agency (NGA) in collaboration with Booz Allen Hamilton and RadiantBlue Technologies. Geowave leverages BigTable architecture to manage terabytes of raster and vector data, serving as an enterprise level geospatial data store. To efficiently index geospatial data and answer queries with geospatial constraints, GeoWave employs a space filling curve to form bidirectional mappings between multi-dimensional data and BigTable’s sorted row identifiers. GeoWave leverages space filling curves beyond indexing. As a complete offering, Geowave provides optimizations to render interactive maps, compute uniform sized map-reduce input splits, and partition locality sensitive data for near neighbors class of algorithms.
Working with large range of numeric data, multidimensional mapping onto a space filling curve carries with it several key challenges. Range of data, such as polygon or a period of time, can exhibit a large number of duplicates when coupled with a high-grain compression. Furthermore, queries over large ranges can result in the decomposition of many independent ranges over the space filling curve. We introduce several techniques to solve these problems.
Data mapped to a space filling curve offer opportunities to improve performance in map image rendering and data partitioning. We share approaches and achievements in each of these areas of concern.