132
CHAPTER 3. FINDING SIMILAR ITEMS
the lengths of the strings minus twice the length of the longest common
subsequence of the strings.
✦Hamming Distance: This distance measure applies to a space of vectors.
The Hamming distance between two vectors is the number of positions in
which the vectors diﬀer.
✦Generalized Locality-Sensitive Hashing: We may start with any collection
of functions, such as the minhash functions, that can render a decision
as to whether or not a pair of items should be candidates for similarity
checking. The only constraint on these functions is that they provide a
lower bound on the probability of saying “yes” if the distance (according
to some distance measure) is below a given limit, and an upper bound on
the probability of saying “yes” if the distance is above another given limit.
We can then increase the probability of saying “yes” for nearby items and
at the same time decrease the probability of saying “yes” for distant items
to as great an extent as we wish, by applying an AND construction and
an OR construction.
✦Random Hyperplanes and LSH for Cosine Distance: We can get a set of
basis functions to start a generalized LSH for the cosine distance measure
by identifying each function with a list of randomly chosen vectors. We
apply a function to a given vector v by taking the dot product of v with
each vector on the list. The result is a sketch consisting of the signs (+1 or
−1) of the dot products. The fraction of positions in which the sketches of
two vectors agree, multiplied by 180, is an estimate of the angle between
the two vectors.
✦LSH For Euclidean Distance: A set of basis functions to start LSH for
Euclidean distance can be obtained by choosing random lines and project-
ing points onto those lines. Each line is broken into ﬁxed-length intervals,
and the function answers “yes” to a pair of points that fall into the same
interval.
✦High-Similarity Detection by String Comparison: An alternative approach
to ﬁnding similar items, when the threshold of Jaccard similarity is close to
1, avoids using minhashing and LSH. Rather, the universal set is ordered,
and sets are represented by strings, consisting their elements in order.
The simplest way to avoid comparing all pairs of sets or their strings is to
note that highly similar sets will have strings of approximately the same
length. If we sort the strings, we can compare each string with only a
small number of the immediately following strings.
✦Character Indexes: If we represent sets by strings, and the similarity
threshold is close to 1, we can index all strings by their ﬁrst few characters.
The preﬁx whose characters must be indexed is approximately the length
of the string times the maximum Jaccard distance (1 minus the minimum
Jaccard similarity).
