4 ms·

Inverted Indexes: A Step-by-Step Implementation Guide (2023)

85 points by klaussilveira 1y ago

the_precipitate 1y ago
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.
- atombender 1y ago
  I think you're thinking of index stream readers?
  - mrkeen 1y ago
    I have heard of neither. But the mention of Burrows leads me to Burrows-Wheeler, which is a compression algorithm (bzip). I'm not 100% but I don't think you can directly query a BWT in the same way you'd query an inverted index (without the later discovery of wavelet trees and FM-indexes / succinct data structures, and all that jazz.) And that's mostly for genomics? Not sure if it applies to plain old document searches. Would love to be corrected though.
    - lazamar 1y ago
      At Meta they are using FM indexes to power text search through the entire commit history of their monorepo.
- marginalia_nu 1y ago
  Another very nice algorithm in the space is this one[1] for intersecting postings lists in sublinear time generally with very good cache characteristics to boot. Works with tree-based indexes as well as skip lists (though a more modern design might also use simple bloom filters to go with the skip pointers). [1] https://nlp.stanford.edu/IR-book/html/htmledition/faster-postings-list-intersection-via-skip-pointers-1.html https://nlp.stanford.edu/IR-book/html/htmledition/faster-pos...
SeanSullivan86 1y ago
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?
- mrkeen 1y ago
  No it's the same thing. With any book you have built-in mechanism to go to a page number see what words are there. An inverted index lets you do the inverse (words -> page numbers).
  - SeanSullivan86 1y ago
    People (non-tech) don't tend to refer to "go to page 106" as using an index. The pages at the back of the book providing the word->page numbers lookup are commonly known as the book's "index"
    - grg0 1y ago
      "commonly" is an understatement; that's literally what a book index is by definition. The only thing "inverted" here is the context. The author even admits themselves that the word->doc mapping is an index: "If user wants to search by words - then words should be keys in our "database" (index)" It's a pointless debate of semantics. An inverted map is still a map.
      - teiferer 1y ago
        It's pointless in the sense that the word "inverse" in the term is pointless, a mild way of saying that it's confusing or even unnecessary to the point of being incorrect. The discussion about it is not pointless since it clears up confusion. It might not have been for you, but it's clearly for many others, so if you think that's pointless then allowing yourself to appreciate other perspectives could go a long way. An inverted map is still a map, but if you are typically thinking of the map A->B and then suddenly somebody talks about an inverted map, then it's understandable that people start to assume that this is now about B->A and get confused if it somehow actually isn't really.
dvh 1y ago
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 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.
AdieuToLogic 1y ago
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." 0 - https://en.wikipedia.org/wiki/Key_Word_in_Context https://en.wikipedia.org/wiki/Key_Word_in_Context
deleted 1y ago
[deleted]
jumploops 1y ago
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. [0]https://project-a.github.io/on-site-search-design-patterns-for-e-commerce/ https://project-a.github.io/on-site-search-design-patterns-f...
bob1029 1y ago
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.
- lazamar 1y ago
  Why not search the FM-indexes directly? It is faster than the n-gram search and you can use the exact full text of the needle.
  - bob1029 1y ago
    If you have millions of them, searching all every time could become a problem.

85 points by klaussilveira 1y ago

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.

atombender 1y ago
I think you're thinking of index stream readers?
- mrkeen 1y ago
  I have heard of neither. But the mention of Burrows leads me to Burrows-Wheeler, which is a compression algorithm (bzip). I'm not 100% but I don't think you can directly query a BWT in the same way you'd query an inverted index (without the later discovery of wavelet trees and FM-indexes / succinct data structures, and all that jazz.) And that's mostly for genomics? Not sure if it applies to plain old document searches. Would love to be corrected though.
  - lazamar 1y ago
    At Meta they are using FM indexes to power text search through the entire commit history of their monorepo.
marginalia_nu 1y ago
Another very nice algorithm in the space is this one[1] for intersecting postings lists in sublinear time generally with very good cache characteristics to boot. Works with tree-based indexes as well as skip lists (though a more modern design might also use simple bloom filters to go with the skip pointers). [1] https://nlp.stanford.edu/IR-book/html/htmledition/faster-postings-list-intersection-via-skip-pointers-1.html https://nlp.stanford.edu/IR-book/html/htmledition/faster-pos...

SeanSullivan86 1y ago

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?

mrkeen 1y ago
No it's the same thing. With any book you have built-in mechanism to go to a page number see what words are there. An inverted index lets you do the inverse (words -> page numbers).
- SeanSullivan86 1y ago
  People (non-tech) don't tend to refer to "go to page 106" as using an index. The pages at the back of the book providing the word->page numbers lookup are commonly known as the book's "index"
  - grg0 1y ago
    "commonly" is an understatement; that's literally what a book index is by definition. The only thing "inverted" here is the context. The author even admits themselves that the word->doc mapping is an index: "If user wants to search by words - then words should be keys in our "database" (index)" It's a pointless debate of semantics. An inverted map is still a map.
    - teiferer 1y ago
      It's pointless in the sense that the word "inverse" in the term is pointless, a mild way of saying that it's confusing or even unnecessary to the point of being incorrect. The discussion about it is not pointless since it clears up confusion. It might not have been for you, but it's clearly for many others, so if you think that's pointless then allowing yourself to appreciate other perspectives could go a long way. An inverted map is still a map, but if you are typically thinking of the map A->B and then suddenly somebody talks about an inverted map, then it's understandable that people start to assume that this is now about B->A and get confused if it somehow actually isn't really.

dvh 1y ago

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 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.

AdieuToLogic 1y ago

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." 0 - https://en.wikipedia.org/wiki/Key_Word_in_Context https://en.wikipedia.org/wiki/Key_Word_in_Context

deleted 1y ago

[deleted]

jumploops 1y ago

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. [0]https://project-a.github.io/on-site-search-design-patterns-for-e-commerce/ https://project-a.github.io/on-site-search-design-patterns-f...

bob1029 1y ago

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.

lazamar 1y ago
Why not search the FM-indexes directly? It is faster than the n-gram search and you can use the exact full text of the needle.
- bob1029 1y ago
  If you have millions of them, searching all every time could become a problem.