# A data structure for an allocation-free dynamic sample rate buffer

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).

• 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. Jan 20 at 16:15
• (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$.) Jan 20 at 16:30
• @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. Jan 20 at 16:43
• @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 Jan 20 at 16:44
• 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. Jan 20 at 21:52