# Evolution of a Web-Scale Near Duplicate
Image Detection System

Andrey Gusev* and Jiajing Xu*  PinterestSan FranciscoCA
<EMAIL_ADDRESS>
(2020)

###### Abstract.

Detecting near duplicate images is fundamental to the content ecosystem of
photo sharing web applications. However, such a task is challenging when
involving a web-scale image corpus containing billions of images. In this
paper, we present an efficient system for detecting near duplicate images
across 8 billion images. Our system consists of three stages: candidate
generation, candidate selection, and clustering. We also demonstrate that this
system can be used to greatly improve the quality of recommendations and
search results across a number of real-world applications.

In addition, we include the evolution of the system over the course of six
years, bringing out experiences and lessons on how new systems are designed to
accommodate organic content growth as well as the latest technology. Finally,
we are releasing a human-labeled dataset of ~53,000 pairs of images introduced
in this paper.

near-duplicate detection, recommendation systems, locality sensitive hashing,
transfer learning, clustering

††submissionid: 979††copyright: iw3c2w3††journalyear: 2020††conference:
Proceedings of The Web Conference 2020; April 20–24, 2020; Taipei,
Taiwan††booktitle: Proceedings of The Web Conference 2020 (WWW ’20), April
20–24, 2020, Taipei, Taiwan††doi: 10.1145/3366423.3380031††isbn:
978-1-4503-7023-3/20/04††footnotetext: *Both authors contributed equally.

##  1\. Introduction

Near duplicate (near-dupe) image detection is a task of clustering exact and
near identical images. There is no universal precise definition of near-dupe
as it is very application platform specific. Typically, we refer to the same
image with pixel-level modifications (e.g. cropping, flipping, scaling,
rotating), or with a different perspective as a near-dupe image. Figure 1
shows some examples of near-dupe image pairs.

Figure 1. Examples of near duplicate image pairs.

(a) Without de-dupe filter

(b) With de-dupe filter

Figure 2. Results for search query ”lisa blackpink kill this love” on
Pinterest: (a) without image de-dupe filter (undesired user experience) (b)
with image de-dupe filter.

Near-dupe image detection is fundamental to photo-sharing web applications,
such as Pinterest. For example, users expect to see relevant and diverse image
search results. An excessive amount of near-dupe images would lead to an
undesired user experience, as shown in Figure 2(a). As another example,
recommendation systems can benefit from less noisy label and training data by
aggregating meta data from near-dupe images.

However, near-dupe image detection remains a challenging problem for a web-
scale image corpus, because it is difficult to (1) capture the criteria of
near-dupe and build a high-precision classifier, (2) scale to billions of
images, and (3) process new images incrementally. Prior web-scale efforts (Liu
et al., 2007; Wang et al., 2013; Gong et al., 2015; Kim et al., 2015) have
mainly focused on one of the above problems. But there has been limited work
that addresses all of the above problems.

(a)

(b)

Figure 3. (a) System Diagram (b) Output of the near-dupe image detection
system are near-dupe clusters. Each row represents one near-dupe cluster, with
the cluster head in dotted line and a few examples from the cluster.

This paper presents the design of our near-dupe image detection system, and
shares our approach to handling the above three challenges. For the first
challenge, we create a gold standard dataset using a crowdsourcing platform
and train an initial classifier to optimize for precision using this dataset;
we then bootstrap over synthetic labels produced by the initial classifier and
train a more powerful classifier based on visual embeddings. For the second
challenge, we map the visual embeddings into locality sensitive hashing (LSH)
(Indyk and Motwani, 1998) terms and implement batch LSH search efficiently on
Spark. For the third challenge, we develop an incremental update algorithm to
process a new batch of images on a daily basis.

Our system detects near-dupe images across 8 billion images, the largest
dataset to the best of our knowledge. Our method has three stages: candidate
generation using a batch LSH algorithm, candidate selection through transfer
learning over visual embeddings, and near-dupe clustering with incremental
updates. We describe how to apply near-dupe signals to make a big impact on
real-world applications such as Pinterest. We also include how to aggregate
meta data in a general recommendation system using near-dupe signals. We share
the lessons learned from the evolution of the system over the past six years,
including methods that could improve efficiency.

The rest of the paper is organized as follows: Sections 2 and 3 survey related
works and give a brief overview of the near-dupe image detection systems built
over the years. Section 4 presents in detail the candidate generation,
candidate selection, and clustering components of the latest system. Sections
5 and 6 describe how near-dupe signals can be used to enhance Pinterest
experiences. Section 7 shares what we have learned over the system’s
evolution.

##  2\. Related Work

###  2.1. Image Representation and Candidate Generation

Previous work represents images by global descriptor (Liu et al., 2007; Lin
and Wang, 2008; Yue et al., 2011), local descriptor (Liu et al., 2010; Li et
al., 2013; Kim et al., 2015), bag-of-visual-words (BOW) (Chum et al., 2009b,
a), and a hybrid of global and local descriptor (Wang et al., 2013; Zhou et
al., 2017). Global descriptor is easy to compute but is vulnerable to heavy
editing such as cropping. Local descriptor and BOW-based methods are great
alternatives to address this issue (Chum et al., 2009b, a; Zhou et al., 2016;
Yao et al., 2014; Liu et al., 2015). The BOW model, based on local descriptor,
is favorable for efficiency and scalability. One challenge for the BOW model
is that global context is lost in the representation. For the task of
detecting near-dupe copies, an overlapping region-based global context
descriptor is developed to increase the robustness of the features (Zhou et
al., 2016). In recent years, deep convolutional neural networks (CNN) have
been extremely successful for computer vision applications and have become the
dominant approach for classification (Krizhevsky et al., 2012; Simonyan and
Zisserman, 2014) and object detection (Girshick et al., 2014; Erhan et al.,
2014). CNN have also been used for the task of near-dupe detection (Su et al.,
2018; Hu et al., 2018; Zhang et al., 2018). However, training an end-to-end
CNN can be time-consuming and costly, and it also comes with extra computation
and storage cost for the task-specific image features. For web-scale
application, it is more desirable to reuse visual embeddings that are already
available. In this work, each image is represented by visual embeddings
trained for other computer vision tasks in (Jing et al., 2015).

For candidate generation, web-scale efforts use variants of approximate
nearest neighbor search (aKNN) (Liu et al., 2007) and min-hash (Chum et al.,
2008) to generate cluster seeds and grow the clusters (Wang et al., 2013; Kim
et al., 2015). LSH, an aKNN method that maps high-dimensional image
representations into a low-dimensional space to produce binary hash code, has
recently become a popular indexing method for large-scale datasets (Chum et
al., 2008, 2009a; Lee et al., 2010; Wang et al., 2017; Hu et al., 2018). This
paper adopts the LSH method and optimizes the implementation extensively on
Spark. We discuss in Section 7 that task-agnostic LSH works well as a
candidate generator.

###  2.2. Near-dupe Classifier and Web-scale System

Prior web-scale near-dupe detection systems use a decision stump as the near-
dupe classifier: (Liu et al., 2007) is based on global descriptors; (Wang et
al., 2013) relies on the number of overlapping visual words; and (Kim et al.,
2015) uses the Jaccard similarity of the sets of visual words of two images.
Because of the limitations of the global and local descriptors, (Kim et al.,
2015) has encountered noisy clusters, which limits its application in
recommendation systems. Geometric verification, e.g. RANSAC (Fischler and
Bolles, 1981), greatly improves the precision of the classifier (Wang et al.,
2013), but is very computationally expensive on a web-scale dataset. In this
work, we collect human curated near-dupe criteria, and train an embedding-
based deep near-dupe classifier to replace RANSAC in order to achieve high
precision efficiently. Compared with existing web-scale efforts, we improve
the design such that our system is capable of incremental updates.

##  3\. System Overview and Evolution

Table 1. Evolution of the Near-dupe system over time.

|  First Generation (Mid 2013) |  Second Generation (Early 2014) |  Third Generation (Mid 2018)
---|---|---|---
Applications | De-duplicate search feed |  Aggregate pin meta data |
|  Canonical pin selection | Remove copyrighted content |
| De-duplicate home feed |  |
Requirements |  Medium precision |  |
|  High precision |  |
|  High precision |  |
Medium-high recall |  |  |
| High efficiency |  |
Image Representation | Global features | Bag-of-visual-words (BOW) | Visual embedding
Candidate Generation | LSH | Inverted index | LSH on Spark
Candidate Selection | RANSAC | RANSAC + Decision tree | Deep classifier
Clustering | Map-Reduce | Map-Reduce | Greedy K-cut on Spark
Detected Near-dupes in |  |  |
Image Corpus (Includes Spam) | 23% | 46% | 64%

The near-dupe image detection system is composed of three main components
illustrated in Figure 3(a): candidate generation largely solves scaling and
drives the recall, candidate selection prunes the candidates to drive the
precision, and clustering approximates equivalence partitions over the
universe of images.

Each component has evolved drastically as application needs change and with
the emergence of newer approaches and technology. Table 3 illustrates how each
component evolves over time.

The first near-dupe detection system, developed in 2013, aimed to remove near-
dupe pin111On Pinterest, a pin is created when a user bookmarks an image, and
it contains meta data such as user-generated text description, board title,
destination url, etc. images on the search page for better user experience, as
shown in Figure 2. In this system, images were represented by global image
descriptors, and we used LSH-based search to generate near-dupe candidates. At
the candidate selection stage, we extracted local image descriptors and
applied geometric verification using RANSAC as the near-dupe classifier. The
clustering stage implemented Algorithm 2 on Map-Reduce, detailed in Section
4.3. The first system was efficient, but the drawback of global descriptors
limited the recall and precision. Since false positives did not affect user
experience in the search result, the system did not require high precision.

As the volume of data grew significantly on Pinterest, new applications
emerged and required higher precision, such as removing copyrighted images and
aggregating pin meta data. In order to overcome the limitation of global image
descriptors, the second generation system in 2014 adopted the popular BOW
image representation, which is ideal for retrieval. We obtained near-dupe
candidates by retrieving similar images from an inverted index containing all
images. To improve the precision of the near-dupe classifier, we employed a
two-stage near-dupe classifier containing (1) geometric verification using
RANSAC to reject false matches and (2) a decision tree model to guard against
near-dupe criteria. The decision tree model was trained using human-labelled
data and used features such as differences in global image descriptors, size
and location of the overlapping area of the two images after being
geometrically aligned, etc.

The second generation had much better recall and precision, but it was
inefficient in space and had high computational cost. Leveraging the emergence
of deep learning and Spark, the third generation focused on bringing the
recall higher while increasing the efficiency of daily processing to keep up
with the growth of the content corpus. The system was deployed in mid-2018.
Section 4 describes the design in more detail.

##  4\. The Latest Generation

In this section, we present each component shown in Figure 3(a).

###  4.1. Candidate Generation

####  4.1.1. Image Representation as LSH Terms

In this system, each image is represented by the visual embedding from (Jing
et al., 2015). To cluster images via the near-dupe relation, each day we
compare tens of millions of new images to billions of existing clusters.
Approaching such a nearest neighbor search without an optimization would yield
quadratic time complexity and a runtime proportional to more than 10
quadrillion image comparisons. Instead, we use a reduction of visual
embeddings into LSH terms to drastically improve the tractability of such a
problem.

Through a process based on bit selection of binarized embeddings, we first
reduce the dimensionality of the original embedding space. Next, the derived
bits are grouped into numeric LSH terms in a process that fundamentally trades
off detection probability and runtime. The smaller the groupings, the more
computationally expensive it is to run the nearest neighbor search, but this
increases the probability of accurate detection. Nearest neighbor search uses
LSH terms and their Jaccard overlap as an approximation of cosine similarity
between vectors in the original embedded space.

####  4.1.2. Batch LSH Search

With every image being represented by a set of LSH terms, we build an inverted
index and implement a batch-oriented search over images. It is important to
note that we only search against images that represent the entire cluster
(known as cluster heads). The selection of cluster heads is a combination of
engagement- and content-based heuristics at the time of initialization of the
cluster. This allows to reduce the search space with minimal recall loss due
to candidate augmentation, described in Section 4.1.3. To make batch-oriented
search efficient at a high level, we use a combination of functional
transformations, compressed inverted indexes and joins to calculate a result
set for all the query images at once. The batch LSH search is implemented on
Spark and requires a series of optimizations, such as dictionary encoding
(Witten et al., 1994) and variable byte encoding (Cutting and Pedersen, 1990),
to ensure we can handle the data volumes even in a much more computationally
tractable LSH term space. A combination of dictionary encoding and variable
encoding on image id can reduce inverted index storage space by 20%. Algorithm
1 details the transformations.

1

Input : $RDD[(indexImgId,List[LSHTerm])]$ ;

// index

2

$RDD[(queryImgId,List[LSHTerm])]$ ;

3 // query

Output : $RDD[(queryImgId,TopK[(indexImgId,Overlap)])]$

4

_;_

_5_ __ // create inverted index for query & index

_flatMapValues, groupBy query_ $\xrightarrow{}RDD[(LSHTerm,List[queryImgId])]$

_flatMapValues, groupBy index_ $\xrightarrow{}RDD[(LSHTerm,List[indexImgId])]$

6

7

_;_

_8_ __ // search results by query

_Join (1) and (2), flatMap over queries posting list, groupBy query_
$\xrightarrow{}RDD[(queryImgId,List[List[indexImgId])]$ ;

9

10

_;_

_11_ __ // count number of times each ImgId is seen

_Merge_ $List[List[indexImgId]]$ into $TopK(indexImgId,Overlap)$

12

13

Algorithm 1 Candidate Generation on Spark

####  4.1.3. Candidate Augmentation

A key observation is that if the query image does not match the cluster head
via a trained classifier, it may match some other images in the cluster - even
those that are extremely similar to the cluster head. To illustrate this,
assume a cluster $A\longleftarrow\\{B:99,C:99,D:70\\}$, where $A$ is the
cluster head, the similarity scores with respect to $A$ are as listed, ranging
from 0 to 100. A query image $Q$ may have scored relatively poorly with
cluster head $A$, i.e. $sim(A,Q)=10$, which is below a chosen $threshold$. We
have observed that $sim(B,Q)$ or $sim(C,Q)$ may be above the $threshold$ even
though $B$ and $C$ are extremely close to $A$ visually. The combination of
$(A,Q)$ presents a difficult or adversarial example for the trained classifier
in Section 4.2, but other images in the cluster may not necessarily share that
characteristic. Top augmentation images that are close to the cluster head
(e.g. $B$, $C$) are added to the candidate list and increase end-to-end recall
of the system by $13\%$.

####  4.1.4. Bootstrapping Over High Precision

A number of iterations of the improvements in the near-dupe system have relied
on data produced in a previous iteration and the property of near-exact
precision. Candidate augmentation is also heavily reliant on near-exact
precision of both the classifier and the consistency of the existing clusters.
We are able to consider $Q$ as matching cluster $A$ when any of top $k$ near-
dupes in $A$ match $Q$. This can only be possible when clusters are
consistently precise. While the near-dupe relation is not transitive, in
general by keeping the classifier at near-exact precision we are able to make
that assumption for close neighbors.

###  4.2. Candidate Selection

####  4.2.1. Near-dupe Classifier

Batch LSH is a powerful way to generate high recall while minimizing
computational cost. However, it will generally not produce optimum precision
and ranking of candidates. We use a pass over generated candidates via a
supervised classifier to select the candidates that are similar enough to be
considered near-dupes.

The task of the classifier is to select near-dupe images from the candidates
produced by LSH and the augmentation. Figure 4 illustrates how this classifier
works. To improve learning and convergence for each pair of images, hamming
bits (binarized visual embeddings from (Jing et al., 2015)) are XORed and fed
into the input layer, followed by 3 layers of fully connected layer and a
sigmoid.

Figure 4. Architecture of the near-dupe classifier.

The classifier is implemented in TensorFlow with Adam optimizer (Kingma and
Ba, 2014) over a set containing more than one billion distinct pairs described
in Section 4.2.2. The inference over the trained network happens in the Spark
context to efficiently vectorize and reduce overhead. With a network that has
almost 10 million parameters, we achieve an average of 1-2ms per prediction on
a cluster of r5d machines on Amazon Web Service.

####  4.2.2. Training Labels for the Classifier

In order to collect a large amount of training labels for the near-dupe
classifier, we used detection results from the previous generation of the
near-dupe detection system over LSH candidates as well as labels derived from
augmentation as described in Section 4.2.3. The previous generation classifier
is detailed in Section 3.

####  4.2.3. Augmentation Labels

Following the Augmentation procedure described in Section 4.1.3, we generate a
new training set for the next generation classifier that specifically targets
adversarial examples. In the provided example, note that even though $Q$ was
(correctly) recorded into cluster $A$ due to the transitivity over $B$, the
classifier was not able to handle $sim(Q,A)$ correctly. Learning over such
pairs is an effective way to increase accuracy.

###  4.3. Clustering

Finding an ideal partition over the universe of images is mathematically not
well-defined, because the near-dupe relation is not transitive and therefore
not an equivalence relation. For example, an image of a cat gradually morphs
into an image of a dog as shown in Figure 5. Each iteration would fall well
within the near-dupe criteria, yet it is not clear how to partition the
sequence.

Figure 5. An image of a cat can morph into an image of a dog through near-dupe
hops.

1

2

3

Input : Edges $(img\\_id1,img\\_id2)$

Output : Transitive closure clusters $C$

4 Initialization

5 Map  _edge ( $img\\_id1,img\\_id2$)_

6 $edge\\_id\leftarrow\textnormal{{Concat}}(img\\_id1,img\\_id2)$;

7 Emit ($img\\_id1,img\\_id2,edge\\_id$);

8

9

10

11

12

13while  _$num\\_edge\\_updated >0$_ do

14 Map  _$(img\\_id1,img\\_id2,edge\\_id)$_

15 Emit ($img\\_id1,img\\_id2,edge\\_id$);

16 Emit ($img\\_id2,img\\_id1,edge\\_id$);

17

18

19 Reduce  _on the first element of the tuple_

20 $group\\_id\leftarrow\textnormal{{Min}}(edge\\_id)$ in the group;

21 $num\\_edge\\_updated\leftarrow 0$;

22 foreach  _$(img\\_id1,img\\_id2,edge\\_id)$_ do

23 if  _$edge\\_id\neq group\\_id$_ then

24 $num\\_edge\\_updated$ += 1

25 end if

26 Emit ($img\\_id1,img\\_id2,group\\_id$);

27

28 end foreach

29

30

31

32 end while

33

Algorithm 2 Transitive Closure Algorithm

We represent images in a graph, where nodes are the images and edges represent
image similarity. We first apply the transitive closure algorithm (Algorithm
2) over coherent sub-clusters. Each sub-cluster is a set of images that pass
the near-dupe threshold for a given query image.

Following transitive closure, we greedily perform k-cut to correct for any
errors that transitive closure may have introduced over several sub-clusters,
illustrated in Algorithm 3. We rely on the fact that transitive closure was
formed from coherent sub-clusters to develop a greedy approximation algorithm
that is tractable.

###  4.4. Incremental Update Algorithm

We design our algorithm to handle a new batch of images on a daily basis. The
algorithm works in two stages. In the first stage, we use the new images to
query against (a) existing image clusters (NvO job) and (b) new images (NvN
job), shown in Table 2. We only run transitive closure for (b) since we want
to recognize the new image cluster within the new images. In the second stage,
we merge the near-dupe image mappings from the NvO job and the NvN job, with
the preference of NvO over NvN. Members of the NvN cluster will be mapped to
the old cluster if such a match is found. Otherwise the NvN cluster will be
added as a new cluster. This enables us to continue to grow existing image
clusters.

Table 2. Two-stage approach to process new images. (a) NvO job: use new images to match existing images (b) NvN job: use new images to match new images. TC: transitive closure. Name | Query set | Index set | TC + K-cut
---|---|---|---
(a) NvO job | New images | Existing images | No
(b) NvN job | New images | New images | Yes

##  5\. Experiments

###  5.1. Gold Standard Dataset

1

2

Input : Transitive closure clusters $C^{(i)}\in C,i=1..|C|$

3 while  _$C\neq\emptyset$_ do

4 foreach  _cluster $C^{(i)}\in C$_ do

5 $h\leftarrow\textnormal{{Rand}}(|C^{(i)}|),C^{{}^{\prime}}\leftarrow\\{\\}$;

6 foreach  _image $C^{(i)}_{k}\in C^{(i)},k\neq h$_ do

7 if  _$\textnormal{{Classify}}(C^{(i)}_{h},C^{(i)}_{k}) >t$_ then

8 $C^{{}^{\prime}}\leftarrow C^{{}^{\prime}}\cup{C^{(i)}_{k}}$;

9

10 end if

11

12 end foreach

13 if  _$C^{{}^{\prime}}\neq\emptyset$_ then

14 $C^{(i)}\leftarrow C^{(i)}\setminus({C^{(i)}_{h}}\cup C^{{}^{\prime}})$;

15

16 end if

17 $C\leftarrow C\cup C^{{}^{\prime}}$;

18

19 end foreach

20

21 end while

Algorithm 3 Greedy Approximate K-cut Algorithm

We created a dataset222Available at
https://www.pinterest.com/pin/100275529191933620. of ~53,000 pairs of images
by using a crowdsourcing platform (86% non-near-dupe and 14% near-dupe image
pairs). The dataset was evaluated by human judges who have achieved high
accuracy against a smaller golden set. For each pair, 5 different human judges
were asked whether the pair constitutes near-dupe images. To the best of our
knowledge, there is no prior work that has created a human-curated dataset of
this scale.

###  5.2. Classifier

We compared the performance of our near-dupe classifiers with the one in the
most recent published web-scale system (Kim et al., 2015), by evaluating on
the gold standard dataset. We implemented the near-dupe classifier based on
the Jaccard similarity between the visual words described in (Kim et al.,
2015).

The Decision tree classifier is described in Section 3. The Base deep
classifier described in Section 4 is trained with a dataset containing 100
million pairs of images generated based on the approach detailed in Section
4.2.2.

We further improved the classifier performance by refining the training set.
The Production deep classifier differed from the base deep classifier in
increasing the size, diversity, and difficulty of the training examples to
over 1 billion pairs of images. Table 3 lists the precision-recall (PR) and
ROC AUC of the above classifiers. By comparing the performance of the
classifiers using various image features, the visual embedding and the amount
of difficult training data play a big role in improving the performance
significantly.

In the latest generation system, we chose an operating point that maximizes
precision while having medium-to-high recall333One application of the system
is to remove copyrighted content by finding near-dupe copies of the content.
During one operation, human judges reviewed 6,700 detected near-dupe copies of
one copyrighted image, and found 0 false positive..

Table 3. Classifier performance on the gold standard dataset. | PR AUC | ROC AUC
---|---|---
Kim et al. (Kim et al., 2015) | 0.58 | 0.83
RANSAC + Decision Tree (Gen. 2) | 0.64 | 0.87
Base Deep Classifier | 0.80 | 0.96
Production Deep Classifier (Gen. 3) | 0.85 | 0.97

###  5.3. Cluster Pinterest Images

We applied the proposed method to a dataset of over 8 billion images crawled
from Pinterest, that comes with the visual embedding from (Jing et al., 2015).
We found ~900 million clusters, containing ~5.4 billion (~64%) near-dupe
images444Prior web-scale works detected ~13%, 27%, 34% in their image corpus
(Liu et al., 2007; Wang et al., 2013; Kim et al., 2015).. The most common
cluster size is 2, and average cluster size is 6. The resulting distribution
of near-dupe cluster sizes meets the power law distribution, as shown in
Figure 5(a).

We also conducted a longitudinal study on the percentage of near-dupe images
on Pinterest by image creation time, and observed an increasing near-dupe
ratio over time, in Table 5(b).

(a)

(b)

Figure 6. (a) Distribution of near-dupe cluster sizes on Pinterest dataset.
(b) Increasing trend of the percentage of non-spam images created on Pinterest
that are near-dupe.

##  6\. Applications at Pinterest

The proposed near-dupe image detection system processes all Pinterest images
and handles new images on a daily basis. We show that this system is helpful
in many applications on Pinterest (Jing et al., 2015; Eksombatchai et al.,
2018; Hamilton et al., 2017; Mao et al., 2016), where over 10 billion
recommendations are made a day. Table 4 summarizes the lifts in user
engagement (e.g. pin click/save) in A/B experiments, after using the near-dupe
detection results.

De-duplicate Pinterest Feeds. The near-dupe mapping can be used to filter out
duplicated content in search result pages and the user home feed, illustrated
in Figure 2.

Aggregate Pin Meta Data. Pin meta data (e.g. descriptions, board titles) are
aggregated among pin images from the same near-dupe cluster, and these meta
data are used in generating keywords for search engine optimization (SEO) and
serving pin recommendations on Pinterest. For graph-based recommendation
engines (Eksombatchai et al., 2018; Hamilton et al., 2017), images within the
same near-dupe cluster are condensed into one node, and this reduces the size
of the graph by $2.5x$ and greatly increases the connectivity of the graph.

Canonical Pin Selection. The near-dupe system can be leveraged to select the
most appropriate pin based on the context of users. Given a cluster of near-
dupe images, each image may link to a different pin. For example,
recommendation systems can select the most localized content in the selected
near-dupe cluster.

Table 4. Summary of engagement lift by using near-dupe mapping, measured through A/B experiments on Pinterest. Applications | Engagement Lift
---|---
Volume in SEO Traffic | +33%
De-duplicate Search feed | +11%
De-duplicate Home feed | +7%
Canonical Image Selection | +9%

##  7\. Lessons

(a)

(b)

Figure 7. (a) Ambiguous image pairs. (b) Near-dupe pairs that were incorrectly
classified by earlier classifier.

Near-dupe Criteria. It is hard to define the exact criteria of near-dupe, and
we rely on a human-curated gold standard dataset to capture this, since our
system aims to be used in recommendation systems. However, human judges have
noisy votes - for example, image pairs in Figure 6(a) are classified as near-
dupe by our system but are labeled as non-near-dupe by human judges. Since
images with text overlay often provide little value in the recommendation
system, such false positives are minor.

Image Representation. We find that the semantics of the image is crucial to
near-dupe classification. Global and local descriptors from previous systems
are pixel-based, while the more powerful visual embedding contains both pixel-
and semantic-level signals and best mimics how humans visualize and identify
near-dupe pairs. Image pairs shown in Figure 6(b) are mis-classified by the
previous classifier due to the limitation of the pixel-based descriptors, and
are correctly classified by the latest system. The high precision of the
system is key to enable the real-world applications in Section 6.

Design Choice: LSH. For near-dupe detection task, a key metric for measuring
the efficacy of LSH candidate generation is not $recall@k$ but rather
$recall@distance$. Only neighbors that are visually close enough can be
considered near-dupe; therefore, the aim is to efficiently find neighbors that
fall within a given distance rather than to find all $k$ closest neighbors
regardless of distance. We evaluated LSH recall by classifier selection on 5
billion LSH candidates produced by the near-dupe system; recall of candidate
generation is over 99.99% - less than 0.01% of candidates outside of what LSH
search generates would be detected as near-dupes by the classifier. Thus, LSH
search works well in the near-dupe system.

Synthetic Labels. By optimizing for precision in iterations of this system, we
were able to build a new generation of the system by bootstrapping over
synthetic training labels. The third generation is trained on a large number
of examples labeled by the previous classifier. Section 5.2 shows that a
combination of synthetic training labels and powerful embedded representation
leads to improvements in accuracy characteristics and ability to generalize.

##  8\. Conclusion

This paper presents the evolution of a web-scale near-dupe image detection
system, and shares how we scale it to over 8 billion images with high
precision, e.g. the use of visual embedding to decrease computational load for
candidate generation and selection, improvement of the near-dupe classifier
using synthetic labels, efficient implementation on Spark, and design for
incremental update. We also showcase how this system allows recommendation
systems to greatly improve relevance and density of content. By sharing our
experiences, we hope real-world applications can benefit from de-duplicating
and condensing image content on the Web.

###### Acknowledgements.

We would like to thank Vitaliy Kulikov, Jooseong Kim, Peter John Daoud,
Qinglong Zeng, Andrew Zhai, Matthew Fang, Raymond Shiau, Charles Gordon,
Siyang Xie, Chao Wang, Zhuoyuan Li, Yushi Jing, and Jacob Hanger for their
help throughout the work.

## References

  * (1)
  * Chum et al. (2009a) Ondrej Chum et al. 2009a.  Large-scale discovery of spatially related images.  _IEEE transactions on pattern analysis and machine intelligence_ 32, 2 (2009), 371–377.
  * Chum et al. (2009b) Ondrej Chum, Michal Perd’och, and Jiri Matas. 2009b.  Geometric min-hashing: Finding a (thick) needle in a haystack. In _Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on_. IEEE, 17–24.
  * Chum et al. (2008) Ondrej Chum, James Philbin, Andrew Zisserman, et al. 2008\.  Near duplicate image detection: min-hash and tf-idf weighting.. In _Bmvc_ , Vol. 810. 812–815.
  * Cutting and Pedersen (1990) D. Cutting and J. Pedersen. 1990.  Optimization for Dynamic Inverted Index Maintenance. In _Proceedings of the 13th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ _(SIGIR ’90)_. ACM, New York, NY, USA, 405–411.  https://doi.org/10.1145/96749.98245
  * Eksombatchai et al. (2018) Chantat Eksombatchai, Pranav Jindal, Jerry Zitao Liu, Yuchen Liu, Rahul Sharma, Charles Sugnet, Mark Ulrich, and Jure Leskovec. 2018.  Pixie: A system for recommending 3+ billion items to 200+ million users in real-time. In _Proceedings of the 2018 World Wide Web Conference_. International World Wide Web Conferences Steering Committee, 1775–1784.
  * Erhan et al. (2014) Dumitru Erhan, Christian Szegedy, Alexander Toshev, and Dragomir Anguelov. 2014.  Scalable object detection using deep neural networks. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 2147–2154.
  * Fischler and Bolles (1981) Martin A Fischler and Robert C Bolles. 1981.  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  _Commun. ACM_ 24, 6 (1981), 381–395.
  * Girshick et al. (2014) Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. 2014.  Rich feature hierarchies for accurate object detection and semantic segmentation. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 580–587.
  * Gong et al. (2015) Yunchao Gong, Marcin Pawlowski, Fei Yang, Louis Brandy, Lubomir Bourdev, and Rob Fergus. 2015\.  Web scale photo hash clustering on a single machine. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 19–27.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs. In _Advances in Neural Information Processing Systems_. 1024–1034.
  * Hu et al. (2018) Weiming Hu, Yabo Fan, Junliang Xing, Liang Sun, Zhaoquan Cai, and Stephen Maybank. 2018\.  Deep constrained siamese hash coding network and load-balanced locality-sensitive hashing for near duplicate image detection.  _IEEE Transactions on Image Processing_ 27, 9 (2018), 4452–4464.
  * Indyk and Motwani (1998) Piotr Indyk and Rajeev Motwani. 1998.  Approximate nearest neighbors: towards removing the curse of dimensionality. In _Proceedings of the thirtieth annual ACM symposium on Theory of computing_. ACM, 604–613.
  * Jing et al. (2015) Yushi Jing, David Liu, Dmitry Kislyuk, Andrew Zhai, Jiajing Xu, Jeff Donahue, and Sarah Tavel. 2015.  Visual search at pinterest. In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, 1889–1898.
  * Kim et al. (2015) Saehoon Kim, Xin-Jing Wang, Lei Zhang, and Seungjin Choi. 2015\.  Near duplicate image discovery on one billion images. In _Applications of Computer Vision (WACV), 2015 IEEE Winter Conference on_. IEEE, 943–950.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012\.  Imagenet classification with deep convolutional neural networks. In _Advances in neural information processing systems_. 1097–1105.
  * Lee et al. (2010) David C Lee, Qifa Ke, and Michael Isard. 2010.  Partition min-hash for partial duplicate image discovery. In _European Conference on Computer Vision_. Springer, 648–662.
  * Li et al. (2013) Jun Li, Shan Zhou, Junliang Xing, Changyin Sun, and Weiming Hu. 2013.  An Efficient Approach to Web Near-Duplicate Image Detection. In _Pattern Recognition (ACPR), 2013 2nd IAPR Asian Conference on_. IEEE, 186–190.
  * Lin and Wang (2008) Chia-Chen Lin and Shing-Shoung Wang. 2008.  An edge-based image copy detection scheme.  _Fundamenta Informaticae_ 83, 3 (2008), 299–318.
  * Liu et al. (2010) Hong Liu, Hong Lu, and Xiangyang Xue. 2010.  SVD-SIFT for web near-duplicate image detection. In _Image Processing (ICIP), 2010 17th IEEE International Conference on_. IEEE, 1445–1448.
  * Liu et al. (2015) Li Liu, Yue Lu, and Ching Y Suen. 2015.  Variable-length signature for near-duplicate image matching.  _IEEE Transactions on Image Processing_ 24, 4 (2015), 1282–1296.
  * Liu et al. (2007) Ting Liu, Charles Rosenberg, and Henry A Rowley. 2007\.  Clustering billions of images with large scale nearest neighbor search. In _2007 IEEE workshop on applications of computer vision (WACV’07)_. IEEE, 28–28.
  * Mao et al. (2016) Junhua Mao, Jiajing Xu, Kevin Jing, and Alan L Yuille. 2016\.  Training and evaluating multimodal word embeddings with large-scale web annotated images. In _Advances in neural information processing systems_. 442–450.
  * Simonyan and Zisserman (2014) Karen Simonyan and Andrew Zisserman. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ (2014).
  * Su et al. (2018) Weng-Tai Su, Chih-Chung Hsu, Ziling Huang, Chia-Wen Lin, and Gene Cheung. 2018.  Joint pairwise learning and image clustering based on a siamese cnn. In _2018 25th IEEE International Conference on Image Processing (ICIP)_. IEEE, 1992–1996.
  * Wang et al. (2017) Min Wang, Wengang Zhou, Qi Tian, and Houqiang Li. 2017\.  A general framework for linear distance preserving hashing.  _IEEE Transactions on Image Processing_ 27, 2 (2017), 907–922.
  * Wang et al. (2013) Xin-Jing Wang, Lei Zhang, and Ce Liu. 2013.  Duplicate discovery on 2 billion internet images. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_. 429–436.
  * Witten et al. (1994) Ian H. Witten, Timothy C. Bell, and Alistair Moffat. 1994\.  _Managing Gigabytes: Compressing and Indexing Documents and Images_ (1st ed.).  John Wiley & Sons, Inc., USA.
  * Yao et al. (2014) Jinliang Yao, Bing Yang, and Qiuming Zhu. 2014.  Near-duplicate image retrieval based on contextual descriptor.  _IEEE signal processing letters_ 22, 9 (2014), 1404–1408.
  * Yue et al. (2011) Jun Yue, Zhenbo Li, Lu Liu, and Zetian Fu. 2011\.  Content-based image retrieval using color and texture fused features.  _Mathematical and Computer Modelling_ 54, 3-4 (2011), 1121–1127.
  * Zhang et al. (2018) Yi Zhang, Yanning Zhang, Jinqiu Sun, Haisen Li, and Yu Zhu. 2018.  Learning near duplicate image pairs using convolutional neural networks.  _International Journal of Performability Engineering_ 14, 1 (2018), 168–177.
  * Zhou et al. (2016) Zhili Zhou, Yunlong Wang, QM Jonathan Wu, Ching-Nung Yang, and Xingming Sun. 2016.  Effective and efficient global context verification for image copy detection.  _IEEE Transactions on Information Forensics and Security_ 12, 1 (2016), 48–63.
  * Zhou et al. (2017) Zhili Zhou, QM Jonathan Wu, Fang Huang, and Xingming Sun. 2017\.  Fast and accurate near-duplicate image elimination for visual sensor networks.  _International Journal of Distributed Sensor Networks_ 13, 2 (2017), 1550147717694172\.