Designing the Elements of a Fuzzy Hashing Scheme

Abstract

The goal of “fuzzy hashing” is to identify near duplicates and similar documents using hashes or digests. We consider a range of design elements that can be used with fuzzy hashing schemes. We examine the criteria for evaluating fuzzy hashes, and develop an approach for optimising a scheme to respect those criteria. We apply this approach to select appropriate design elements and parameter values. This results in surprising choices, the preference of skip-ngrams for adversarial problem domains; and that 2 bit vectors are preferred to 1 bit vectors.