Inverted index

An inverted file is an index structure mapping words to their locations in a text or text collection. Inverted files are usually the most important data structure used in search engines.

If you have an inverted file for a set of documents $D=\{S^{1},S^{2},\dots ,S^{d}\}$, you can seach for a word $P$, and get either the set of documents containing $P$, or all pairs of documents and offsets where $P$ occurs.

References

• Justin Zobel, Alistair Moffat and Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing. ACM Transactions on Database Systems (TODS), Volume 23, Issue 4 (December 1998), Pages: 453 - 490.