hash/geotimehash extension for spatio-temporal sorting and partitioning

[gadomski]

As we're working on stac-geoparquet, we're finding that there are significant performance improvements when the data are sorted and partitioned.¹² As space and time are the two "first-class" attributes of STAC items, it follows that a good sort key should include both. The idea of combining a geohash with a timehash is not particularly novel, but this author hasn't found a good, portable implementation so I'm experimenting with some ideas over in rustac (PR). I'm thinking it may make sense to extract the code to its own repository and provide Python+WASM bindings, so folks don't need to use rustac to use the hasher.

Currently, my implementation has three inputs to its hashing function:

• spatial precision in degrees
• temporal precision as a duration (e.g. one hour or one day)
• temporal extent

There should be an optional fourth input³, spatial extent, but for simplicity I'm currently using the entire WGS84 domain. If you know your temporal extent, and are happy with the global domain, the algorithm can calculate the spatial and temporal precisions for you and apply the hash to a stream of items (no need to load them all into memory). Currently, I'm using the hash as a prefix for item ids, which should enable faster needle-in-a-haystack (aka search-by-id) queries against stac-geoparquet; one can imagine other uses for a hash (partitioning, filtering, etc).

Very simple usage looks like this:

$ cargo run -- hash scripts/fixtures/1000-sentinel-2-items.parquet | jq '.features.[].id' | (head; tail)
"69febadfa5bbcdbf-S2B_MSIL2A_20240828T174909_R141_T13TEF_20240828T214916"
"69feb3d97e9b6d24-S2B_MSIL2A_20240828T174909_R141_T13TEE_20240828T214916"
"69feba5fec9f5f37-S2B_MSIL2A_20240828T174909_R141_T13TDF_20240828T214916"
"69feb35b7ebb4d74-S2B_MSIL2A_20240828T174909_R141_T13TDE_20240828T214916"
"69feba4d3fdf5be6-S2B_MSIL2A_20240828T174909_R141_T13TCF_20240828T214916"
"69feb3493dff4f64-S2B_MSIL2A_20240828T174909_R141_T13TCE_20240828T214916"
"69fe9edd3f9afbe6-S2B_MSIL2A_20240828T174909_R141_T13TBF_20240828T214916"
"69fe97d93497fb2c-S2B_MSIL2A_20240828T174909_R141_T13TBE_20240828T214916"
"69fcfbfd3cd659ee-S2B_MSIL2A_20240828T174909_R141_T13SED_20240828T214916"
"69fcfaeb6ef64d27-S2B_MSIL2A_20240828T174909_R141_T13SEC_20240828T214916"
"20dc719720acaca6-S2A_MSIL2A_20240711T173911_R098_T13SEB_20240712T025100"
"20dc39b7b2a8bce5-S2A_MSIL2A_20240711T173911_R098_T13SEA_20240712T024752"
"20dc79a570ad3cec-S2A_MSIL2A_20240711T173911_R098_T13SDD_20240712T025103"
"20dc78a123ad3825-S2A_MSIL2A_20240711T173911_R098_T13SDC_20240712T024630"
"20dc7117698988a5-S2A_MSIL2A_20240711T173911_R098_T13SDB_20240712T025100"
"20dc3937fb891a75-S2A_MSIL2A_20240711T173911_R098_T13SDA_20240712T024831"
"20dc3927fb851cb6-S2A_MSIL2A_20240711T173911_R098_T13SCA_20240712T025137"
"20da8e07a1228035-S2A_MSIL2A_20240710T180921_R084_T12TXL_20240711T032121"
"20da87017322b4fe-S2A_MSIL2A_20240710T180921_R084_T12TXK_20240711T031353"
"20da28968129849b-S2B_MSIL2A_20240709T174909_R141_T13TEF_20240709T235809"

Because you can only compare hash values if they were generated with the same input parameters, we'll need to store those parameters on the items. It probably also makes sense to store them on a collection, so that a collection can "advertise" what hasher params should be used for its items. All this leads us to propose a new STAC extension, and I'd love to hear your thoughts and feedback.

Extension proposal

• Title: Hash (or GeoTimeHash)
• Field Name Prefix: hash
• Scope: Item, Collection

Field Name	Type	Description
hash:spatial_precision	number	REQUIRED The spatial precision of the hashing algorithm in degrees latitude/longitude
hash:temporal_precision	string	REQUIRED An ISO 8601 duration
hash:temporal_extent	string	REQUIRED A '/'-separated ISO 8601 interval with both start and end defined (cannot have "..")
hash:spatial_extent	[number]	The bounding box of the items. If not provided, the global bounding box will be used
hash:dtype	string	One of uint32 or uint64 (default uint64)
hash:encoding	string	One of base64 or base16 (default base16)
hash:value	string	The actual hash value. This is optional, as the hash might only be used (e.g.) as an item id prefix

Note

The extension will also need to define the hashing algorithm, so others may implement.

Note

I'm not quite sure how the "prefix the item id with the hash" stuff fits in. Should that be part of the extension spec?

Footnotes

1. https://www.gadom.ski/posts/stac-geoparquet-organization/ ↩

2. https://github.com/opengeospatial/geoparquet/blob/main/format-specs/distributing-geoparquet.md#spatial-partitioning ↩

3. And really another fifth one to set the precision of the output hash (u32 or u64, or maybe more?) ↩

[diegoripley]

I am not an expert on geohashes or timehashes, but my rudimentary understanding of the applications of this extension is that it can be used:

1. As a way for people to structure their data in places like object storage, for example:

object-storage://product_id/geotimehash/{filename}.{parquet,tiff,etc}

2. As a quick way for people to do queries. You mentioned WASM, so I am assuming your primary use-case would be as a way for browsers to do quick searches vs. expensive spatial queries.

Is this some of the applications you see for this extension, or are you thinking of any others? I would love to hear your on potential applications.

Other

I can imagine this extension being used to create an offline browser application of [1] (not affiliated), with no server required.

[1] https://www.pickyourplace.app/explore#13.75/49.22717/-123.14209

[gadomski]

As a way for people to structure their data in places like object storage

Yup, this is the "partitioning" use-case. You could use a truncated version of the hash to partition files in object storage.

As a quick way for people to do queries. You mentioned WASM, so I am assuming your primary use-case would be as a way for browsers to do quick searches vs. expensive spatial queries.

Yup, if a large number of items are sorted by a geotimehash, then parquet row groups (or files, in a partitioned setup) will have spatial and temporal bounds that are a subset of the full dataset's. This will allow tools such as DuckDB to skip row groups (or files) that are ouside of a spatial or temporal query.

[diegoripley]

That makes total sense, especially for leveraging DuckDB to skip row groups.

I’m curious how you envision this intersecting with the evolving landscape of multidimensional, versioned formats like Icechunk. Because Icechunk introduces Git like branching and versioning by abstracting the storage layer into a transactional, content-addressable store, the traditional physical partitioning approach (e.x. /geotimehash=.../) doesn't map 1:1 since the storage layout is abstracted away.

In a Icechunk context, do you see the geotimehash playing a role strictly at the STAC metadata level to help narrow down the search to the correct datasets/branches, or could it theoretically be integrated into how the multi-dimensional chunks themselves are indexed? My use-case does not currently make use of Git-like branching, so I may keep it partitioned as you have envisioned, but I am interested in your thoughts.

Also, I’m planning to run some experiments this weekend structuring a sample dataset with this geotimehash approach to test behaviour. I'd be happy to report back with my findings if you're interested!

[gadomski]

I think @hrodmn's suggestion of hashing within a partition, rather than globally, could play well with traditional physical partitioning.

[hrodmn]

I love the idea of adding a convention for generating sortable ids that improve query performance 👏

How would you recommend setting hash:temporal_extent and hash:temporal_precision for a continuously updated collection where new items are being added all the time? Is there a cost associated with setting it to some distant future date?

Or, is this feature more applicable to static snapshots of STAC items?

[gadomski]

For collections with an undefined end date, you'll need to pick some date in the future that you think will capture all of your data. Alternatively, you could periodically re-write all the hashes as your temporal bounds expand.

I'd probably go with the former for most cases (e.g. pick 2100 and forget about it :-P) but that's just an instinct, I don't have evidence for that.

[hrodmn]

Maybe you set a hive-partition on simple attributes like year and month, then generate hashes for each partition independently so that the items within a single partition are sorted optimally. In this case the collection-level hash metadata would not really apply, but you could store it at the item-level.

[gadomski]

This might help the heterogenous-distribution use-case as well, per @jsignell's comment.

[jsignell]

I like this idea a lot! Is there an assumption that the data is evenly distributed such that the partitions will be similar sizes for a given hash:temporal_precision and hash:spatial_precision?

[gadomski]

It's a good point — using this type of hash as a partition key will provide similarly-sized partitions only if the items are relatively homogenous through space and time. It's an open question whether this will unduly affect performance ... I'm still a bit unsure (at least in the stac-geoparquet case) whether row group metadata will help mitigate performance issues due to unevenly-sized partitions.

As they say, "an area for future research."

[espg]

Possibly related to this-- I've been working on a new geospatial bounding box that uses healpix cells to encode spatial extent coverage. All of our data is at the poles, and the bounding 'box' specification is really just two kitty-corner coordinate pairs rather than all four corner coordinates of the box. This is miserable for Antarctica, so I've been working on a 'morton bounding box' to replace the two lat/lon coordinate pairs-- with an eye towards using these for fast spatial searches via STAC catalogs.

A morton index identifies a healpix cell (which is a geospatial hash). Since healpix cells are multi-resolution, a single morton index (which is a single 64-bit integer) will encode a.) how large your cell is, and b.) where that cell is located on the globe. Of course, once you have geospatial collections of data, you begin to have a fairly good chance of that data crossing cell boundaries. The idea with the morton bounding box is to account for this by selecting the four Morton indices that make up the minimum spanning tree of cells that cover input dataset. Since each of the four indices can be a different size of coverage, this ends up being reasonably compact-- here's a real example, showing the data points for a STAC catalog, along with the morton box spanning tree for flight line data over Antarctica (i.e., tree for span = 4):

That's for the top level STAC catalog metadata; each STAC item in the catalog would have there own morton bounding box. The actual morton indices look like this:

-613322221212
-613322221       # contains above cell
-613113          # doesn't contain either above cell
-613             # contains all above cells

I'm using 'bounding box' because it's a defined space in the STAC metadata schema to define four 64-bit numbers...but you could get a decent 'polygon' that fits much tighter if you allow for more cells. Here's what it looks like for the same example using 12 instead of 4:

But again, 4 values works for most cases... and parquet is most happy when it's parsing a data structure of fixed rather than variable length. There are 12 total base cells the cover the full globe, so if you're spatial coverage in under a 3rd of the planet, you can likely generate a decent coverage 'box' using the coordinates. For individual STAC items (rather than the catalog), you very rarely need even four coordinates to get a compact footprint, but having space allows for cases where you bump up against the base cell boundaries (i.e., intersecting over the north or south pole).

We'll roll out a version of this to solve this duplicate geospatial item issue in the coming week for our users internally, and post more details there if folks are interested.

[gadomski]

Very cool, thanks for sharing! I think including extent could be really useful for catalogs that have spatially-heterogenous data (like yours). For large EO catalogs with constant footprints (landsat, sentinel, etc), maybe less so?

I'd like to explore the idea more thought, so will be happy to read any details and findings you have as you roll it out.