apache / apache/datasketches-python

Expose get_composite_estimate() on hll_sketch in the Python binding

未关闭 适合新手
#68 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
主要语言
Jupyter Notebook
星标
46
派生
9
PR 合并指标
30 天内没有已合并 PR

描述

### Request

The Python binding exposes `get_estimate()` only. Both reference implementations additionally expose the estimator that gives an order-independent result, and we would like it available from Python:

- **`get_composite_estimate()`** — public in C++ (`hll/include/hll.hpp`, `hll_sketch_alloc::get_composite_estimate()`) and in Java ([`HllSketch.getCompositeEstimate()`](https://apache.github.io/datasketches-java/6.1.0/org/apache/datasketches/hll/HllSketch.html), *"This is less accurate than the getEstimate() method and is automatically used when the sketch has gone through union operations where the more accurate HIP estimator cannot be used."*)

This is the only method we are asking for as binding parity, since it is the only one of the three discussed below that is public in both C++ and Java.

### Use case, and why it matters from Python specifically

In [datasketches-cpp#374](https://github.com/apache/datasketches-cpp/issues/374) a maintainer explains that HLL carries two estimators — HIP, which is more accurate but order-dependent, and the composite estimator, which is order-independent — and that:

> The choice of estimator here lets you make a trade-off between accuracy and order-independence.

with `getCompositeEstimate()` named as the way to take the order-independent side. That guidance is clear and we would like to follow it.

From Python we currently cannot. On `datasketches==5.2.0`, `dir(hll_sketch)` returns 18 public methods, none of which selects an estimator, and `src/hll_wrapper.cpp` on `main` binds no such method. So a Python caller who needs reproducibility across merge orders has no supported way to ask for it, while the same program in C++ or Java does.

Minimal illustration — one sketch, one fixed multiset of 3,000 distinct strings, four insertion orders, **no union anywhere**:

```
datasketches 5.2.0 · lg_k=12 · HLL_8
sorted est=2993.822394 HipAccum=2993.82 KxQ0=2616.65 NumAtCurMin=1972
shuffle(1) est=2982.892501 HipAccum=2982.89 KxQ0=2616.65 NumAtCurMin=1972
shuffle(2) est=2995.259277 HipAccum=2995.26 KxQ0=2616.65 NumAtCurMin=1972
shuffle(3) est=2965.637291 HipAccum=2965.64 KxQ0=2616.65 NumAtCurMin=1972
```

```python
from datasketches import hll_sketch, tgt_hll_type
items = [f"item-{i}" for i in range(3000)]
def build(order):
s = hll_sketch(12, tgt_hll_type.HLL_8)
for x in order: s.update(x)
return s
# same multiset, different insertion order -> different get_estimate()
```

Register state (`KxQ0`, `NumAtCurMin`, read from `to_string()`) is identical across all four; the reported estimate tracks `HipAccum`. Same-order runs are byte-for-byte deterministic across fresh processes. **This is the documented HIP behaviour and we are not reporting it as a defect** — it is simply the use case for wanting the other estimator.

### Two related observations, offered separately

1. **`get_hip_estimate()`** — mentioned in #374, but it does not appear in the current public C++ or Java API, so we are *not* requesting it as parity. Noting it only so the omission is deliberate rather than an oversight in this request.

2. **Out-of-order state** — `is_out_of_order_flag()` is private in C++ and absent from the Java public API, so this is a new-API question rather than parity. It would nonetheless be useful to a caller: it is the only way to know whether a returned `get_estimate()` is currently order-dependent. Today it is reachable from Python only by string-matching `to_string()`. Entirely at your discretion, and happy to drop it.

### A documentation question, if it's welcome here

The [Sketch Criteria](https://datasketches.apache.org/docs/Architecture/SketchCriteria.html) page lists as a required property:

> **Order Insensitive:** Results independent of item presentation order

Read literally, that is difficult to reconcile with #374 in the case where `getEstimate()` returns HIP — including for a single sketch fed raw input, as above, with no union involved. Would it be worth qualifying that wording for HLL when the HIP estimator is in use? Happy to open this separately if it would be better tracked on its own.

### Environment

`datasketches` 5.2.0 (current release) · Python 3.12 · `lg_k=12` · `HLL_8`

贡献指南

这个仓库没有索引到贡献指南

调研方向

从 src/hll_wrapper.cpp 开始,查找 get_estimate() 如何在 hll_sketch 上公开;将该绑定与 hll/include/hll.hpp 以及所引用的 Java HllSketch API 进行比较。当 Python 调用方可以调用 get_composite_estimate(),并且绑定的相关检查确认该方法可用且返回底层的复合估计值时,工作即告完成。

由索引模型根据 Issue 内容生成。

评估

技术栈
cpp, java, python
领域
api
Issue 类型
功能
难度
2/5
预计耗时
1-3 小时
活跃度
活跃
描述清晰度
描述清楚
新手友好度
78/100

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。