3.11. REFERENCES FOR CHAPTER 3
133
✦Position Indexes: We can index strings not only on the characters in
their preﬁxes, but on the position of that character within the preﬁx. We
reduce the number of pairs of strings that must be compared, because
if two strings share a character that is not in the ﬁrst position in both
strings, then we know that either there are some preceding characters that
are in the union but not the intersection, or there is an earlier symbol that
appears in both strings.
✦Suﬃx Indexes: We can also index strings based not only on the characters
in their preﬁxes and the positions of those characters, but on the length
of the character’s suﬃx – the number of positions that follow it in the
string. This structure further reduces the number of pairs that must be
compared, because a common symbol with diﬀerent suﬃx lengths implies
additional characters that must be in the union but not in the intersection.
3.11
References for Chapter 3
The technique we called shingling is attributed to [11]. The use in the manner
we discussed here is from [2].
Minhashing comes from [3]. The improvement that avoids looking at all
elements is from [10].
The original works on locality-sensitive hashing were [9] and [7]. [1] is a
useful summary of ideas in this ﬁeld.
[4] introduces the idea of using random-hyperplanes to summarize items in
a way that respects the cosine distance. [8] suggests that random hyperplanes
plus LSH can be more accurate at detecting similar documents than minhashing
plus LSH.
Techniques for summarizing points in a Euclidean space are covered in [6].
[12] presented the shingling technique based on stop words.
The length and preﬁx-based indexing schemes for high-similarity matching
comes from [5]. The technique involving suﬃx length is from [13].
1. A. Andoni and P. Indyk, “Near-optimal hashing algorithms for approxi-
mate nearest neighbor in high dimensions,” Comm. ACM 51:1, pp. 117–
122, 2008.
2. A.Z. Broder, “On the resemblance and containment of documents,” Proc.
Compression and Complexity of Sequences, pp. 21–29, Positano Italy,
1997.
3. A.Z. Broder, M. Charikar, A.M. Frieze, and M. Mitzenmacher, “Min-wise
independent permutations,” ACM Symposium on Theory of Computing,
pp. 327–336, 1998.
4. M.S. Charikar, “Similarity estimation techniques from rounding algo-
rithms,” ACM Symposium on Theory of Computing, pp. 380–388, 2002.
