Idea: fully parallel ndmeasure.label
- 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
Assessment
This issue has not been assessed yet.