Normalized Google distance

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Google distance is a semantic similarity measure derived from the number of hits returned by the Google search engine for a given set of keywords. Keywords with the same or similar meanings in a natural language sense tend to be "close" in units of Google distance, while words with dissimilar meanings tend to be farther apart.

Specifically, the normalized Google distance between two search terms x and y is

\operatorname{NGD}(x,y) = \frac{\max\{\log f(x), \log f(y)\} - \log f(x,y)}
{\log M - \min\{\log f(x), \log f(y)\}}

where M is the total number of web pages searched by Google; f(x) and f(y) are the number of hits for search terms x and y, respectively; and f(xy) is the number of web pages on which both x and y occur.

If the two search terms x and y never occur together on the same web page, but do occur separately, the normalized Google distance between them is infinite. If both terms always occur together, their NGD is zero.

The normalized Google distance is derived from the earlier normalized compression distance (Cilibrasi & Vitanyi 2003). A closely related algorithm was described by (Allen and Wu, 2002).