Ways to create a huge inverted index

Question

I want to create a big inverted index of around 10⁶ terms. What method would you suggest? I'm thinking in fast binary key store DBs like Tokyo cabinet, voldemort, etc. Edit: I've tried MySQL in the past for storing a table of two integers to represent the inverted index, but even with the first column having a db index, queries were very slow. I think for those situations a SQL database has too much overhead, overhead of transactions, query parsing, etc. I'm searching for what technologies or algorithmic approaches would scale while having good response times and performance. I'm rolling my own solution for research purposes.

Answer 1

Yes, definitely consider Lucene for indexing as its basically the pre-eminent indexer right now. In fact I'm currently considering it for indexing my database of images. The "default" language is Java but it has been ported to other languages such as CLucene for C++, PyLucene for python.

A quick tutorial can be found here.

Answer 2

The question is somewhat vague, so I think the only answer I can give is: use a "generalized inverted index" (GIN index) in PostgreSQL to create whatever kind of inverted index you want. All the hard work is done for you: it uses the write-ahead log for crash safety, internally uses btree structures for performance, and it's part of a mature database management system.

If your problem is full text search, then postgresql's full-text search is already built for you and can use GIN internally.

Answer 3

That is very cool you're trying to roll your own. Perhapstudy up on Lucene's inverted index file format? http://lucene.apache.org/java/3_1_0/fileformats.html