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.

Sign up for GitHub

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

Jump to bottom

estimate: new command for probabilistic algorithms starting with --cardinality-estimate option #2360

Open
jqnatividad opened this issue Dec 20, 2024 · 3 comments
Open

estimate: new command for probabilistic algorithms starting with --cardinality-estimate option #2360

jqnatividad opened this issue Dec 20, 2024 · 3 comments
Labels
enhancement New feature or request. Once marked with this label, its in the backlog.

Comments

@jqnatividad
Copy link
Collaborator

jqnatividad commented Dec 20, 2024 •
edited
Loading

Currently, --cardinality is computed by maintaining frequency tables in memory, which can potentially lead to OOM errors for very large datasets.

Add a "streaming" --cardinality-estimate option to estimate the cardinality using constant memory.

Use the HyperLogLog algorithm to do this.

There are several implementations in the Rust ecosystem - https://crates.io/search?q=hyperloglog
@jqnatividad jqnatividad added the enhancement New feature or request. Once marked with this label, its in the backlog. label Dec 20, 2024
@jqnatividad
Copy link
Collaborator Author

The most mature crate seems to be https://crates.io/crates/hyperloglogplus.

Use that for the implementation.

@jqnatividad
Copy link
Collaborator Author

Adding cardinality estimate is non-trivial and is not compatible with multi-threaded approach we use there.
Just create a stand-alone estimate command that will initially host HLL, but will also be the command for other probabilistic algorithms.

@jqnatividad jqnatividad changed the title stats: add --cardinality-estimate option estimate: new command for probabilistic algorithms starting --cardinality-estimate option Dec 29, 2024
@jqnatividad jqnatividad changed the title estimate: new command for probabilistic algorithms starting --cardinality-estimate option estimate: new command for probabilistic algorithms starting with --cardinality-estimate option Dec 29, 2024
@jqnatividad
Copy link
Collaborator Author

After further examination, the cardinality-estimator crate from CloudFlare looks promising...

https://crates.io/crates/cardinality-estimator

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement New feature or request. Once marked with this label, its in the backlog.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@jqnatividad