<p>Perhaps a variant of the Bloom filter called <a href="http://arxiv.org/ftp/cs/papers/0306/0306046.pdf" rel="nofollow">Compact Approximator</a>: like a bloom filter but generalized so the entries are values from a lattice.
That lattice is here just floats between 0 and 1 (it has more structure than just being a lattice but it satisfies the requirements) or however you're storing those numbers.</p>

<p>An update replaces the relevant entries by the max between it and the value being remembered, a query computes the minimum of all its relevant entries (examples below). The results can only overestimate the true value. By reversing the ordering (swapping min and max and initializing to 1 instead of 0) you can get an underestimation, together giving an interval that contains the true value.</p>

<hr>

<p>So for example, using the first approximated (overestimations), putting in a number looks like this:</p>

<pre><code>index1 = hash1(key)
data[index1] = max(data[index1], value);
index2 = hash2(key)
data[index2] = max(data[index2], value);
... etc
</code></pre>

<p>And getting the overestimation looks like:</p>

<pre><code>result = 1
index1 = hash1(key)
result = min(data[index1], result);
index2 = hash2(key)
result = min(data[index2], result);
... etc
</code></pre>
Space-efficient probabilistic data structures for number retrieval
<p>Consider we have an algorithm that receives a hypothetically long stream of keys. It then generates a value between 0 and 1 for each key, as we process it, for posterior retrieval. The input set is large enough that we can't afford to store one value for each key. The value-generating rule is independent across keys.</p>

<p>Now, assume that we can tolerate error in the posterior lookup, but we want to still <strong>minimize</strong> the difference in <strong>retrieved</strong> and <strong>original</strong> values (i.e. asymptotically over many random retrievals). </p>

<p>For example, if the original value for a given key was 0.008, retrieving 0.06 is much better than retrieving 0.6.</p>

<p>What data structures or algorithms can we use to address this problem? </p>

<p>Bloom filters are the closest data structure that I can think of. One could  quantize the output range, use a bloom filter for each bucket, and somehow combine their output at retrieval time to estimate the most likely value. Before I proceed with this path and reinvent the wheel, are there any known data structures, algorithms,  theoretical or practical approaches to address this problem?</p>

<p>I am ideally looking for a solution that can <strong>parameterize</strong> the tradeoff between space and error rates.</p>