Say I have a set of documents $D = \{d_1, d_2, \dots, d_n\}$ in some natural language.

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}\}$. $\text{words}(d_1)$ is an ordered multiset, but that isn't too important to this problem - we can treat it as a typical set.

Say I have some $K \subset W$.

And there is also $S \subset K$.

I want to efficiently find $E \subset D$ such that:

  1. $\forall e\in E\space \exists\space s: s \in S \land s\in e $ (the documents in E all contain at least one word from $S$).

  2. $\forall e\in E\space (w \in e \implies w \in K )$ (all documents in E only contain words that are in $K$).

My first extremely naive solution to this was simply putting this data into a normalized relational database, and finding the set of documents for a given $K$ and $S$ using a join. This very quickly becomes too slow on a dataset of say, 2 million documents (even with useful indexes added, powerful machine etc). In that database I had a pretty unexciting schema:

Document Sentence Word
id: int id: int id:int
text:string text: string text: string
document_id: int sentence_id: int
index_in_sentence: int

Two avenues I am considering exploring are building a word trie and building an inverted index. I studied undergrad computer science a few years ago but now no longer work in tech, so I don't have any academic or industry people to ask (none of the industry people I discussed this problem with had a good suggestion.)

The problem is different to typical search engine search, which generally doesn't care about the set $K$, instead just looking for matches based on the smaller set $S$.

But I was hoping that anyone reading this can tell me 'the problem you are working on has been solved, just go check out algorithm X or data structure Y', that would be amazing.

Some further context: for my problem, both $D$ and $W$ are fixed ($D$ is several million documents, $W$ is in the order of high 10s or low hundreds of thousands, ie a natural language). $S$ might be from 10-100 in size typically, and $K$ might be from 50-5000 typically.

But I want to build a data structure (whether in postgres, neo4j, reddis, or even just in some application language like C or Python) that I can query with a variety of $K$ and $S$ values, and quickly find the subset of $D$ that satisfies the above constraints.

I am not looking for programming language or database choice level solutions here, just any pointers on how to efficiently do this kind of search. Of course, if it happens that some programming or database paradigm is a great fit, please let me know.

Note: I have found a rather similar question with some suggested solutions here.

I am going to investigate these options, but in the mean time I welcome any pointers!


1 Answer 1


You are trying to compute the set

$$E = \{e \in D \mid e \subseteq K \land e \cap S \ne \emptyset\}.$$

There is a naive algorithm. Store $K,S$ in a hashtable (using a hash function that maps each word to its hash value). Then for each $e \in D$, iterate through the words of $e$, look them up in the hashtable for $K$ and $S$, and check whether it satisfies the conditions; if it does, include it in $E$. If you prefer a database-style approach, you can probably express this using joins (e.g., a join between $e$ and $S$, a join between $e$ and $K$), and use any join algorithm you like: a hash join, a sort-merge join, etc.

I imagine you're hoping for a faster algorithm, whose running time is sub-linear in $|D|$. I don't hold out a lot of hope for such an algorithm. You're basically looking for the ability to perform subset queries, which I think might be hard. See, in particular, state of the art of subset, set containment and partial match queries, Data structure for testing all subsets of a query for membership, Best data structure for queries about subsets?, Finding containing sets in a set of sets. I suspect you may find that none of them are that much better than the naive algorithm.

  • 1
    $\begingroup$ Hello. Thank you for the pointers! And yes, that naive algorithm is what I had implemented in SQL. It started getting pretty sluggish on larger datasets. I have just read this paper: Data structure set-trie for storing and querying sets: Theoretical and empirical analysis: pubmed.ncbi.nlm.nih.gov/33566827 I am going to explore using the data structure they describe as a solution. If I have success (or notable failure) I will report back here for the benefit of future readers. Thank you also for that extremely useful set of links, I will explore those too. $\endgroup$ Commented May 18, 2022 at 23:43

Your Answer

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