Skip to content

Docs: show other spatial and data science indexes (k-d trees) alongside H3 #281

Open

Description

@alxmrs

Summary

The Learn page (docs/learn.md) shows H3, Uber's grid of hexagons, as a spatial index: give every row the ID of the hexagon it falls in, and a spatial join becomes an equality join. Other general-purpose data science indexes answer related questions, and it would be good to show how they fit with xarray-sql. One example is k-d trees: binary trees that split points by one coordinate at a time, as in scipy.spatial.KDTree or scikit-learn's KDTree and BallTree.

What a k-d tree adds over H3

  • Exact nearest neighbours and radius queries on arbitrary coordinates. That includes projected x/y and coordinates that aren't on Earth, such as embeddings and feature spaces. H3 answers these only approximately, through neighbouring hexagons.
  • Matching scattered observations to the nearest grid cell, or the k nearest. Examples include stations, ship tracks and lightning strikes. The Learn page snaps points to a regular grid with arithmetic, but curvilinear and irregular grids need a real index.

Possible shapes

  1. A docs section (the original suggestion). Build the tree in Python over a registered Dataset's coordinates, write the matches as a small table (point_id, cell lat, cell lon, distance), register it, and join it in SQL. This works on every engine today. It's the same pattern as the geospatial suite's regridding case (08), where Python computes the weights and SQL applies them.

  2. Engine-native nearest-neighbour queries, where they exist:

    • DuckDB's vss extension (HNSW, a graph index for approximate nearest neighbours, on fixed-size arrays);
    • the spatial extension's R-tree index, for ST_DWithin-style joins on native tables.

    Worth surveying which engines have one, and whether a registered table can use it or must be copied first.

  3. A helper, probably in the geo extra or a future ml one, that builds the match table from a Dataset and a set of points.

Starting with (1), as a short section after "Geometry and H3", seems right, with (2) and (3) as follow-ups if the pattern proves useful.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions