Implement VarOptItemsSketch for Go

[Fengzdadi]

Overview

This issue tracks the implementation of VarOptItemsSketch (Variance Optimal Sampling) for the Go library, following the Java and C++ implementations.

VarOpt provides weighted sampling with optimal variance for subset sum estimation - useful for network traffic monitoring, ad analytics, and log sampling.

Proposed Implementation Plan

We plan to split this into multiple PRs for easier review:

PR 1: Core VarOptItemsSketch (basic functionality)

• Add VarOptItems family (ID=13) to internal/family.go
• Implement VarOptItemsSketch[T] struct with fields: k, n, h, m, r, totalWtR, data, weights
• Implement warmup mode (n ≤ k): store all items
• Implement estimation mode (n > k): weighted sampling with tau threshold
• Min-heap operations for H region
• Basic unit tests

PR 2: Serialization & Compatibility

• Implement Java-compatible serialization (equivalent to encodeVarOptItemsSketch + VarOptItemsSketchEncoder.Encode())
• Implement NewVarOptItemsSketchFromSlice()
• Add cross-language compatibility tests
• Generate test data files for validation

PR 3: Subset Sum Estimation

• Implement EstimateSubsetSum(predicate) returning bounds
• Pseudo-hypergeometric confidence intervals
• Tests for estimation accuracy

PR 4: VarOptItemsUnion (optional, can be deferred)

• Implement union with gadget/marks mechanism
• Serialization for union state

References

• Java: VarOptItemsSketch.java
• C++: var_opt_sketch.hpp
• Algorithm paper: Variance Optimal Sampling

[proost]

Implement ToByteArray() (Java-compatible format)
Implement NewVarOptItemsSketchFromSlice()

I don't know how l look like, but if possible i recommend to follow encoding package interface. Those methods name is more predictable to engineers who are familar with go.

[jmalkin]

What does from slice mean in this context?

[proost]

@jmalkin
I guess serialized sketch.

[Fengzdadi]

Implement ToByteArray() (Java-compatible format)
Implement NewVarOptItemsSketchFromSlice()

I don't know how l look like, but if possible i recommend to follow encoding package interface. Those methods name is more predictable to engineers who are familar with go.

Thanks for the feedback @proost

You suggested following Go's encoding package interface (MarshalBinary/UnmarshalBinary).

I looked at the existing codebase and found two different patterns:

Module	Serialization Method
kll, frequencies	ToSlice()
theta	MarshalBinary()

Q: Which naming convention should we follow for sampling?

1. ToSlice(serde) / NewXxxFromSlice(data, serde) - consistent with kll/frequencies
2. Marshal(serde) / Unmarshal(data, serde) - closer to Go standard

[Fengzdadi]

What does from slice mean in this context?

@proost is correct - "FromSlice" means deserializing from []byte (byte slice), which is Go's idiomatic representation of binary data.

[proost]

@Fengzdadi

If serde is needed for serialization, then i recommend encoder / decoder pattern like encoding/base64, encoding/binary, encoding/json, etc.

you can define stream i/o and bytes both using this pattern.

[proost]

@Fengzdadi
Hi! Are you still working on it?

[Fengzdadi]

@Fengzdadi Hi! Are you still working on it?

Hi! Sorry for the late reply. Yes — I’m still happy to keep contributing.

I’m just not sure what the highest-priority next step is right now. Would you prefer I continue iterating on my existing PR (#120), or should I close it and start a smaller, more focused PR based on current needs?

If there’s a specific issue/area you’d like me to pick up, I’m happy to follow your guidance.

[proost]

@Fengzdadi

I’m just not sure what the highest-priority next step is right now.

It doesn't matter in which order you do them. Just do what feels comfortable to you and we are welcome.

VarOptItemsSketch is incomplete. so if you are not working on, I will finish to complete.

[Fengzdadi]

I've been a bit too busy lately, but I'm still happy to finish this part slowly.