Comparing one small dataset with a big dataset for similar records
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.