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 上公開;將該 binding 與 hll/include/hll.hpp 以及所參照的 Java HllSketch API 進行比較。當 Python 呼叫端可以呼叫 get_composite_estimate(),且 binding 的相關檢查確認該方法可用並回傳底層的複合估計值時,工作即告完成。

由索引模型根據 Issue 內容生成。

評估

技術堆疊
cpp, java, python
領域
api
Issue 類型
功能
難度
2/5
預估耗時
1-3 小時
活躍度
活躍
描述清晰度
描述清楚
新手友好度
78/100

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。