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

[Enhancement]: consider replacing bloom filters with xor filters / binary fuse filters #32995

Open
1 task done
alexanderguzhva opened this issue May 12, 2024 · 4 comments
Open
1 task done

[Enhancement]: consider replacing bloom filters with xor filters / binary fuse filters #32995

alexanderguzhva opened this issue May 12, 2024 · 4 comments
Assignees
@weiliu1031
Labels
kind/enhancement Issues or changes related to enhancement

Comments

@alexanderguzhva
Copy link
Contributor

Is there an existing issue for this?

  • I have searched the existing issues

What would you like to be added?

consider replacing bloom filters with xor filters / binary fuse filters

an image from https://github.com/FastFilter/xor_singleheader

Why is this needed?

No response

Anything else?

No response
@alexanderguzhva alexanderguzhva added the kind/enhancement Issues or changes related to enhancement label May 12, 2024
@xiaofan-luan
Copy link
Contributor

is there any performance profiling result?

@alexanderguzhva
Copy link
Contributor Author

significantly faster.

https://arxiv.org/pdf/2201.01174

Untitled

Alternatively, we may use `Blocked Bloom filters' (https://save-buffer.github.io/bloom_filter.html; an example of a go package is https://github.com/greatroar/blobloom)

@xiaofan-luan
Copy link
Contributor

@weiliu1031 let's profiling all the filter in multiple dimensions:

  1. write speed
  2. query speed/batch query speed
  3. memory utilization
  4. if it can merge without loss precision it is a big plus

@weiliu1031
Copy link
Contributor

/assign

@weiliu1031 weiliu1031 mentioned this issue May 27, 2024
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@weiliu1031 weiliu1031

Labels
kind/enhancement Issues or changes related to enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@alexanderguzhva @xiaofan-luan @weiliu1031