Tag Info

About

Full text search systems use a data structure called an inverted index. Logically an inverted index consists of a key containing the word, and a list of documents that word appears in. The document entry may also have a weighting based on the frequency with which that word appears in the document. A weighting may also be applied to the search terms.

Full text search engines locate documents matching the search terms and calculate the closeness of the match using a heuristic called a cosine ranking. This is calculated by forming an n-dimensional vector from the search terms and then constructing similar vectors from the search results. The dot product of these two vectors is the cosine of the angle between these vectors in n-dimensional space. A cosine value of 1 indicates parallel vectors and the closest possible match.

Typically the search results are fed into a priority queue and then popped out in order from highest cosine ranking to lowest. Some systems also apply weightings to the cosine rankings based on other factors; the most famous examples of this is Google's Pagerank algorithm.

Text retrieval systems normally use proprietary engines, although many general-purpose database systems also offer a full text search function.

history | show excerpt | excerpt history