3 ms·
The basic data structure behind most text databases and search engines is an inverted index. Basically it's a map of words to a list of documents containing th
by dhotson 16y ago
The basic data structure behind most text databases and search engines is an inverted index.
Basically it's a map of words to a list of documents containing that word.
eg
{"hello": [1, 2], "world": [1,3,4], ...}
(the numbers are document id's)
So for example, the word 'hello' occurs in documents 1 and 2. 'world' occurs in documents 1,3 and 4.
Doing boolean queries is also really easy with an inverted index. You basically get the document set for each word and then do a union on the sets for an OR query.. or an intersection to do an AND query.
Pretty cool right?
- _delirium 16y agoThe convention of calling this the "inverted" index never ceases to trip me up whenever I see it, since when it comes to IR, I always think of a normal index as being a word->locations mapping, like the index in the back of a book.
- ctd 16y agoHeh, just happened to me, too. Have to remember we're in a technical context here. :)