inverted index
In plain wordsA lookup table that lists, for every word, all the documents containing it — like the index at the back of a book — so a search engine can find matches almost instantly.
A data structure that maps each term in a vocabulary to a postings list: the identifiers of the documents that contain the term, often with term frequencies and word positions. A query is answered by fetching the postings for its terms and merging or scoring them, touching only documents that share terms with the query instead of scanning the whole collection. Compressed postings, skip pointers and early-termination algorithms such as WAND make this fast at web scale. The inverted index is the engine behind sparse retrievalsparse retrieval, n.: Finding documents by the words they contain, giving more weight to rare, telling words — the classic way search engines work. functions such as BM25BM25, prop. n.: A decades-old formula that search engines use to score how well a document matches a query, rewarding rare query words and repeated matches — with diminishing returns — and correcting for long documents. and TF-IDFTF-IDF, abbr.: A simple score for picking out the words that characterize a document: a word counts for more the more often it appears there, and for less the more of the collection's other documents also use it., and its strategy — partition the data into lists and probe only promising ones — reappears in the inverted-file (IVF) indexes used for approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster. over vectors.
Adding phrase search meant storing word positions in the inverted index, which doubled its size.
Origin
The idea descends from concordances and back-of-book indexes. Inverted-file organizations were in use in computerized document retrieval by the 1960s and became the standard architecture of text search engines; open-source libraries such as Apache Lucene made them ubiquitous.
Usage note
'Inverted' because it reverses the natural document-to-words mapping into a words-to-documents mapping.
Related
- BM25BM25, prop. n.: A decades-old formula that search engines use to score how well a document matches a query, rewarding rare query words and repeated matches — with diminishing returns — and correcting for long documents.
- sparse retrievalsparse retrieval, n.: Finding documents by the words they contain, giving more weight to rare, telling words — the classic way search engines work.
- information retrievalinformation retrieval, n.: The study and engineering of search: how to organize huge piles of documents so that the few that matter to someone's question can be found and ranked quickly. AI systems rely on it to look things up.
- TF-IDFTF-IDF, abbr.: A simple score for picking out the words that characterize a document: a word counts for more the more often it appears there, and for less the more of the collection's other documents also use it.
- approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster.
- hybrid searchhybrid search, n.: Searching two ways at once — by exact keywords and by meaning — and merging the results, so you catch precise matches like product codes as well as differently worded matches.
Sources
- Zobel, J. & Moffat, A. (2006). Inverted files for text search engines. ACM Computing Surveys 38(2).
Mentioned in
BM25BM25, prop. n.: A decades-old formula that search engines use to score how well a document matches a query, rewarding rare query words and repeated matches — with diminishing returns — and correcting for long documents., information retrievalinformation retrieval, n.: The study and engineering of search: how to organize huge piles of documents so that the few that matter to someone's question can be found and ranked quickly. AI systems rely on it to look things up., sparse retrievalsparse retrieval, n.: Finding documents by the words they contain, giving more weight to rare, telling words — the classic way search engines work., TF-IDFTF-IDF, abbr.: A simple score for picking out the words that characterize a document: a word counts for more the more often it appears there, and for less the more of the collection's other documents also use it.