3
$\begingroup$

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.
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Narek Bojikian
    Dec 16, 2018 at 11:00
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Mar 3, 2019 at 19:17

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – aufziehvogel
    Feb 26, 2019 at 18:58
  • $\begingroup$ 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. $\endgroup$
    – aufziehvogel
    Feb 26, 2019 at 21:22
  • $\begingroup$ @Aufziehvogel, oh, I see, I was confused. Thanks for the explanation! $\endgroup$
    – D.W. ♦
    Feb 26, 2019 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.