The Google Similarity Distance

By Rudi Cilibrasi, Paul M. B. Vitányi. 2004

1,879 citations recorded by the source corpus.

Words and phrases acquire meaning from the way they are used in society, from their relative semantics to other words and phrases. For computers, the equivalent of "society" is "database," and the equivalent of "use" is "a way to search the database". We present a new theory of similarity between words and phrases based on information distance and Kolmogorov complexity. To fix thoughts, we use the World Wide Web (WWW) as the database, and Google as the search engine. The method is also applicable to other search engines and databases. This theory is then applied to construct a method to automatically extract similarity, the Google similarity distance, of words and phrases from the WWW using Google page counts. The WWW is the largest database on earth, and the context information entered by millions of independent users averages out to provide automatic semantics of useful quality. We give applications in hierarchical clustering, classification, and language translation. We give examples to distinguish between colors and numbers, cluster names of paintings by 17th century Dutch masters and names of books by English novelists, the ability to understand emergencies and primes, and we demonstrate the ability to do a simple automatic English-Spanish translation. Finally, we use the WordNet database as an objective baseline against which to judge the performance of our method. We conduct a massive randomized trial in binary classification using support vector machines to learn categories based on our Google distance, resulting in an a mean agreement of 87 percent with the expert crafted WordNet categories

Subfields: Computational Theory and Mathematics, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Molecular Biology

Citations in the corpus

Representation Learning for Measuring Entity Relatedness with Rich Information (2015, methodology): “…e2), length(e2, e1)} 2× depth (12) • Wikipedia Link-based Measure (WLM): Milne and Witten [2008] proposed a low-cost measure of semantic relatedness based on Wikipedia entity graph, inspired by Normalized Google Distance [Cilibrasi and Vitanyi, 2007]: sr(e1, e2) = log(max(|E1|, |E2|))− log(|E1 ∩ E2”
N-gram IDF: A Global Term Weighting Scheme Based on Information Distance (2015, methodology): “[10] R. L. Cilibrasi and P. M. Vitányi.”
Representation of the Online Tourism Domain in Search Engines (2008, background): “To date, the total number of Web pages on the Internet indexed by Google is approaching 1010 as of early 2007 (Cilibrasi and Vitànyi 2007).”
A Survey on Context Learning (2017, methodology): “They use a method analogous to Normalized Google Distance [35].”
A Survey of Text Similarity Approaches (2013, methodology): “If both terms always occur together, their NGD is zero, or equivalent to the coefficient between x squared and y squared.”
An effective, low-cost measure of semantic relatedness obtained from Wikipedia links (2008, methodology): “The second measure we use is modeled after the Normalized Google Distance (Cilibrasi and Vitanyi, 2007), which is based on term occurrences on web-pages.”
Clustering to Find Exemplar Terms for Keyphrase Extraction (2009, methodology): “Normalized Google Similarity Distance (NGD) is a new measure for measuring similarity between terms proposed by (Cilibrasi and Vitanyi, 2007) based on information distance and Kolmogorov complexity.”
A new sentence similarity measure and sentence based extractive technique for automatic text summarization (2009, methodology): “First, using the NGD we define the global and local dissimilarity measure between terms (as shown in Cilibrasi & Vitányi, 2007 the NGD is nonnegative and does not satisfy the triangle inequality, i.e. hence isn't distance and consequently in the further it we shall name dissimilarity measure).”
An open-source toolkit for mining Wikipedia (2013, methodology): “Another feature, normalized link distance, is modeled after the normalized Google distance measure [4].”
KORE: keyphrase overlap relatedness for entity disambiguation (2012, methodology): “Building on the co-occurrence-based information-theoretic model of [20, 6], the Milne-Witten relatedness measure, MW for short, for two entities e and f with sets of incoming Wikipedia links Ie and If , respectively, is defined as (where N is the total number of articles in Wikipedia):”
Entity Linking with a Knowledge Base: Issues, Techniques, and Solutions (2015, methodology): “In addition to Normalized Google Distance model, Ratinov et al. [76] proposed to use the point-wise mutual information (PMI-like) measure to calculate the topical coherence between Wikipedia entities: Coh P ðu 1 ; u 2 Þ ¼ jU 1 \ U 2 j=jWP j jU 1 j=jWP j Á jU 2 j=jWP j : Furthermore, Guo et al. [22] ”
Query Expansion Techniques for Information Retrieval: a Survey (2017, neutral): “PMING distance [95,94] includes the combination of two semantic similarity measurement techniques: PMI and NGD.”
Measuring semantic similarity between words using web search engines (2007, methodology): “2, Web-based semantic similarity measures proposed in previous work (Sahami [42], Chen [6]), Normalized Google Distance (NGD) [8], and the proposed method (SVM).”
Reinforced Similarity Integration in Image-Rich Information Networks (2013, neutral): “Index Terms—Information retrieval, image mining, information network, ranking Ç”
Tag ranking (2009, neutral): “Analogous to the principle of Google distance [17], we first estimate the distance between two tags ti and tj as follows.”