> Golomb Coded Sets are similar to bloom filters but the storage space is much smaller. Worse performance though.
Humm. A link to these would have been good[1], but anyway I understand that an optimally filled bloom filter takes ~1.44 times more space than the optimal theoretic value (which I understand Golomb encoding gives you?), so 'much smaller' is not a helpful measure. Likewise the 'worse performance' is not a helpful phrase, I believe a linear lookup time is needed for decoding, but a small amount of space for an extra indexing structure can speed things up lots. Bloom filters are updatable (addition only in the simplest bloom filter), golomb coded sets practically can't be updated except by rebuilding AIUI.
I suppose binary heaps should get a mention <https://en.wikipedia.org/wiki/Binary_heap> cos they barely seem to figure in other comments here. The neat bit is they are trees but implicit (stored in an array) not explicit (which would use pointers) and are always balanced giving you log access times in a compact form.
Humm. A link to these would have been good[1], but anyway I understand that an optimally filled bloom filter takes ~1.44 times more space than the optimal theoretic value (which I understand Golomb encoding gives you?), so 'much smaller' is not a helpful measure. Likewise the 'worse performance' is not a helpful phrase, I believe a linear lookup time is needed for decoding, but a small amount of space for an extra indexing structure can speed things up lots. Bloom filters are updatable (addition only in the simplest bloom filter), golomb coded sets practically can't be updated except by rebuilding AIUI.
I suppose binary heaps should get a mention <https://en.wikipedia.org/wiki/Binary_heap> cos they barely seem to figure in other comments here. The neat bit is they are trees but implicit (stored in an array) not explicit (which would use pointers) and are always balanced giving you log access times in a compact form.
[1] <https://en.wikipedia.org/wiki/Golomb_coding> but there are simpler explanations on the web