13
$\begingroup$

I'm working on an application which requires creating a very large database of n-grams that exist in a large text corpus.

I need three efficient operation types: Lookup and insertion indexed by the n-gram itself, and querying for all n-grams that contain a sub-n-gram.

This sounds to me like the database should be a gigantic document tree, and document databases, e.g. Mongo, should be able to do the job well, but I've never used those at scale.

Knowing the Stack Exchange question format, I'd like to clarify that I'm not asking for suggestions on specific technologies, but rather a type of database that I should be looking for to implement something like this at scale.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I think the structure you want to implement is a "trie" - whether you can find a DB that efficiently works with that structure, or need to roll your own in RDBMS of your choice I cannot say. $\endgroup$
    – Neil Slater
    Jul 23, 2014 at 13:43

3 Answers 3

Reset to default
9
$\begingroup$

See Lucene NGramTokenizer

Are you sure you can't just use lucene or similar indexing techniques?

Inverted indexes will store the n-gram only once, then just the document ids that contain the ngram; they don't store this as highly redundant raw text.

As for finding ngrams that contain your query sub-n-gram, I would build an index on the observed ngrams, e.g. using a second lucene index, or any other substring index such as a trie or suffix tree. If your data is dynamic, probably lucene is a reasonable choice, using phrase queries to find your n-grams.

Improve this answer
$\endgroup$
3
$\begingroup$

Basically for this task you can efficiently use any SQL database with good support of B+tree based indexes (MySQL will suite you needs just perfect).

Create 3 tables:

  1. Documents table, columns: id/document
  2. N-grams table: n_gram_id/n_gram
  3. Mapping between n-grams and documents: document_id/n_gram_id

Create indexes on N-gram table/n_gram string and Mapping table/n_gram_id, also primary keys will be indexed by default well.

Your operations will be efficient:

  1. Insertion of document: just extract all n-grams and insert into document table and N-grams table
  2. Lookup for in_gram will be quick with support of index
  3. Querying for all n-grams that contain a sub-n-gram: in 2 steps - just query based on index all n-grams which contain sub-n-gram from 2nd table. Then - retrieve all corresponding documents for each of these n-grams.

You don't even need to use joins to achieve all these operations so indexes will help a lot. Also if data will not suite in one machine - you can implement sharding scheme, like storing n_grams started from a-n on one server and o-z on another or other suitable scheme.

Also you can use MongoDB, but I'm not sure how exactly you need to implement indexing scheme. For MongoDB you will get sharding scheme for free as it is already built-in.

Improve this answer
$\endgroup$
1
$\begingroup$

I haven't done this before but it sounds like a job for a graph database given the functionality you want. Here's a demo in neo4j.

Improve this answer
$\endgroup$

Your Answer

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

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