Question: How do we ensure `TDigest::merge` never causes numCentroids over centroidsCapacity and thus index out of bound?

Closed
#703 8 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
25/100
Issue type
Bug
Clarity
Needs clarification
Activity status
Stale
Tech stack
java
Domain
data

Research direction

Start by reading TDigestDouble.java lines 571-602 and trace how merge updates numCentroids and uses centroidsCapacity. Determine whether the code establishes the required bound; done means documenting the invariant or identifying the precise change needed if it does not.

Written by the indexing model from the issue text.

Description

https://github.com/apache/datasketches-java/blob/37edd8c9898f8f073aaafad7097cb0949eb84c85/src/main/java/org/apache/datasketches/tdigest/TDigestDouble.java#L571-L602

I don't find any constraint that numCentroids will never exceed centroidsCapacity here.

Dominant language
Java
Stars
958
Forks
226
Avg merge
3d 40m
Merged PRs (30d)
13

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from apache/datasketches-java

All issues in apache/datasketches-java

Similar issues

More Java issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.