To really appreciate inverted indexes, it’s worthwhile to study ISR (Inverted Stream Readers), a concept introduced by the great Mike Burrows. It’s also worth exploring encoding techniques like PForDelta. These elegant ideas demonstrate how true systems design masters can distill complex concepts into simple, powerful abstractions.
Edit: I stand corrected: it's called index stream readers (thanks atombender for pointing this out). For those who knows Mike Burrows only for the Burrows-Wheeler transformation (BZip), you might also want to know that he was also one of the main developers of AltaVista, the first real search engine for the internet. He also designed the early versions of Bing search engine. Eventually he worked for Google and designed their lock service called Chubby.
I've sometimes been confused by the term "inverted index". The example in this post feels like what I would just call an "index"... i.e documents indexed by the words they contain. Feels about the same as the index in the back of a physical book.
Is the distinction that an index on a multi-valued attribute is called an inverted index?
I recently used inverted index (with ranked document retrieval) and it all took only 66 lines of JavaScript: https://github.com/dvhx/ngspicejs/blob/master/js/search.js and I'm kinda proud of that code, it's compact, without dirty tricks or without being overtly smart. Well except for using 1/term_frequency instead of logarithms, it's easier to debug (sums of fractions instead of random numbers produced by logarithms) and I just left it there, it works fine.
A related concept is "Key Word in Context (KWIC)"[0] indicies. These were very common, and useful, in Unix documentation. Another name for them is "permuted index."
Tangential, but for anyone looking to utilize Elasticsearch in production, I highly recommend “On-Site Search Design Patterns for E-Commerce”[0]
I was familiar with both inverted indexes and Elasticsearch at a conceptual level, but this overview helped me improve our search (rankings, facets, etc.) much faster than I would have otherwise.
Combining n-grams and bitmap indexes can give you most of the magic in the space.
I've been working on an architecture for code search that relies on a repo-level trigram index and a per-repo FM-index (actual code). The trigram index is used to find the bitmaps of repos that contain each term. These are then ANDed together to produce the final list of repos to search via FM-index.
8 comments
[ 1874 ms ] story [ 3165 ms ] threadEdit: I stand corrected: it's called index stream readers (thanks atombender for pointing this out). For those who knows Mike Burrows only for the Burrows-Wheeler transformation (BZip), you might also want to know that he was also one of the main developers of AltaVista, the first real search engine for the internet. He also designed the early versions of Bing search engine. Eventually he worked for Google and designed their lock service called Chubby.
Is the distinction that an index on a multi-valued attribute is called an inverted index?
0 - https://en.wikipedia.org/wiki/Key_Word_in_Context
I was familiar with both inverted indexes and Elasticsearch at a conceptual level, but this overview helped me improve our search (rankings, facets, etc.) much faster than I would have otherwise.
[0]https://project-a.github.io/on-site-search-design-patterns-f...
I've been working on an architecture for code search that relies on a repo-level trigram index and a per-repo FM-index (actual code). The trigram index is used to find the bitmaps of repos that contain each term. These are then ANDed together to produce the final list of repos to search via FM-index.