GEO / GIS queries

[joepio]

Atomic Server basically supports three indexes as of now: full-text search, a value index, and subject index. If we want a performant way for users to see items on a map, we'll need a different kind of index.

Approaches

Leave out of scope (current option).

Scope creep. GIS features are a whole thing. There's a whole bunch of standards in this domain that people may expect (like wms of wfs).
Even if we build a performant index for GEO queries, we still only support one specific GEO related feature.
We will still miss things like:

• Server-side rasterization (heatmaps)
• Counts / aggregates
• Shapes / polygons

Use starts_at / range queries sorted by lat / long value

Our current index already allows for range queries. By running two range queries and combining the results we can already do geo queries.

However, this may break down if we do queries closer to the poles perhaps.

Find existing embeddable solution

List of useful tools, but nothing that really looks like what I'm searching for.

Custom / clever KV spatial index(es) using sled

Geohashing

Convert latitude and longitude into a geohash string. Geohashes have the property that prefixes of the hash represent larger areas, with each character added to the hash refining the location to a smaller region. This allows for efficient range queries by querying keys with the same prefix.

This geohash crate can come in useful.
When we process a commit, we check added or set properties with a geo datatype. When we find these, we update the geo tree index, which contains all geo resources (for a certain drive?).

Quadtree encoding

Morton Encoding

Convert each (latitude, longitude) pair into a Morton code and use these codes as keys in your Key/Value store. Range queries can be performed by calculating the Morton codes for the corners of the query region and retrieving keys within this range