View source for Sheerer's Inequality

'''Google distance''' is a [[semantic similarity]] measure derived from the number of hits returned by the [[Google search|Google search engine]] for a given [[Set (computer science)|set]] of [[keyword (internet search)|keyword]]s. 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

:<math>
\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)\}}
</math>

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''(''x'',&nbsp;''y'') 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, or equivalent to the coefficient between ''x'' squared and ''y'' squared.

The normalized Google distance is derived from the earlier  [[normalized compression distance]] (Cilibrasi & Vitanyi 2003). Allen and Yu (2002) proposed a related measure.

==References==
*R.L. Cilibrasi and P.M.B. Vitanyi (2003). [http://arxiv.org/abs/cs.CV/0312044 Clustering by Compression, ArXiv.org] or [http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tk/&toc=comp/trans/tk/2007/03/k3toc.xml&DOI=10.1109/TKDE.2007.48  Clustering by Compression, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370–383.].
*R.L. Cilibrasi and P.M.B. Vitanyi (2004). [http://arxiv.org/abs/cs.CL/0412098 , The Google Similarity Distance, ArXiv.org] or [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1412045&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D1412045 Clustering by Compression, IEEE Trans. Information Theory, 51:4(2004), 1523 - 1545. ].
*[http://www.newscientist.com/article.ns?id=dn6924 Google's search for meaning] at Newscientist.com.
* R. Allen and Y. Wu, (2002) Generality of Texts [http://www.springerlink.com/content/h3ex0p8ky75e8d54/?MUD=MP] or [http://boballen.info/PAPERS/genconc.pdf], ICADL, Singapore, December, 2002, 111-116.   R. Allen and Y. Wu (2005, submitted 2002). [http://onlinelibrary.wiley.com/doi/10.1002/asi.20202/abstract, Metrics for the Scope of a Collection] or [http://boballen.info/PAPERS/scope.pdf] JASIST, 55,(10), 2005, 1243-1249. 
*J. Poland and Th. Zeugmann (2006), [http://www-alg.ist.hokudai.ac.jp/~thomas/publications/dag_c2c_pz.pdf Clustering the Google Distance with Eigenvectors and Semidefinite Programming]
*A. Gupta and T. Oates (2007), [http://dli.iiit.ac.in/ijcai/IJCAI-2007/PDF/IJCAI07-261.pdf Using Ontologies and the Web to Learn Lexical Semantics] (Includes comparison of NGD to other algorithms.)
* Wong, W., Liu, W. & Bennamoun, M. (2007) Tree-Traversing Ant Algorithm for Term Clustering based on Featureless Similarities. In: Data Mining and Knowledge Discovery, Volume 15, Issue 3, Pages 349–381. {{doi|10.1007/s10618-007-0073-y}} (the use of NGD for term clustering)


[[Category:Computational linguistics]]
[[Category:Statistical distance measures]]


{{linguistics-stub}}