thomasmg

26 ms·

271.
by thomasmg 7y ago
To be exact, it's a "logistic curve", which initially is exponential. From this 3Blue1Brown excellent video: https://www.youtube.com/watch?v=Kas0tIxDvrg
272.
by thomasmg 7y ago
When comparing countries (e.g. Italy against South Korea), you have to consider many factors. Cultural factors: how quickly do people change their habits, to do e.g. social distancing. Do people in public wear surgical masks. Population den
273.
by thomasmg 7y ago
Well, the same thing happened to me. I implemented it, wrote a benchmark, and later was told this is samplesort... Historic footnote: samplesort was the Python sort algorithm before it was replaced with Timsort: https://bugs.pyth
274.
by thomasmg 7y ago
Related is samplesort https://de.wikipedia.org/wiki/Samplesort - it is a comparison sort, and yes the complexity is also O(n log n), same as quicksort and merge sort. But it may have less branches, and possibly better
275.
by thomasmg 7y ago
Thanks for the link! I wasn't aware of this. The source code is available at https://github.com/wuwuz/Vacuum-Filter/ To me it looks like a version of the cuckoo filter that isn't restricted to a 2^n size
276.
by thomasmg 7y ago
(Author here) The project started by taking the cuckoo filter source code (which happens to be written in C++), and extend it. A lot of code comes from that conversion. Other implementations (Morton, CQF) are also written in C++. I write Ja
277.
by thomasmg 7y ago
(Co-author of the paper.) You are right. However, it is a bit hard to find the threshold. Even the original author of the cuckoo filter didn't get it right, see https://github.com/efficient/cuckoofilter/issues
278.
by thomasmg 7y ago
Yes it is possible to do this, but do people actually use those features? For (pure) cardinality estimation, there is HyperLogLog, which can also be merged...
279.
by thomasmg 7y ago
Interesting idea! Elias-Fano monotone sequences unfortunately do need a bit more space than just a list of Rice codes. What is possible, without having to increase the space usage, is to re-arrange the Rice codes in each bucket, so that all
280.
by thomasmg 7y ago
I would love to see improvements to the GCS code I have, but I tested with many different sizes and Golomb-Rice parameters... I was not able to reduce the size overhead in any way. Maybe you can help? There are two implementations, one is J
281.
by thomasmg 7y ago
Very interesting! If both construction and lookup need to be very fast, and if you do have enough memory, then I would say a blocked Bloom filter would be best (without knowing your use case in detail). With a regular Bloom filter, you will
282.
by thomasmg 7y ago
No, actually 2 would also work. It's just that 3 hash functions needs the least space for some reason (less than 2, less than 4 or more).
283.
by thomasmg 7y ago
I think there are many use cases where you don't add entries after construction, for example for log-structured merge trees. You anyway can't add too many, otherwise it will hurt the false positive rate. What _are_ important use c
284.
by thomasmg 7y ago
Yes, the underlying theory is from a minimal perfect hash function called "BDZ": http://cmph.sourceforge.net/bdz.html . Yes, sometimes a retry is needed, but the array is not made larger; it just retries with a di
285.
by thomasmg 7y ago
(Co-author here) For GCS, I also found the Golomb-Rice parameter Q-1 to be better, this is what we used. According to my calculation, the overhead of GCS is around 1.5 bit/key. See also https://github.com/0xcb/Golo
286.
by thomasmg 7y ago
Co-author of the paper here. The repo https://github.com/FastFilter/fastfilter_cpp contains all the source code and benchmarks. Yes, construction of the xor filter is slower, but I wouldn't say massively. You shou
287.
by thomasmg 7y ago
(Also a Swiss resident here) Another interesting language is (rather, was) "Matten-Englisch", something like Pig-Latin, "because people wanted to communicate in a way the police would not understand": https://
288.
by thomasmg 8y ago
Longer term, Hydrail [1] (Hydrogen) might replace Diesel-electric. I guess this will start with cities, where pollution is a problem. [1] https://en.wikipedia.org/wiki/Hydrail
289.
by thomasmg 8y ago
As a secondary (supplemental) hash, I found the Murmur finalizer methods are ok, but you can get better if you use different constants. See my result in this answer: https://stackoverflow.com/questions/664014/what-