# Inverted Index for Search Engines

Inverted indexing is a technique to perform full-text searches across multiple documents efficiently.

The idea is to build a key-value store where keys are the terms encountered in each indexed document. The values are sets; each of them contains the references to the documents in where the term has been found.

## Indexing Documents

When indexing a document, each term (word) is scanned. Each encountered term can be skipped if it is considered nonrelevant. It is typically the case of words such as "the," "a," "this," "that." We call those terms stop words. A term could be added to the index as a new key if it did not previously exist. If the term is already present (because other documents containing this term have already been indexed), the set is updated, so it now includes the reference of the document.

For example, let's say we have the three following documents.

```
d1: "Penguins are a group of aquatic flightless birds"
d2: "Dolphins are a widely distributed and diverse group of aquatic mammals"
d3: "Japanese bush warblers are Asian passerine birds more often heard than seen"
```

The resulting inverted index is the following structure. (Note that we have skipped the stop words.)

```
INDEX = {
'aquatic': {'d1', 'd2'},
'asian': {'d3'},
'birds': {'d3', 'd1'},
'bush': {'d3'},
'distributed': {'d2'},
'diverse': {'d2'},
'dolphins': {'d2'},
'flightless': {'d1'},
'group': {'d1', 'd2'},
'heard': {'d3'},
'japanese': {'d3'},
'mammals': {'d2'},
'more': {'d3'},
'often': {'d3'},
'passerine': {'d3'},
'penguins': {'d1'},
'seen': {'d3'},
'warblers': {'d3'},
'widely': {'d2'}
}
```

## Searching

Now, searching for the term `birds`

is performed by a simple lookup on key `birds`

, which
returns the set `{d3, d1}`

. The documents `d1`

and `d3`

are returned as expected because
they both contain the term `birds`

.

When searching for more than one term, multiple lookups are performed, and the resulting sets are merged with a set intersection.

Searching for terms `aquatic birds`

gives us two sets: `{d1, d2}`

and `{d3, d1}`

. The intersection
of those sets is: `{d1, d2} ∩ {d3, d1} = {d1}`

. The document `d1`

is returned, and it contains
both terms `aquatic`

and `birds`

.

Such lookups are generally performed in *O(1)* (hash map) or *O(log n)* (B-Trees or similar), which is
efficient.

However, the set intersection algorithm complexity is necessarily linear. In practice, this may not be a problem
because search results are generally limited to a fixed number of items (e.g., only the `n` most recent items are taken into account)
thus limiting the intersection computation.

## Basic implementation

For this article, I have written a short Python implementation.