Hi all! FYI, I'm sending some statistics on the size of our sketch RE-KLL (produced by my Python implementation), depending on the stream length N and accuracy parameter k. More precisely, I'm plotting the maximal nominal capacity (MaxNomSize) of the sketch, which is very close to the true number of stored items (up to O(k) items). I've tried all N = 10^L for L = 3, 4, ..., 11.
Even though the size seems to be linear in log(N) on the first sight, when you
look at the derivative, it's actually slowly increasing as N grows. I think
this confirms the log^{1.5}(N) in the space bound in the paper. However, it
seems strange that the derivative is not monotone.
(The test for N = 10^11 and k = 25 is still running and should finish in a few
days. I can run tests for N = 10^12 if you'd like, the results will be produced
by Christmas or so :-) Perhaps, better to use the Java implementation then.)
Cheers,
Pavel
RE-KLL-sizes.pdf
Description: RE-KLL-sizes.pdf
--------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
