It makes sense (to me now, in retrospect) that a Bloom filter would require more memory than a characteristic fingerprint because the Bloom filter supports element tests in addition to equivalency. Thanks for working through the details!<p>Regarding &quot;Due to the way virtual memory is implemented&quot;, the essay does not use that memory model. It says a binary search take O(n log n) time, but it&#x27;s actually O(n log n) essentially random lookups. If we assume log n lookup time then the binary search is better described as O(n (log n) (log n)), yes?