# 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$$

$$\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:

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. Dec 16, 2018 at 11:00
• I presume the 100k refers to the typical number of words per $words(p_j)$ set. Could you edit the question to show the typical number of words per $words(d_i)$ set, too?
– D.W.
Mar 3, 2019 at 19:17

• Nice idea, but I think the LSH part will not work with my approach. The words of a person ($words(p_j)$) will usually be a much larger set than the words of a document ($words(d_i)$). Basically, it's the vocabulary you know vs the words a text contains. I want to see texts from which I know all but ~10 words. I think LSH only works if the documents (in my case: user vocabulary compared document) should be very similar according to Jaccard distance. Hashing might still be an idea to reduce the complexity for each comparison operation. Feb 26, 2019 at 18:58
• If I'm not wrong set difference can be small even if $words(p_j)$ is much larger than $words(d_i)$. Consider $words(p_j) = \{i, do, know, a, lot, of, words, because, am, learning, so, much\}$ and $words(d_i) = \{ here, are, words \}$. Then $words(d_i) \setminus words(p_j) = \{ here, are \}$. The opposite $words(p_j) \setminus words(d_i)$ will be very large in almost all situations of my use case. Feb 26, 2019 at 21:22