Implement Hartigan's leader algorithm as a C window function

[greenape]

One of the most awesome things FlowKit does is provide an implementation of the Isaacman et al's meaningful locations algorithm. At present, the clustering portion of this, which uses Hartigan's leader algorithm, is written as a pl/pgSQL aggregate function and is pretty hairy, and very slow.

A much better fit here would be a C window function, ala PostGIS' DBSCAN and KMeans functions.

This isn't the easiest thing in the world to do, because the window-functions-in-C bit of Postgres is one of the more weakly documented areas, but would I suspect yield some big performance wins. (Might also be something worth contributing back to PostGIS.)

I'd suggest that the signature wants to be something like:

ST_Leader(point, weight, distance_threshold) -> cluster number (iirc, you can't return more than one value per row from a window function.)

We'd possibly want to pair this with a weighted centroid implementation as well, to facilitate matters, and make it easy to get the cluster centroid back after doing the assignment.

Alternatively, you can apparently write window functions using PL/R! So that's also a possibility.

[greenape]

This post on the pg-development group has a minimal window function implementation: https://www.postgresql.org/message-id/[email protected] which is a decent reference.

[greenape]

Also relevant, is this PR against PostGIS which added the DBSCAN window function: https://github.com/postgis/postgis/pull/86

[greenape]

Other options on the return type might be a json blob, a composite type, or a custom type.

[greenape]

Or maybe in rust, @Thingus?

[Thingus]

PGX (the Rust crate for talking to Postgres) only spits out json/jsonb right now, so as long as that's appropriate, it seems ideal