dask / dask/dask-image

Idea: fully parallel ndmeasure.label

Open
#199 0 comments 3 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
226
Forks
56
PR merge metrics
No merged PRs in 30d

Description

We implemented distributed labeling in #94.

@chrisroat mentions [here](https://github.com/dask/dask-blog/issues/47#issuecomment-809924075) that instead of adding the total number of labels from previous chunks, we can uniquify each block's labels by using the top 32 bits of a 64-bit integer, assuming neither the labels of a single chunk nor the total number of chunks exceed 32 bits, which is a pretty safe assumption.

The issue with this approach is that you end up with very large label ids, which don't play well with some of the downstream processing, which requires creating arrays of size `max_label`.

@jakirkham [came up](https://github.com/dask/dask-blog/issues/47#issuecomment-811444438) with an interesting solution: instead of using the top 32 bits, use the bottom n bits, where n is large enough to accommodate the number of blocks. Since the number of blocks is known at the start, we can bit-shift the labels by that amount and do this fully in parallel. This should result in at most 2x "wastage" in label space, which is probably acceptable for the benefit of a cleaner, more parallel task graph.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.