3
$\begingroup$

I'm looking for a data structure that would allow storing samples (in O(1)) from a data stream in a fixed-size buffer while the stream length isn't known in advance.

Once the buffer size is exhausted it should start overwriting previous elements in a staggered manner, retroactively reducing the sampling rate of the data in the buffer.

I've already come up with the algorithm, but want to know if there's a proper name for this so I can look for ready-made implementations.

Basically, for a 16-element buffer, the insertion order would be:

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
   16    18    20    22    24    26    28    30 [a]
      32          36          40          44
         48          52          56          60
            64                      72
               80                      88
                  96                      104
                     112                     120
                        128
                           144
                              160
                                 176
                                    192
                                       208
                                          224
                                             240
<repeat from [a]>

Sorted buffer contents after the first 16 insertions:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Sorted buffer contents after the first 32 insertions:
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

After 64 insertions:
0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60

...and so on.

Basically, after storing the initial N elements, with each following M * N/2 elements stored, the buffer contains a (shuffled) history with an effective sampling rate of 1/(M+1).

$\endgroup$
6
  • 2
    $\begingroup$ Very clever. If this algorithm is indeed novel (or at least if no-one immediately comes up with a prior description of it), you might want to consider also publishing a general description of the algorithm, rather that just an implementation in a specific language. $\endgroup$ Jan 20 at 16:15
  • 1
    $\begingroup$ (AIUI, you first store input 0 at position 0 in the $2^n$ element buffer and then iterate over the rest of the input stream, storing input $i$ at position $p(i)=((i-1)\bmod(2^n-1))+1$ in the buffer if and only if all but the $n$ highest bits of the binary expansion of $i$ are zero. Which works because $p(i)$ is the digital root of $i$ in base $2^n$, so the input $j$ replaced by input $i$ always has the same digital root $p(j)=p(i)$. Thus, after $2^{kn}$ inputs, the retained input indices are exactly those of the form $i=2^{(k-1)n}p$ for $0≤p<2^n$.) $\endgroup$ Jan 20 at 16:30
  • $\begingroup$ @IlmariKaronen thanks, my implementation is stateful and mostly visual/intuition based, I'll see if it can be further optimized by deriving the indices directly. $\endgroup$ Jan 20 at 16:43
  • $\begingroup$ @IlmariKaronen I'm also curious whether there's a way to recover the chronological ordering at any moment faster than in O(N*log(N)), currently I've resorted to keeping insertion "timestamps" alongside the items themselves $\endgroup$ Jan 20 at 16:44
  • $\begingroup$ If I'm not mistaken, that should indeed be possible with some bit manipulation. I don't have time to write an answer right now, but I'll try to remember to get back to you on that. $\endgroup$ Jan 20 at 21:52

1 Answer 1

4
$\begingroup$

The best name I can think of is derandomized or deterministic reservoir sampling. I don't know of any ready-made implementations.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.