mapbox / mapbox/robosat

Implement optional random feature sampling for `rs extract`

Open
#7 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
2.1k
Forks
385
PR merge metrics
No merged PRs in 30d

Description

For features like buildings we want to sample OpenStreetMap when extracting geometries in `rs extract`.

The osmium handlers in `robosat.osm` should take a sampler and then for every OpenStreetMap entity call back ask the sampler if they should handle this entity or not.

For the sampler we have a few options:
1. let user pass a number `n` of samples (e.g. 20k); we take the first `n` and after that just drop features. Problem: we don't randomly sample from all geographical areas; not a good idea
2. let the user pass a fraction `f` of samples (e.g. `0.1`); in the osm call backs we take a random number `r` in [0, 1] and keep the sample if the number if `r < f`. Problem: users want a fixed amount of samples (e.g. 20k) but a fraction will change depending on how many features there are in osm. For example with parking lots a fraction of 0.1 is maybe a few thousands, with buildings it's millions.
3. do two passes over the data; in the first pass count how many features there are in osm, then come up with a fraction to keep; then in the second pass we use approach 2. Problem: needs two passes over the data, and two separate handlers for one feature.
4. use an online algorithm for random sampling: [reservoir sampling](https://en.wikipedia.org/wiki/Reservoir_sampling). It's an algorithm for randomly sampling `k` items out of a stream of unknown size. [This](https://www.paypal-engineering.com/2016/04/11/statistics-for-software/#dipping_into_the_stream) is a good read.

Tasks:
- [ ] Implement a `ReservoirSampler` class; it takes a size `n` of max. number of items to randomly sample from a stream of unknown size.
- [ ] Let our osmium handlers take a `ReservoirSampler`; in the osm entity call backs they push features into the reservoir. And in the save function they save features from the reservoir. The reservoir is responsible for keeping or discarding features doing the sampling.
- [ ] Add an optional argument to the `rs extract` tool for users to set the sample size; pass this argument to the sampler.

Note: now that we have the rs dedupe tool deduplicating detections against OpenStreetMap we need to think about how to design the interface here. The dedupe tool currently ready in the OpenStreetMap features created in the extract tool. If we randomly sample features in extract we can no longer use it for deduplication.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start in robosat.osm and trace how the rs extract entry point constructs osmium handlers and saves extracted features. Implement the ReservoirSampler flow described in the tasks, expose an optional sample-size argument on rs extract, and verify that the handlers save only the reservoir contents while considering the stated dedupe interaction.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
cli, data
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.