[FEA] Expand aggregation kinds for feature engineering (map concat, approx distinct, approx topk)
- Dominant language
- C++
- Stars
- 9.8k
- Forks
- 1.1k
- Avg merge
- 3d 6m
- Merged PRs (30d)
- 278
Description
**Background**
cuDF supports a wide range of aggregation kinds, but there are some functionality gaps that are relevant for feature engineering workflows.
Some common aggregation kinds include map concat, approx distinct, approx quantile and approx topK.
* For map concat, we would need some kind of specialization on `MERGE_SETS` to only deduplicate on keys rather than both keys and payload. Also see below for additional scoping
* For approx distinct we may need to add some aggregation kinds like `HYPERLOGLOG` and `MERGE_HYPERLOGLOG`.
* For approx quantiles we probably already have adequate support using `TDIGEST` and `MERGE_TDIGEST` aggregation kinds.
* For approx topK I suspect we will need a new algorithm to support this.
**Support for `MERGE_MAPS` or "map concat"**
In cuDF, map types are often modeled as `list>`. cuDF supports aggregations with `list<...>` payloads, using the `MERGE_LISTS` and `MERGE_SETS` aggregation kinds. However, the common "map concat" use case requires deduplication over the keys in each row.
For example:
```
input_data = cudf.DataFrame({'a':[
[{'key':'k1','value':'red'}, {'key':'k2','value':'green'}],
[{'key':'k1','value':'orange'}, {'key':'k1','value':'blue'}],
[{'key':'k1','value':'red'}, {'key':'k2','value':'red'}],
[{'key':'k1','value':'red'}, {'key':'k1','value':'red'}],
]})
valid_output = cudf.DataFrame({'a':[
[{'key':'k1','value':'red'}, {'key':'k2','value':'green'}],
[{'key':'k1','value':'orange'}],
[{'key':'k1','value':'red'}, {'key':'k2','value':'red'}],
[{'key':'k1','value':'red'}],
]})
```
This transformation is roughly equivalent to a segmented stream compaction with a custom equality condition. The algorithm could segment by row, run distinct with keep any on the "key" child column, and then gather over both the "key" and "value" child columns into the result. I believe the order of keys does not matter, but I could imagine that some applications would want to apply a segmented sort to the map column.
Contributor guide
Assessment
This issue has not been assessed yet.