Algorithm / data structure to filter documents by number of missing words Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)?

Problem Definition

We have a list of documents $D = \{d_1, d_2, \dots, d_n\}$. Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\text{words}(d_1) = \{w_1, w_5, w_{7}\}$.

Each person $p_j$ also has a set of words $\text{words}(p_j)$.

The goal is to find all documents where the length of the set difference between both is smaller than a threshold $t$:

$$
|\text{words}(d_i) \setminus \text{words}(p_j)| &lt; t
$$

$\text{words}(p_j)$ will in most of the cases be much larger than $\text{words}(d_i)$ (i.e. there will be a lot of words in the person's set that are not in the document's set).

Complexity

The sizes will probably be around these numbers:


documents: millions or tens of millions of documents
words: around 100k different words (per independent set)
person: between 1 and 1000 people


Use Cases

My actual use case for this is to retrieve foreign language texts where I do not know all the vocabulary, yet. I have a list of words that I know for each language and I want to find documents from a collection of texts that contain between 1 and 10 words that I do not know, yet. That way, I expect to be able to find texts that I can understand while also improving my vocabulary skills.

Another use case might be finding recipes that match a user's stock at home. In this case, you might want to find documents (recipes) that contain between 0 and 2 missing items, so that the user either has to buy nothing or can replace the few missing items with something similar.

My current approach

While it is easy to find documents that have an overlap of at least $t$ words, I found the opposite (find documents that have a difference of at most $t$ words) quite complex. At the moment I fell back to a two stage approach:


I first filter documents by the length of the text and the length of the sentences and compare them to an average value I store for myself
In the filtered list I then loop in my code and calculate the set difference for each document and delete all that have more than $t$ unknown words.
Use a locality sensitive hash, like MinHash or SimHash.

You could also sort the set of words, extract shingles, and hash them using MinHash or something similar.