Comparing one small dataset with a big dataset for similar records

Question

I create a varying small dataset (dataset: X) with 500 records in each query. Everytime I need to compare the dataset with a bigger one (dataset: A) (15 milion records) to find similar (or semi-silmilar) values from three different columns. The values are either one word or a sentences. My algorithms is like this:

1. make a vector of words in each record in both datasets
2. with a for loop, search for similarities over the big dataset (e.g. with tfidf). That means each record from the small dataset should look for possible similarities over the big dataset.

However, the problem is searching a big data is very slow. Is there any efficeint way to solve this problem? Thanks

Answer 1

A way to speed up this process is to preprocess the large dataset, the goal being to store the documents from A in a way which avoids a lot of useless comparisons.

• Store each document from A in an inverted index $m$, so that for any word $w$ $m[w]$ is the list of all documents in A which contain word $w$ (note that a document can appear several times in this data structure).
• When comparing a new query against $A$, instead of iterating through all documents in $A$ just compare against the subsets which have at least one word in common, i.e. $m[w]$ for every word $w$ in the query.

Couple remarks:

• Normally stop words would be excluded from the keys since they appear everywhere and they are not relevant for matching.
• The key doesn't have to be a single word, it could also be an n-gram (or several n-grams) or even several words in case it fits in memory.

This kind of problem is frequent in the task of record linkage.