Welcome! Thanks for visiting!
This post is part of an ongoing series: How Search Really Works.
Previous Instalment: The Keyword Density Myth.
If a search engine would search "live" through the documents it knows about for the occurrence of the word we’re looking for it could take its time and then simply report where it found our word.
In this example our search engine has only one index: the documents itself.
However, time is something a search engine doesn’t have; the query needs to be answered now.
What we need is a real index!
Boolean Index - Talk about the Matrix
The problem with a boolean index, where we put a little flag (1) or not (0) for every word for every document is that it quickly grows way and way too large.
Three documents with amongst them just four words take 12 1’s or 0’s — apart from the bits and bytes we need to store the word. Now imagine a matrix where one of the sides is 13,940,000,000 columns wide…
The Inverted Index
In the inverted index we record only the places (documents) where a word does occur.
It’s called inverted because instead of the documents providing the occurrences of a word, the word points to which documents it occurs in.
Sorted by document pointer, the inverted index is extremely efficient in performing AND queries.
Let’s reshuffle our example a little bit to make this visually clear: 
If we search for documents that contain the words "search compression" and we down these rows at the same time, as soon as one row makes a jump to a higher document ID, you can jump forward in the other row as well: no use checking the intermediate ones as you now know that those won’t have both words.
Knowing only about yes/no occurrences, an inverted index is horrible at phrase and proximity matching:
To be continued…
I hang out at Twitter where I enjoy the company, the buzz, the nuggets of info and opinion we pass along.Join me on Twitter!
As posted in How Search Really Works.
You're welcome to join the conversation; add your response. You can track the conversation using the RSS 2.0 feed.
You can also trackback from your own site.
4 Responses to “How Search Really Works: "The" Index (1)”
Trackbacks
-
Learn SEO: Search Indexing Says:
February 26th, 2008 at 1:31 pm[…] In the first parts of the series we have been educated in META keywords, keyword links, keyword stuffing, keyword density myth, and now we have “How Search Really Works: “The” Index (1)” […]
February 24th, 2008 at 11:14 pm
Excellent post on co-occurrence in search. Interested in seeing the follow ups. Information retrieval should be on the “must-know” list for all SEOs but amazing how many don’t completely grasp it.
February 25th, 2008 at 5:41 am
I thought I understood a little about search engines but now I’m confused. Eagerly awaiting part 2.
February 25th, 2008 at 9:08 am
I’m really looking forward to read more of this serie. I could make some people very happy if I referred them here!