4

I have a use case where I have access to a large database with many documents (millions+). I want to build functionality such that, when I want to add a new document to that database, I first want to scan the database for potential duplicate documents. Documents may differ in file type and other information (i.e. one is a digital copy, while another is a hard copy that was scanned in via a printer) while still materially being the same document, so I unfortunately can't rely on metadata or similar.

In order to determine if a document is a duplicate, I plan to use some weighted combination of NLP (via something like spaCy) to compare document similarity, comparison of word distributions (both the simple word distribution and something like TF-IDF), and other relevant metrics.

In order to actually find potential duplicates for a newly uploaded document, I can't think of any way to avoid scanning every document in the database, comparing one-by-one, and tracking the one with metrics that matched most closely.

Thoughts I've had for optimizing this:

  • I know indexing can often be used to speed up search operations, but to my understanding that's only good for searching for a specific value in a specific column. I don't think it's a good fit, as I'm trying to essentially take a weighted average of each metric and report which are closest. I guess I could index every column; could this potentially be worth it, or would the constant reindexing be a huge performance penalty?
  • I've been thinking of using a clustering (unsupervised machine learning) model in order to cluster similar documents together, then try and use the clusters it gives me to try and determine which cluster the new document would fit in, then just search in there, but I'm getting caught up in the details. I'm sure this would be a practical approach for finding preexisting duplicates in the database, but is this practical to do every time a new document is added to the set (i.e. could it be used to speed up the actual search through the database)? I'm not too well-versed in machine learning, so I'd appreciate some input on this.

So ultimately - is there a way for me to structure my database such that I don't need a linear search in this scenario?

2
  • 3
    One way would be to create a signature of each of your documents. Then you can compare the signature of your new document with the signatures of the existing documents. Only those documents with matching signatures would be textually compared. A signature can be as simple as a Base64 string of the first letters of every word or as complicated as the word frequency of every four letter and above word. – Gilbert Le Blanc Jun 17 at 18:36
  • @GilbertLeBlanc Unfortunately, I'm not sure that's an option, as identical documents could have slightly different textual content due to human error (i.e. scanning it in wrong and OCR then reads the text inaccurately), resulting in a different signature even for identical documents. However, it does give me some ideas about something like indexing based on the letter distribution and only fully comparing things with similar letter distribution, as odds are they will be at least similar. I'll need to think on it; thanks for the idea! – kaladin Jun 17 at 19:53
4

You could define an index on each measure, query each to find the few documents that are closest, then build the intersection of these various results. That would turn a size-of-data comparison into a (number of measures) x (width of search in a measure). This is likely to be smaller than the number of rows for a sensible number of measures.

Depending on the DBMS and how good your SQL-fu is you may even be able to convince the query processor to perform these index read and then inner join the sub-results together to produces the intersection.

One big snag with this is outliers. Say we define 20 measures. An in-coming document matches an existing document exactly in 19 of these 20 but is out-of-range on the last. The existing document will never make it into the result even though a human would likely say the two matched. To avoid that you'd have to define degree of correlation in the index matches, and then you're back to size-of data operations again.

What's wrong with doing the usual vector-space comparison?

Intel reckons a modern server chip can do a few hundred gigaflops or so. Let's call it 10^11 floating point calculations per second. To compare one document to another on 20 measures using Euclidean distance would need 80 computations. Let's call it 100. That's 10^9 comparisons per second. So to compare to 1M existing documents would take 10^-3 seconds, or 1 millisecond. Let's knock off a few more zeros because data has to move around inside chips. How often will you be adding documents? How many scanners do you have & how long does OCR take to process? Can you live with a duplication check taking a bit less than one second per document.

Taking the Euclidean approach farther, if your DBMS supports a geometry data type you could choose the two or three most selective measures and define a spatial index on those. That should efficiently reduce the search of 1M+ existing documents down to a level where the full vector search is tractable.

1
  • You've got some really interesting ideas in here - thank you for the writeup. The outlier problem, and other bits and pieces of your response, are definitely something I've been heavily thinking about. I also read up on spatial databases and there are lots of cool ideas there I may experiment with. I'll need to test out some of this on my database instance and see how the different approaches perform. This has given me a great start - thanks! – kaladin Jun 18 at 19:09
2

As a general hint: Use the fastest and easiest metrics to rule out the most of the documents, until you reach a document set that can be tested 1 to 1.

An idea would be the following: As you only want to find duplicates and not similarities, something very simple like storing the first 100 and the last 100 characters of a document in two separate columns helps to pre-select potential candidates. (100 is a random number, that you can adjust)

Then you can run a string similarity check like Levenshtein-Damerau with an appropriate threshold (see for example Optimizing the Damerau-Levenshtein Algorithm in TSQL) on these 2 columns with the new document's start and end strings. If the documents are the same then the strings should match to the most part.

I don't know which performance you expect/need. I ran the above UDF on 2.25 million records of max. column length 50 and different runs took me 20-40 seconds on my desktop computer.

1
  • This is a really interesting idea - thank you for the write-up. The answers here have led me to definitely consider something signature-based (which your "first 100/last 100" characters essentially is), but with a degree of correlation rather than expecting exactly matching signatures, and your answer has a lot of useful overlap. I think my current concept is to index the column with TF-IDF data, then only fully check documents with similar enough TF-IDF data (i.e. 90% accurate on 90% of dimensions). We'll see how efficient that actually ends up being, but this is a start. Thanks! – kaladin Jun 18 at 18:55
2

Near duplicate classification models tend to have high runtime overhead. A brute-force application of such a classifier over a large document database is impractical. One way to handle large-scale scenarios is to combine the near-duplicates classifier with a similarity search engine. The basic idea: index vector representations of the documents, use the index to retrieve a subset of similar documents, and apply near-duplicates detector over that subset.

Here is a deduplication example using a similarity search service and duplicates detector to handle millions of document vector embeddings.

(Mind that I am a co-author of that example.)

0
1

I've ended up using ElasticSearch's More Like This query for my use case. It offers text similarity queries that use TF-IDF as their behind-the-scenes metric, which have been both extremely fast and very accurate for me.

The project also involves doing some preprocessing and clustering on the data, which will be used to speed up the data lookup further by only focusing on elements within the same cluster for the duplicate search. I anticipate ElasticSearch will be 90% of the reason for the fast querying I'm looking for, but some of the clustering I mentioned will likely find its way into the end product.

The project is an iterative process, so this is subject to change, but it seems like a very good fit.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.