I would like to store the frequencies with which words co-occur with each other over a variety of contexts in a large (> 1 billion tokens) text corpus. I need to store the word pair, the type of co-occurrence (e.g. word1 in the same sentence as word2, word1 in the same paragraph as word2), and some metadata about the text in which the co-occurrence was found, (e.g. year, author, publisher). So a single row might look like:

word1     word2   count decade  publisher   author        context_type
nuclear   danger   22    1980s    NYT      Mary Smith      paragraph

The frequencies will be sparse and Poisson distributed. I would then like to be able to query the data by date ranges, or groups of authors (for example), aggregating the counts of the results.

I have little experience with databases and am not sure what to use. Do I need related SQL tables (e.g. with the book metadata in one table and word data in another), or a simple flat NoSql solution? The vocabulary is about 50,000 words, so if every word-word co-occurrence was observed there would be 2.5 billion rows even without the metadata (I think). But probably most of them won't be observed. This makes me think maybe a graph database is a possible solution. Is there a good cloud solution on AWS or google maybe?

  • What do you consider a "context"? – alk May 20 at 17:23
  • Have you benchmarked a "dumb" 1-table SQL solution with data (dummy or real) yet? 2.5 billion rows is a good amount, but isn't unmanageable. It may be that you're foreseeing performance issues where there aren't any. – Delioth May 21 at 16:40

Do I need related SQL tables (e.g. with the book metadata in one table and word data in another)

A separate table for words can be used, but it is probably not necessary. A "word" is identified by all of its letters, it has no additional metadata, and for your use case, you probably don't have the requirement to correct individual word spellings after the frequency table was built. A word table may be of help to save some disk space, for the price of requiring some additional JOINs for getting the actual letters, so it is just a trade-off between speed and disk resources.

(Note that according to this source, the average number of letters in an english word is less than 5, so even if words in the frequency table are replaced by 32 bit integer IDs pointing into a word table, I guess the potential savings are not too high. But this also depends a lot on how the specific DB will store strings internally.)

A separate table for books makes definitely sense. Publisher, author, and decade will probably be stored there (and maybe more information about the book like its title). Word pairs will occur in several different books, so there is actually an n:m relationship between word pairs and books, which means you will need an additional link table. If you need this, you can also store the count of the specific word pair for a particular book in that table.

I would also consider to give the context type a separate table as well. This leads to a classical star schema, which is often used for OLAP databases:

Word pair table:

id   word1     word2   
123  nuclear   danger    

Context_type table:

id   type
1  direct_neighbours
2  sentence
3  paragraph

Book table

id   title           publisher author
456  'Lorem Ipsum'   NYT       Mary Smith

and finally the Frequency table (the "star center") like

book_id   word_pair_id  context_type_id  count
456       123           2                11

This makes me think maybe a graph database is a possible solution

I am not an expert on this, but I guess a graph database can be helpful if you want to interpret the words as vertices of a graph, and each word pair as an edge within this graph, and you have requirements which involve specialized operations like graph traversal. But for the query examples you gave in your question, I would try a relational database first and see how far it gets you (something lightweight like Sqlite would be my first choice).

If you need a more specialized system, an OLAP database or OLAP engine (on top of a relational DB) maybe the right tool for the job. You will find some systems just by googling for this keyword.

  • 1
    I think for an OLAP solution, it makes sense to break out the authors into a separate table. There are likely multiple authors that share the same name. It's also the case that often books are written by more than one author which would indicate an additional table for the many-to-many relationship. – JimmyJames May 20 at 16:23
  • 1
    @JimmyJames: I agree partially. For OLAP, normalization is usually not as helpful as for classical OLTP applications, quite the opposite. But I guess one has to know the exact requirements here and test different schemas to find out what works best. Problem here is, when a book is written by more than one author, it will be not possible to separate the word count (or word pair count) by author and book, so we actually don't know if the OPs idea of querying "by author" will make much sense. Maybe it is just not-so-well chosen example. – Doc Brown May 20 at 17:21
  • 1
    Sorry, I'm not sure I follow. The main reason I suggest breaking out authors is that you could have multiple authors with identical names. An author table would allow for disambiguation. Would you manage the multiple author situation with more rows in the Frequency table? I have to admit that OLAP design isn't something I'm totally comfortable with. – JimmyJames May 20 at 17:26
  • 1
    @JimmyJames: I would recommend to the OP to check which query requirements really exist, and if querying for a separate author is really a requirement, given the fact one cannot easily separate the words written by one of multiple authors in one book. Then, and only then I would think about making the schema more complex. – Doc Brown May 20 at 17:29
  • 2
    @JimmyJames: your suggestion leads to a so-called snow-flake schema. That can be also a valid option, but I would recommend to the OP (or anyone who is doing something similar) to read the "Benefits" and "Disadvantages" sections of that Wikipedia article carefully before making a decision here. – Doc Brown May 20 at 17:38

I don't think you need any databases or anything fancy like cloud computing. Computers are fast, and you can wait a little bit for it to process.

Do you really want to know count of every single combination of words at once or do you want to query just some of them?

Here is the solution for knowing all of them: You can make a map of (word1, word2) --> (countSentence, countParagraph) where word1 comes before word2 alphabetically. We will refer to this data structure as WordCount.

Map WordCount; For each paragraph Array UniqueWordsSeenInParagraph For each sentence For each combo in sentence ++countSentence in WordCount add word to UniqueWordsSeenInParagraph For each combo in UniqueWordsSeenInParagraph ++countParagraph in wordCount

You could write this in c or java. You might, depending on size want to write results to a file. There are some techniques you could use if you have memory constraints. Let me know how much memory and disk space you have, and we could do calculations.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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