# 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. – narek Bojikian Dec 16 '18 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 '19 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. – Aufziehvogel Feb 26 '19 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. – Aufziehvogel Feb 26 '19 at 21:22