Re:Ask HN: Fast sampling and update of weighted items? (data...
by loicfevrier on Wednesday March 25, 2009 @03:32PM
(#532305)
It means that K is much smaller that N.
Because if K is a O(N) then doing an update in O(log n) is not good, it is better to rebuild the whole strcuture in O(n).
and how are these K items found? Do they have the same weight as the sampled item?