Golomb-coded-map
A space-efficient, associative alternative to the Bloom filter (by 0xcb)
writeups
A collection of various writeups on research topics (by sipa)
| Golomb-coded-map | writeups | |
|---|---|---|
| 1 | 4 | |
| 4 | 49 | |
| - | - | |
| 0.0 | 0.0 | |
| over 1 year ago | about 1 year ago | |
| C | Sage | |
| MIT License | - |
The number of mentions indicates the total number of mentions that we've tracked plus the number of user suggested alternatives.
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Golomb-coded-map
Posts with mentions or reviews of Golomb-coded-map.
We have used some of these posts to build our list of alternatives
and similar projects. The last one was on 2021-08-18.
writeups
Posts with mentions or reviews of writeups.
We have used some of these posts to build our list of alternatives
and similar projects. The last one was on 2021-09-02.
-
Bitcoin tries to maintain 10 minutes between each block. This gives everyone in the world enough time to update their ledgers. Consistency is difficult when millions of machines are turned on and off every day. And yet, bitcoin is still becoming more reliable by the block
However, averaged over sufficiently long periods of time, the duration of blocks tends to be 600.5958 seconds (10 minutes times 2016/2014, see https://github.com/sipa/writeups/tree/main/bitcoin-difficulty-adjustment for a very mathematical explanation). If the average tends to less than that, it implies the hashrate is on average growing. If the average tends to more than that, it implies the hashrate is average shrinking.
- Private Authentication Protocols
-
An optimal algorithm for bounded random integers
You may be interested in this work going in the opposite direction, holding the bias constant and extracting the most ranges from a constant amount of randomness:
https://github.com/sipa/writeups/tree/main/uniform-range-ext...
This work is interesting because generating random bits via strong generators is typically much more expensive than extraction-- so it can be very useful in cases where a number of small random values are needed in a tight loop such as for some kinds of hash table and generating permutations.
-
A fast alternative to the modulo reduction
I recently discovered a generalization of this approach, which allows mapping a single hash to multiple independent numbers, each in their own range, while maintaining various uniformity properties.
A write-up is here, in case anyone is interested: https://github.com/sipa/writeups/tree/main/uniform-range-ext...
What are some alternatives?
When comparing Golomb-coded-map and writeups you can also consider the following projects:
xor_singleheader - Header-only binary fuse and xor filter library
cuckoofilter
awesome-ethereum-rollups - A list of resources related to scaling with rollups.