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)| < t$$

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:

1. 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
2. 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.
• One way is to sort all sets lexicographically and use sliding window (two pointers) to compare two sets in linear time of comparisons in the size of the sets. I don't know if you can achieve an asymptotically better runtime for a deterministic algorithm. But since heuristics work for you as well that might not be the best way to go. – narek Bojikian Dec 16 '18 at 11:00