Duplicate detection introduction

Before we discuss the details of duplication detection and similarity analysis in Lingo4G, it's worth taking a look at a toy example that demonstrates the difficulties of the problem itself as well as introduce the key concepts used later in this chapter: features, hash grouping and pairwise similarity.

Let's imagine with following situation:

There is a parent-teacher conference at a large school. Many kids, teachers and their parents or legal guardians showed up:

🧔🏼 👵 👨🏼 👵🏻 👧🏽 👵🏼 👨🏽‍🦱 👴🏽 🧓🏻 👵🏽 👩🏼‍🦱 👵🏿 🧑🏼 👵🏾 👦🏿 👱🏼 👨‍🦰 👴 👱 👨‍🦲 👨🏽‍🦲 👴🏻 🧑🏿 👨‍🦱 👩🏾‍🦱 👴🏼 👩🏾 👨🏾‍🦰 👨🏾‍🦱 👴🏾 👨 👧 🧓🏾 👴🏿 👨🏾‍🦲 👦🏼 👨🏿 🧓 👧🏿 🧑 👩🏼 🧓🏼 👧🏼 👨🏽‍🦰 👨🏽 🧓🏽 👱🏾 👨🏻‍🦱 👨🏻‍🦰 🧓🏿 👦🏻 🧑🏾 👱🏻 👩 👧🏾 👩‍🦰 🧑🏽 👩🏻 🧔🏾 👱🏿 👨🏻‍🦲 👩🏽 👨🏻 👩🏾‍🦰 👦 👩🏾 👨🏾 👧🏻 👦🏾 👩🏿 👨🏼‍🦰 👦🏽 🧑🏻 👩🏻‍🦰 👨🏿‍🦰 🧔🏻 👩🏻‍🦲 👩🏼‍🦰 👨🏼‍🦱 👩🏿‍🦱 👩🏽‍🦲 👩🏽‍🦰 👨🏿‍🦱 👩‍🦲 👩🏿‍🦲 👩🏿‍🦰 👨🏼‍🦲 👩🏼‍🦲 🧔🏻 👩‍🦱 👨🏿‍🦲 👩🏾‍🦲 🧔🏽 👩🏻‍🦱 👱🏽 🧔 🧔🏿 👩🏽‍🦱

The problem to consider is this:

Are there any two (or more) people that are lookalikes?

The first thing to realize is that the definition of a "lookalike" is really vague. Say, a stunt double should be very similar to the actor they substitute on the set (but they're rarely identical). This is hardly a useful definition: we need a more concrete, measurable notion of pairwise similarity between two objects.

API request structure

Lingo4G's document​Pairs:​duplicates request stage is responsible for finding similar document pairs. There are three key elements of this request and they correspond exactly to the description in our toy example above. Here is an example request structure:

{
  "type": "documentPairs:duplicates",

  "query": {
    ...
  },

  "hashGrouping": {
    ...
  },

  "validation": {
    ...
  }
}
    

The query property specifies which documents from the entire index should be included in the pairwise similarity search. You can use the query to, for example, restrict duplicate searches to just a range of dates, a given author or use any other valid query.

The hash​Grouping property configures preliminary document grouping: how document features are defined, how their hashes are computed and how they're compared.

Finally, the validation element provides the way of computing the final pairwise document similarity for any pair of documents that have a hash collision. This element also includes the thresholds of the similarity range which form the stage's result.

Every duplicate detection request will have the three elements described above. All the different intents and applications of this request stage are expressed by varying the source of features, how hashes are computed and how the pairwise similarity is defined.

Let's dive straight into a real-life example to discuss the internal structure of each of these primary building blocks.

Finding identical duplicates

Let's find pairs of Arxiv publications with identical titles published between 2015 and 2017. Lingo4G comes with a ready-to-use example dataset descriptor (which also downloads a preprocessed Arxiv data dump). Run the indexing command and the server (this will take a while):

l4g index  -p datasets/dataset-arxiv
l4g server -p datasets/dataset-arxiv

Then open the sandbox API editor (it should be available at https://localhost:8080 and enter the request below.

{
  "components": {
    "sourceFields": {
      "type": "fields:simple",
      "fields": [
        "title"
      ]
    }
  },

  "stages": {
    "similarPairs": {
      "type": "documentPairs:duplicates",

      "query": {
        "type": "query:string",
        "query": "created:[2015 TO 2017]"
      },

      "hashGrouping": {
        "pairing": {          
          "maxHashGroupSize": 200
        },
        "features": {
          "type": "featureSource:values",
          "fields":{
            "type": "fields:reference",
            "use": "sourceFields"
          }
        }
      },

      "validation": {
        "pairwiseSimilarity": {
          "type": "pairwiseSimilarity:featureIntersectionToUnionRatio",
          "features":{
            "type": "featureSource:values",
            "fields":{
              "type": "fields:reference",
              "use": "sourceFields"
            }
          }
        },
        "min": 1,
        "max": 1
      },

      "output": {
        "explanations": true
      }
    }
  }
}

The three main request blocks are highlighted in the request above. How do they work together?

1. The query property defines the documents among which to find duplicates:

   "query": {
     "type": "query:string",
     "query": "created:[2015 TO 2017]"
   }

   We use the query:​string component and provide a range query that matches documents created between 2015 and 2017.

2. The hash​Grouping property configures preliminary grouping:

   "hashGrouping": {
     "pairing": {
       "maxHashGroupSize": 200
     },
     "features": {
       "type": "featureSource:values",
       "fields": {
         "type": "fields:reference",
         "use": "sourceFields"
       }
     }
   }

   The max​Hash​Group​Size property declares the maximum cardinality of a hash-colliding group: groups containing more than this number of documents will be omitted from pairwise comparisons. Remember the number of such comparisons grows exponentially so this is a safety limit to prevent the algorithm from slowing down on accidental very large collision groups. In our case it is unlikely that more than 200 papers in arxiv share an identical title, so it's a reasonable setting.

   The features property specifies a feature source. Here, we use entire field values as the source of features from which hashes are then computed. This means each unique title will have a hash value that will collide with all other documents with the same title. We use a reference to the source​Fields component to specify which fields should be actually used as a source; we do it because the same set of fields is used from more than one place of the request. Here is the definition of this reusable component:

   "components": {
     "sourceFields": {
       "type": "fields:simple",
       "fields": [
         "title"
       ]
     }
   }

3. Finally, we declare pairwise document similarity for documents that ended up in the same group after preliminary hash grouping:

   "validation": {
     "pairwiseSimilarity": {
       "type": "pairwiseSimilarity:featureIntersectionToUnionRatio",
       "features": {
         "type": "featureSource:values",
         "fields": {
           "type": "fields:reference",
           "use": "sourceFields"
         }
       }
     },
     "min": 1,
     "max": 1
   }

   The key element here is pairwise​Similarity for which we use the feature​Intersection​To​Union​Ratio implementation. This type of pairwise similarity computes a set of unique features for each document and then divides the number of features they have in common by the total number of unique features. We declare the source of features in an identical way as for hash grouping (entire values, referencing the same set of fields) so either the two documents will have a similarity of 1 (the same value in the title field) or 0 (accidental hash collision from different values). Since so, we also declare the threshold of similarity values we're interested in as [1, 1] (min and max properties above, intervals boundaries are inclusive).

   Note that we could declare a different source of features for hash grouping and for the pairwise similarity computation. Later on, we show where such a set up can be useful.

Once the above request executes, you should see a screen similar to:

The response of our similar​Pairs stage is a JSON structure with a few nested elements. It is very often useful to retrieve not just the result of the request but also gain some insights into the internal stages of the algorithm. This is the purpose of the leading diagnostics block that contains some human-readable information which can be used to tune (or diagnose) similarity requests. For example:

"Computing feature hashes": {
  "Features": "entire values from field: title",
  "Documents": "50,434",
  "Hash count": "50,434"
}

This section shows how many hashes were computed (Hash count) from how many documents in scope (Documents) and what the source of features was ( entire values from field:​ title). In this example these numbers are the same, but only because we take entire values from the title field and the title holds a single value only. We will see later how we can compute hashes from sub-fragments of a field (such as sentences, word n-grams or even individual terms).

In the next section, we can gain some insight into hash grouping:

"Aggregating results": {
  "Hash collision groups": "7",
  "Skipped large hash collision groups": "0",
  "Pairwise hash comparisons": "9",
  "Candidate pairs": "9",
  "Out of scope pairs": "0"
}

We had Hash collision groups collisions between (out of the total of all computed feature hashes). No group was larger than the max​Hash​Group​Size threshold we specified in the request because Skipped large hash collision groups is zero. These hash collision groups further result in a number of pairs promoted for direct pairwise similarity computation (Candidate pairs block).

The Computing hash collisions block is a very low-level diagnostic considering an implementation detail, and we will skip it for now. A more useful and interesting information is at the very end:

"Validating pairs using pairwiseSimilarity:featureIntersectionToUnionRatio [entire values from field: title]": {
  "Pairwise similarity function": "pairwiseSimilarity:featureIntersectionToUnionRatio [entire values from field: title]",
  "Similarity thresholds": "[1.0, 1.0]",
  "Pairs passing": "9"
}

The Pairs passing element indicates the number of document pairs that passed the thresholds specified in the pairwise​Similarity element above. This means that out of all candidate pairs with a hash collision, we ended up with this number of document pairs that actually had the same title — this is exactly what the pairs block contains: an array of objects each describing a pair of documents similar to our notion of pairwise similarity. Here is an example pair:

{
  "pair": [
    86,
    226443
  ],
  "similarity": 1,
  "explanation": "Documents share 1 out of 1 distinct feature (entire values from field: title)."
},

The pair sub-element contains exactly two (Lingo4G-internal) document identifiers. The similarity between these two documents is 1 and the (optional) element explanation precisely describes how the similarity was computed: Documents share 1 out of 1 distinct feature (entire values from field: title).

Many applications will require not just the internal identifiers of duplicate documents but also additional information, such as field values. To accomplish this, we need to combine the document​Content stage, which retrieves document fields, with documents:​from​Document​Pairs, which converts document pairs into a flat list of documents. All we need to do then is to add the document​Content stage to our request and provide our similar​Pairs stage, converted to a flat list, as source of documents for content fetching:

"content": {
  "type": "documentContent",
  "limit": "unlimited",
  "documents": {
    "type": "documents:fromDocumentPairs",
    "documentPairs": {
      "type": "documentPairs:reference",
      "use": "similarPairs"
    }
  },
  "fields": {
    "type": "contentFields:simple",
    "fields": {
      "id": {},
      "title": {},
      "author_name": {},
      "created": {},
      "updated": {},
      "abstract": {
        "maxValueLength": 250
      }
    }
  }
}

A response to such an extended query contains both similar pairs of documents and their field values. Client-side code needs to intersect these structures manually, but this should not be a problem. Here is how the Explorer displays the result of such a combined request:

The title of these two documents is identical (as is the abstract) but the date of document submission and the author list are different. Whether this is coincidental or not is irrelevant now, but it leads to an important question how to construct a similarity request for when the text in two documents is almost the same but not quite identical. This problem is called near-duplicate detection, and we will discuss it next.

Finding near-duplicates

We will modify the request for finding identical arxiv paper titles, provided in the previous example. This time, we want to search for pairs of documents where the title is almost the same but not quite.

Perhaps the first thing we'd have to do is redefine pairwise document similarity. We want a "contiguous" measure of similarity between document titles: one that would distribute the score between identical titles and very different titles over some predetermined range of numbers. Many strategies can be used here, but we can start with something that is intuitive: let's use the words of each title as features. A normalized similarity score based on such features could be the number of unique words the two titles have in common, divided by the total number of unique words in both. Here is an example:

The number of unique terms for both documents is 6 (lucy, had, a, blue, gray, cat). The number of terms in common is 4 (lucy, had, a, cat). The pairwise similarity between these two documents is therefore 4/6 ≈ 66%. Here is the definition of such a pairwise similarity in Lingo4G API:

"validation": {
  "pairwiseSimilarity": {
    "type": "pairwiseSimilarity:featureIntersectionToUnionRatio",
    "features": {
      "type": "featureSource:flatten",
      "source": {
        "type": "featureSource:words",
        "fields": {
          "type": "fields:reference",
          "use": "sourceFields"
        }
      }
    }
  },
  "min": 0.9,
  "max": 0.999
},

Note we use the same similarity implementation as previously (feature​Intersection​To​Union​Ratio) but this time we restrict the score threshold to be between 0.9 and 0.999 (we're not interested in identical duplicates but everything close to being identical is interesting).

The source of features is a bit more complex and requires a comment. We use the feature​Source:​words implementation type to extract a list of individual words from the title field (via the source​Fields reference). However, this implementation produces composite features — higher-level features that contain smaller features. In this particular case, feature​Source:​words produces a single feature from each field value; each such feature internally contains an array of smaller features representing individual words. If we used this implementation directly as input to the pairwise similarity implementation (feature​Intersection​To​Union​Ratio), it would be no different from using entire titles because individual words are "enclosed" by the composite feature and it is those top-level features that would be compared. We need to "open up" composites and get access to individual features contained by the composite. This is precisely what the top-level feature​Source:​flatten does.

Now that we have the pairwise similarity, we need to decide which features to use for preliminary grouping. Previously, we used the entire title but this will no longer work: if two titles differ by even a single word, the hash code of a feature constructed on top of such entire value would be (with high probability) different and the two documents would never make it to the same group of candidates for pairwise comparisons.

A different try would be to copy-paste the same feature source we used for the pairwise similarity above — (flattened) words. This approach does work but it is very, very inefficient. Single words are not unique: the same words occur in many, many titles and their hashes would (in the majority of cases) create collision groups close to, or even exceeding, the max​Hash​Group​Size threshold.

Here is the diagnostic output from a request that uses flattened words for preliminary grouping but restricts the documents to just those having the word "solar" in the title:

"Computing feature hashes": {
  "Features": "flattened composites of words from field: title",
  "Documents": "42,276",
  "Hash count": "367,799"
},
"Aggregating results": {
  "Hash collisions": "9,539",
  "Pairwise hash comparisons": "5,290,430",
  "Candidate pairs": "4,975,598",
  "Skipped large hash collision groups": "359"
},
"Validating pairs using pairwiseSimilarity:featureIntersectionToUnionRatio [flattened composites of words from field: title]": {
  "Pairwise similarity function": "pairwiseSimilarity:featureIntersectionToUnionRatio [flattened composites of words from field: title]",
  "Similarity thresholds": "[0.9, 0.999]",
  "Pairs passing": "25"
},

The number of documents matching "solar" is 42,276 and the number of hash collision groups is a mere 9,539, but each such collision group contained many elements and the number of candidate pairs shot up to almost 5 million! In fact, 359 collision groups were skipped entirely because they contained too many candidates to even consider. In the end, out of the 5 million candidate pairs checked, we got an output of 25 document pairs that met the similarity threshold criteria. The result is accurate, but we made a lot of needless work.

There is clearly a need for a more intelligent feature selection strategy for preliminary grouping. Features should be unique enough to redistribute potential candidates into small groups with documents that have a high probability of meeting the pairwise similarity criteria.

In this example, we will use overlapping, fixed-length sub-sequences of words. This technique is known as shingling or term n-grams. Consider 3-grams from our example sentences above:

The number of n-grams is approximately the same as the number of terms, but n-grams are typically much more unique to the document they come from. It is very likely to encounter a term "a" in any English text but quite infrequently we can find "a blue cat".

Longer n-grams will be more globally unique but if we make them too long, we run a risk of failing to group shorter titles or titles that have changed words scattered around. In the example above, the two documents do have shared 3-grams ("lucy had a", "had a blue") but they don't share any 4-grams. This tradeoff between possibly "missing" a similar document pair because n-grams are too long and having too many non-unique enough n-grams is difficult to solve. It requires some domain knowledge (How long are document fields? What is the content being analyzed? What is the cost of missing a similar pair vs. waiting for too long?) and perhaps a few rounds of trial-and-error on actual documents.

Continuing the example, we will pick 5-grams of words as features for preliminary grouping, leaving pairwise similarity defined on top of individual words. Below is the full API request. Note the highlighted preliminary grouping block:

{
  "components": {
    "sourceFields": {
      "type": "fields:simple",
      "fields": [
        "title"
      ]
    }
  },

  "stages": {

    "similarPairs": {
      "type": "documentPairs:duplicates",

      "query": {
        "type": "query:string",
        "query": "created:[2015 TO 2017]"
      },

      "hashGrouping": {
        "pairing": {
          "maxHashGroupSize": 200
        },
        "features": {
          "type": "featureSource:ngrams",
            "window": 5,
            "source": {
              "type": "featureSource:words",
              "fields": {
                "type": "fields:reference",
                "use": "sourceFields"
              }
            }
        }
      },

      "validation": {
        "pairwiseSimilarity": {
          "type": "pairwiseSimilarity:featureIntersectionToUnionRatio",
          "features": {
            "type": "featureSource:flatten",
            "source": {
              "type": "featureSource:words",
              "fields": {
                "type": "fields:reference",
                "use": "sourceFields"
              }
            }
          }
        },
        "min": 0.9,
        "max": 0.999
      },

      "output": {
        "explanations": true
      }
    },

    "documents": {
      "type": "documentContent",
      "limit": "unlimited",
      "documents": {
        "type": "documents:fromDocumentPairs",
        "documentPairs": {
          "type": "documentPairs:reference",
          "use": "similarPairs"
        }
      },

      "fields":{
        "type": "contentFields:simple",
        "fields": {
          "id": {},
          "title": {},
          "author_name": {},
          "created": {},
          "updated": {},
          "abstract": {
            "maxValueLength": 250
          }
        }
      }
    }
  }
}

Once run, the output should display pairs of documents with similar but not identical titles. Here is an example:

It's clear these titles fulfill our initial goal: they're very similar but not identical. If you imagine the same kind of similarity search over a long text field (for example the abstract in arxiv data), it's easy to imagine the difficulty in spotting such differences, especially when the similarity between fields is high. Luckily, Lingo4G has a built-in stage that can highlight duplicated text blocks found in a pair of documents and this is what we will do next.