A hypothetical optimal bloom filter-like data structures needs -log₂ ε bits per key as noted in [1]. For the absolutely arbitrary value ε=0.25 that&#x27;s 2 bits per key (so 2n bits), and you need that t times. Or if you do it directly with a higher success probability, say, 10^-6 then it&#x27;s 20 bits per element. That&#x27;s more than half of the input size, assuming 32 bit keys. The approach I wrote about uses O(log₂ p) = O(log₂ (n&#x2F;ε)) bits, or put differently: a constant number of integers. Bloom filters are awesome (and I know HN loves them) but this isn&#x27;t a good application for them.<p>Sorting in-place would be a neat trick, you&#x27;d have to store the t integers, but as I showed t=30 is more than enough. That&#x27;s 30 ints, again way less than a Bloom filter.<p>Re: position information, I&#x27;d consider that linear space too (measured in machine words). It&#x27;s a good idea but keep in mind that if the input was in a random order, these are n accesses to completely random memory locations. Due to the way virtual memory is implemented (TLB misses are commonly resolved using a B-Tree data structure to prevent timing attacks), they actually take closer to log n time. There&#x27;s an older paper that shows that this takes roughly the same time as sorting the input. I believe it was in [2] somewhere. Huge pages might mitigate this nowadays.<p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Bloom_filter#Alternatives" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Bloom_filter#Alternatives</a> - citation goes to Pagh, Anna; Pagh, Rasmus; Rao, S. Srinivasa (2005), &quot;An optimal Bloom filter replacement&quot;, SODA&#x27;05, pp. 823–829<p>[2] <a href="http:&#x2F;&#x2F;www.cs.le.ac.uk&#x2F;people&#x2F;rraman&#x2F;rahman-thesis.pdf" rel="nofollow">http:&#x2F;&#x2F;www.cs.le.ac.uk&#x2F;people&#x2F;rraman&#x2F;rahman-thesis.pdf</a> PhD thesis of Naila Yasmeen Rahman. The PDF resists my attempts to do full-text search. It might have been &quot;Analysing cache effects in distribution sorting&quot; from WAE&#x27;99. I&#x27;m sorry that I can&#x27;t be more specific right now.