Inverted index

[1] The purpose of an inverted index is to allow fast full-text searches, at a cost of increased processing when a document is added to the database.

It is the most popular data structure used in document retrieval systems,[3] used on a large scale for example in search engines.

Additionally, several significant general-purpose mainframe-based database management systems have used inverted list architectures, including ADABAS, DATACOM/DB, and Model 204.

[5] A goal of a search engine implementation is to optimize the speed of the query: find the documents where word X occurs.

The matching requires constructing an inverted index of all substrings of a certain length from the reference DNA sequence.