Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

CountMinSketch Documentation is wrong #83

Open
nytr0gen opened this issue Dec 13, 2024 · 0 comments
Open

CountMinSketch Documentation is wrong #83

nytr0gen opened this issue Dec 13, 2024 · 0 comments

Comments

@nytr0gen
Copy link

Hi,

I noticed that the documentation on CountMinSketch is wrong. It states that the accuracy parameter to be used should be 0.999 (which is also the default value at https://github.com/Callidon/bloom-filters/blob/eb43a770544e1796e8e04919a30bd7cb2bf09e0f/src/sketch/count-min-sketch.ts#L77C54-L77C59)

I believe the accuracy variable used in the determining the rows parameter should be actually 1 - accuracy. This is based on the this documentation.

More specifically this paragraph which states that for a probability at least 1−δ, the CountMinSketch algorithm will require ln 1/δ rows.

Screenshot 2024-12-13 at 12 45 56 Screenshot 2024-12-13 at 12 47 55

There's also the fact that, at the moment, ln 1/δ with an δ of 0.999 will result in 1 rows for the algorithm, but that's counter intuitive because for a better accuracy, we will need more rows, not less.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant