&gt; a lot more expensive than a few multiplications<p>It&#x27;s &quot;t&quot; times the few multiplications, because each one gives a 75% success factor. This is equivalent to doing multiple hash functions.<p>&gt; and would use a lot more space<p>Well, yes and no. A Bloom filter is space-efficient, so it depends on what you compare it to.<p>If you have both lists in memory then each verification test can be run in constant memory.<p>But suppose you sort in-place? This cuts your overall memory use in half. You can use some of that saved space to construct the Bloom filter, then sort, then construct and compare the result.<p>It&#x27;s also possible to compute all &quot;t&quot; values first, then sort in-place, then compare. This is another sort of signature. I don&#x27;t know enough to tell if this will require more or less space than an equivalently powerful Bloom filter.<p>&gt; &quot;What do you want to gain by augmenting the data with position information?&quot;<p>It&#x27;s a linear time check, rather than O(n log n). But at a cost of n * log(n) bits (or n*32 bits if we assume 32 bit indices.)