The Google Similarity Distance

Rudi CilibrasiPaul M. B. Vitanyi

article2004TKDE1,882 citations

Introduces a universal semantic similarity metric based on Kolmogorov complexity and search engine page counts, demonstrating how collective web data can automatically drive text clustering, classification, and translation without manual supervision.

Listen

Extracting meaningful semantic relationships between words and concepts is a long-standing challenge in artificial intelligence and computational linguistics. Traditional approaches, such as expert-built knowledge bases like Cyc and WordNet, require decades of labor-intensive curation, resulting in structures that remain minute compared to the scale of human knowledge. Meanwhile, the rapid growth of the World Wide Web provides an immense, low-grade repository of collective human usage. The article sets out to demonstrate that relative semantic similarity between arbitrary words and phrases can be automatically and reliably extracted without human curation or feature engineering by using aggregate search engine page counts.

To accomplish this, the authors introduce the Normalized Google Distance (NGD), a mathematical framework derived from information theory and algorithmic complexity. Instead of analyzing document text directly, the method uses only the frequency of individual search terms and their pairwise joint co-occurrences reported by Google across billions of indexed web pages. The authors theoretically prove that the aggregate web distribution universally captures the semantic knowledge and individual biases of distributed web authors. They empirically test this metric across several domains using unsupervised hierarchical clustering, supervised machine learning with Support Vector Machines (SVM), and bilingual vocabulary mapping.

Across multiple experiments, the method successfully captured nuanced semantic distinctions. It automatically organized concepts into coherent hierarchical trees, separating colors from numbers and grouping artworks and literary texts accurately by creator. In supervised learning tasks, the model distinguished real-world concepts such as emergencies from non-emergencies with 75% accuracy and identified prime numbers with 94.74% accuracy. Furthermore, in a massive randomized benchmark across 100 WordNet categories, an SVM trained on 6-dimensional NGD vectors achieved a mean agreement rate of 87.25% (with a standard deviation of about 0.117) against expert-crafted knowledge, rarely falling below 75% accuracy. The method also proved effective in automatically resolving unknown word-translation permutations between English and Spanish.

These findings demonstrate that web-scale co-occurrence statistics provide a low-cost, automated alternative to labor-intensive semantic knowledge engineering. Because the metric relies solely on high-level query hit counts rather than downloading or indexing full document collections, it offers immense computational savings over traditional techniques like Latent Semantic Analysis. For decision-makers and technologists, this approach opens viable avenues for scalable automated classification, knowledge discovery, and data-mining workflows without requiring expensive domain-specific training data.

Organizations considering this technique should evaluate pilot applications in classification and clustering using the freely available CompLearn software tool. Practitioners should proceed with an awareness of the system's operational constraints: the method depends on the stability and accuracy of third-party search engine query reporting and sampling approximations. Daily search request limits also require caching strategies for large-scale operations. Despite these operational limitations, the underlying mathematical theory and extensive empirical testing provide strong confidence that aggregate web data reliably reflects real-world conceptual relationships.

Centrum Wiskunde Informatica CSIRO’s Data61 University of Amsterdam University of New South Wales binary classification context information engine Google Similarity Distance semantic distance word similarity

arXiv: cs/0412098 rudi-cilibrasi/libcomplearn

Paper: An Information-Theoretic Definition of Similarity, Dekang Lin (1998). Establishes the foundational information-theoretic definition of similarity from first principles that underpins mathematical formulations of corpus-derived semantic distance.
Paper: Using Information Content to Evaluate Semantic Similarity in a Taxonomy, Philip Resnik (1995). Introduces the information-content approach to measuring semantic similarity using corpus probabilities and hierarchical taxonomies like WordNet, providing the baseline evaluated in the source.
Paper: Semantic Similarity Based on Corpus Statistics and Lexical Taxonomy, Jay J. Jiang et al. (1997). Presents a hybrid statistical and taxonomy-based similarity metric that serves as an essential benchmark for evaluating information-based conceptual distances.
Paper: Automatic Retrieval and Clustering of Similar Words, Dekang Lin (1998). Demonstrates how information-theoretic measures can automatically discover and cluster semantically related words directly from large text corpora.
Paper: Word Association Norms, Mutual Information, and Lexicography, Kenneth Ward Church et al. (1989). Pioneers the use of point-wise mutual information and co-occurrence counts to measure associative closeness between words from unannotated text.

Paper: Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis, E. Gabrilovich et al. (2007). Advances beyond web search page counts by mapping words and texts into explicit conceptual vectors derived from Wikipedia to compute semantic relatedness.
Paper: From Frequency to Meaning: Vector Space Models of Semantics, Peter D. Turney et al. (2010). Surveys the evolution of turning frequency and co-occurrence statistics from vast text corpora into formal vector space models of semantics.
Paper: From Word Embeddings To Document Distances, Matt J. Kusner et al. (2015). Extends semantic distance between individual word vectors to full document-level distances using optimal transport theory.
Paper: Neural Word Embedding as Implicit Matrix Factorization, Omer Levy et al. (2014). Provides theoretical grounding for neural vector representations by proving their equivalence to implicit factorizations of co-occurrence mutual information matrices.
Paper: ConceptNet 5.5: An Open Multilingual Graph of General Knowledge, R. Speer et al. (2016). Integrates distributional co-occurrence embeddings with large-scale relational knowledge graphs to achieve robust multilingual semantic representations.

Cover for The Google Similarity Distance

Abstract

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 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 as database, and Google as 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 world-wide-web using Google page counts. The world-wide-web 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% with the expert crafted WordNet categories.

Topics

binary classification context information engine hier-archical clustering support vector wordnet web content web search engines

Keywords

I Introduction
I-A An Example:
I-B Related Work:
I-C Outline:
I-D Materials and Methods:
II Technical Preliminaries
II-A Normalized Information Distance:
II-B Normalized Compression Distance:
III Theory of Googling for Similarity
III-A The Google Distribution:
III-B Google Semantics:
III-C The Google Code:
III-D The Google Similarity Distance:
III-E Universality of Google Distribution:
III-F Universality of Normalized Google Distance:
IV Applications and Experiments
IV-A Hierarchical Clustering:
IV-B Dutch 17th Century Painters:
IV-C English Novelists:
IV-D SVM – NGD Learning:
IV-E NGD Translation:
V Systematic Comparison with WordNet Semantics
VI Conclusion
VII Appendix: Relation to LSA
References
VIII Biographies of the Authors

Knowls

Knowl 1 — Normalized Google Distance
equation
The Normalized Google Distance ( $\text{NGD}$ ) measures the semantic dissimilarity between two search terms (words or phrases) $x$ and $y$ using aggregate page counts returned by a search engine indexing a collection of $N$ total pages:

$\text{NGD}(x,y) = \frac{\max\{\log f(x), \log f(y)\} - \log f(x,y)}{\log N - \min\{\log f(x), \log f(y)\}}$

where:
- $f(x)$ denotes the number of web pages returned for the singleton query $x$ ,
- $f(y)$ denotes the number of web pages returned for the singleton query $y$ ,
- $f(x,y)$ denotes the number of web pages returned for the joint query containing both $x$ and $y$ (Boolean AND),
- $N$ is a normalization parameter chosen such that $N \ge M$ , where $M = |\Omega|$ is the total number of indexed web pages (or any value strictly greater than $\max\{f(x), f(y)\}$ ), and
- $\log$ denotes the base-2 logarithm (though any logarithm base yields identical results as the base cancels across the numerator and denominator).
The $\text{NGD}$ is an approximation of the theoretical Normalized Information Distance (NID) based on Kolmogorov complexity, utilizing the Google distribution over web pages as a compressor for relative semantics.
Knowl 2 — Mathematical Properties of Normalized Google Distance
theoretical result
For a normalization parameter $N \ge M$ (where $M$ is the total count of indexed web pages):
1. Range: The range of $\text{NGD}$ is in $[0, \infty)$ , with values typically between $0$ (identical semantics) and $1$ (unrelated terms). If $x = y$ , or if $x \neq y$ and $f(x) = f(y) = f(x,y) > 0$ , then $\text{NGD}(x,y) = 0$ . If $f(x) = 0$ , then for any $y$ with $f(y) > 0$ , $\text{NGD}(x,y) = \frac{\log f(y)}{\log(N / f(y))}$ .
2. Symmetry and Non-Metricity: $\text{NGD}$ $NGD$ is symmetric ( $\text{NGD}(x,y) = \text{NGD}(y,x)$ $NGD (x, y) = NGD (y, x)$ ) and nonnegative with $\text{NGD}(x,x) = 0$ $NGD (x, x) = 0$ . However, $\text{NGD}$ $NGD$ is not a mathematical metric:
  - Identity of indiscernibles fails because distinct words that always co-occur identically ( $f(x) = f(y) = f(x,y)$ ) yield $\text{NGD}(x,y) = 0$ .
  - The triangle inequality $\text{NGD}(x,y) \le \text{NGD}(x,z) + \text{NGD}(z,y)$ fails in general. For example, if $x$ and $y$ are disjoint with $|x| = |y| = \sqrt{N}$ and $z = x \cup y$ , then $f(x,y) = 0$ , $f(x,z) = f(y,z) = \sqrt{N}$ , and $f(z) = 2\sqrt{N}$ . This gives $\text{NGD}(x,y) = 1$ while $\text{NGD}(x,z) + \text{NGD}(z,y) = \frac{4}{\log(N/4)}$ , violating the triangle inequality whenever $N > 64$ .
3. Scale Invariance: If the indexed page corpus size $N$ grows and the frequency counts $f(x), f(y), f(x,y)$ grow proportionally as fixed fractions of $N$ , the value of $\text{NGD}(x,y)$ remains invariant.
Knowl 3 — Universality of the Google Distribution
theoretical result
Let $\Omega$ be the universe of indexed web pages partitioned into $a$ disjoint subsets $\Omega_1, \dots, \Omega_a$ representing individual web authors or subcorpora, such that $\Omega = \bigcup_{i=1}^a \Omega_i$ and $\Omega_i \cap \Omega_j = \emptyset$ for $i \neq j$ . Let $S$ be the set of search terms.

For each subcorpus $i \in \{1, \dots, a\}$ , let $x_i = x \cap \Omega_i$ be the event that a page produced by author $i$ contains term $x$ . Define the subcorpus normalization constant $N_i = \sum_{\{x,y\} \subseteq S} |x_i \cap y_i|$ . The author's individual probability distribution $g_i$ on singleton and doubleton terms $\{x,y\} \subseteq S$ is defined by:

$g_i(x,y) = \frac{|x_i \cap y_i|}{N_i}$

The global Google distribution $g(x,y) = |x \cap y| / N$ over $\Omega$ with $N = \sum_{\{x,y\} \subseteq S} |x \cap y|$ can be expressed as:

$g(x,y) = \sum_{i=1}^a \frac{N_i}{N} g_i(x,y)$

The global distribution $g$ is universal for the enumeration $\{g, g_1, \dots, g_a\}$ in that for every author $i$ and all pairs $x,y \in S$ ,

$g(x,y) \ge c_i \cdot g_i(x,y)$

where $c_i = \frac{N_i}{N} > 0$ and $\sum_{i=1}^a c_i = 1$ . Consequently, the global prefix code-length $G(x,y) = \log(1/g(x,y))$ minorizes each author's individual code-length $G_i(x,y) = \log(1/g_i(x,y))$ up to an additive constant: $G(x,y) \le G_i(x,y) + \log(N/N_i)$ .
Knowl 4 — Universality of Normalized Google Distance
theoretical result
Let $\text{NGD}_i(x,y)$ be the normalized Google distance defined relative to the individual prefix code-length $G_i$ of an author/subcorpus $i \in \{1, \dots, a\}$ partitioning the web $\Omega$ . For any parameter $k \ge 1$ , the global normalized Google distance $\text{NGD}(x,y)$ minorizes the individual distance $\text{NGD}_i(x,y)$ :

$\text{NGD}(x,y) < \beta \cdot \text{NGD}_i(x,y) + \gamma$

where:

$\beta = \frac{\min\{G_i(x), G_i(y)\} - \log k}{\min\{G_i(x), G_i(y)\}}$

$\gamma = \frac{\log(k N / N_i)}{\min\{G(x), G(y)\}}$

This relation holds with high probability in two distinct respects:
1. Uniform Page Selection: For any fixed pair of search terms $(x,y)$ , if a web page is drawn uniformly at random from $\Omega$ , the inequality holds for the author $i$ of that page with probability greater than $(1 - 1/k)^2$ .
2. Term Selection per Author: For any fixed author $i$ , the probability mass under $g_i$ concentrated on the pairs of search terms $(x,y)$ satisfying the inequality is at least $(1 - 2/k)^2$ .
Knowl 5 — SVM-NGD Feature Representation for Concept Classification
model/method
Supervised semantic classification of search terms is accomplished by embedding words into fixed-dimensional Euclidean feature spaces using anchor terms and Normalized Google Distance ( $\text{NGD}$ ), followed by Support Vector Machine (SVM) training:
1. Anchor Selection: A human expert or automated selection provides a set of $d$ anchor words $a_1, a_2, \dots, a_d$ , where approximately half the anchors relate to the contemplated concept class and half are unrelated.
2. Feature Mapping: Each training or testing word $w$ is converted into a $d$ -dimensional real vector $\mathbf{v}(w) = (v_1, v_2, \dots, v_d) \in \mathbb{R}^d$ , where:
  
  $v_j = \text{NGD}(w, a_j) \quad \text{for } 1 \le j \le d$
3. Classifier Training: Labeled positive and negative training examples converted to vectors $\mathbf{v}(w)$ are used to train an SVM. Hyperparameters (kernel width and error cost) are optimized via five-fold cross-validation, and candidate test terms are classified via their embedded anchor vectors.
Knowl 6 — WordNet Semantic Benchmark Performance
empirical result
The accuracy of the SVM-NGD classification framework was benchmarked against the WordNet database across 100 randomly chosen semantic categories:
- Setup: For each WordNet category, the SVM was trained on 50 labeled examples (positive examples sampled randomly from the WordNet category, negative examples drawn randomly from a standard dictionary) embedded into 6-dimensional vectors using 6 anchor words (3 from the WordNet category, 3 from the dictionary). Evaluation was performed on a balanced test set of 20 unseen examples (10 positive, 10 negative).
- Results: Across the 100 trials, the mean classification accuracy was $87.25\%$ with a sample variance of $\approx 0.01367$ (standard deviation $\approx 0.1169$ ). Accuracy rarely dropped below $75\%$ .
- Query Complexity: Caching individual search term counts and anchor counts reduced the required search engine queries from an un-cached worst case of $100 \times 70 \times 6 \times 3 = 126{,}000$ to $6 + 70 + (70 \times 6) = 496$ queries per experiment, totaling $49{,}600$ queries across all 100 trials.
Knowl 7 — Bilingual Lexicon Translation via NGD Matrix Correlation
algorithm
Given a seed vocabulary of matched translation pairs across two languages and sets of unaligned words, the correct translation permutation is determined by maximizing the Pearson correlation between NGD distance matrices without bilingual text corpora.
Input: Seed matched pairs $(e_1, s_1), (e_2, s_2), \dots, (e_n, s_n)$ from source language E and target language S
Input: Unaligned words in source language $U_E = \{u_{E,1}, \dots, u_{E,m}\}$
Input: Unaligned words in target language $U_S = \{u_{S,1}, \dots, u_{S,m}\}$
Output: Optimal translation permutation $\pi^*$ mapping $U_E$ to $U_S$
Construct source basis matrix $B_E \in \mathbb{R}^{m \times n}$ where $B_E[j, k] = \text{NGD}(u_{E,j}, e_k)$
best_corr = -1.0
best_perm = null
for each permutation $\pi$ of $(1, 2, \dots, m)$ do
    Construct candidate target matrix $B_S^\pi \in \mathbb{R}^{m \times n}$ where $B_S^\pi[j, k] = \text{NGD}(u_{S,\pi(j)}, s_k)$
    Flatten $B_E$ and $B_S^\pi$ into 1D vectors $v_E$ and $v_S^\pi$ of length $m \cdot n$
    Compute Pearson correlation $r = \text{corr}(v_E, v_S^\pi)$
    if $r > best_corr$ then
        best_corr = $r$
        best_perm = $\pi$
    end if
end for
if best_corr > 0 then
    return mapping $u_{E,j} \mapsto u_{S,best_perm(j)}$ for all $j \in \{1, \dots, m\}$
else
    return failure
end if
In an evaluation using 8 known English-Spanish word pairs and 5 unknown words (plant, car, dance, speak, friend), the method recovered the correct permutation (planta, coche, bailar, hablar, amigo) with the maximal positive correlation.
Knowl 8 — Hierarchical Clustering via NGD Distance Matrices
model/method
Unsupervised hierarchical semantic clustering of words or phrases is performed by constructing the full pairwise NGD matrix for an input list of terms and inferring an unrooted ternary dendrogram using a quartet-based randomized hill-climbing heuristic. The optimization maximizes a tree fidelity score $S(T) \in [0, 1]$ (where $S(T) = 1$ denotes zero distortion):
- Colors and Numbers: Clustering lists of colors, numbers, and ambiguous terms automatically separates color terms and number terms onto opposite major branches, while placing polysemous words ('black', 'white', 'zero', 'one', 'two') and non-conforming words ('small') near the central tree hub.
- Fine Arts and Literature: Clustering titles of 15 paintings by Rembrandt, Jan Steen, and Ferdinand Bol or 12 literary works by Shakespeare, Jonathan Swift, and Oscar Wilde groups titles strictly by creator into separate, non-overlapping clusters with tree fidelity scores $S(T) \approx 0.94$ .
Knowl 9 — SVM-NGD Learning on Domain Tasks: Emergencies and Primes
empirical result
The SVM-NGD classification framework was evaluated on two concept classes:
1. Emergency Concept Learning: Trained on 22 positive emergency terms (e.g., 'avalanche', 'car collision', 'murder') and 25 negative non-emergency terms (e.g., 'broken dishwasher', 'headache', 'paper cut') using 6 anchor words ('crime', 'happy', 'help', 'safe', 'urgent', 'wash'). The model achieved $15/20 = 75.00\%$ accuracy on a 20-word test set, correctly identifying emergencies ('assault', 'coma', 'suicide') and rejecting non-emergencies ('meal', 'desk', 'acne').
2. Prime Number Concept Learning: Trained on 21 prime numbers and 22 composite numbers using 5 anchor words ('composite', 'number', 'orange', 'prime', 'record'). On a 19-number test set, the model achieved $18/19 = 94.74\%$ accuracy, demonstrating that statistical web co-occurrence can capture numerical and mathematical distinctions without deductive rules.
Knowl 10 — Computational and Practical Limitations of Web Search Distance
limitation
The Normalized Google Distance framework possesses several practical and structural constraints:
1. Hit Count Inaccuracy and Volatility: Search engine page counts are computed via sampling rather than exact enumeration, change frequently as indexes update, and are particularly unreliable when evaluating Boolean OR queries.
2. Query Quotas and Latency: Commercial search engines enforce daily query limits per IP address (e.g., 500 requests/day), requiring anchor sharing and caching to make classification or clustering feasible.
3. Associative vs. Deductive Semantics: The web-derived distance reflects associative usage rather than formal logic; words with opposite polarities (e.g., 'true' and 'false') frequently co-occur in the same contexts and thus exhibit small NGD values.
4. Intractability of Full Document Latent Semantic Analysis (LSA): Unlike LSA, which requires singular value decomposition over a $d \times a$ document-term matrix (computationally impossible for $10^{10}$ web pages requiring terabytes of storage), NGD operates strictly on aggregate term co-occurrence counts, trading detailed document-level representations for web-scale breadth.

Coverage note — None was omitted; all major theoretical contributions, definitions, empirical benchmarks, algorithms, and practical limitations have been captured.

References

1.J.P. Bagrow, D. ben-Avraham, On the Google-fame of scientists and other populations, AIP Conference Proceedings 779:1(2005), 81–89.
2.C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitanyi, W. Zurek, Information Distance, IEEE Trans. Information Theory, 44:4(1998), 1407–1423.
3.C.H. Bennett, M. Li, B. Ma, Chain letters and evolutionary histories, Scientific American, June 2003, 76–81.
4.C.J.C. Burges. A tutorial on support vector machines for pattern recognition, Data Mining and Knowledge Discovery, 2:2(1998),121–167.
5.Automatic Meaning Discovery Using Google: 100 Experiments in Learning WordNet Categories, 2004, http://www.cwi.nl/∼cilibrar/googlepaper/appendix.pdf
6.R. Cilibrasi, Complearn Home, http://www.complearn.org/
7.R. Cilibrasi, R. de Wolf, P. Vitanyi. Algorithmic clustering of music based on string compression, Computer Music J., 28:4(2004), 49-67.
8.R. Cilibrasi, P. Vitanyi. Clustering by compression, IEEE Trans. Information Theory, 51:4(2005), 1523- 1545.
9.R. Cilibrasi, P. Vitanyi, Automatic meaning discovery using Google, http://xxx.lanl.gov/abs/cs.CL/0412098 (2004).
10.R. Cilibrasi, P. Vitanyi, A New Quartet Tree Heuristic for Hierarchical Clustering, http://www.cwi.nl/∼paulv/papers/quartet.pdf
11.P. Cimiano, S. Staab, Learning by Googling, SIGKDD Explorations, 6:2(2004), 24–33.
12.T.M. Cover and J.A. Thomas, Elements of Information Theory, Wiley, New York, 1991.
13.J.-P. Delahaye, Classer musiques, langues, images, textes et genomes, Pour La Science, 317(March 2004), 98–103.
14.The basics of Google search, http://www.google.com/help/basics.html.
15.L.G. Kraft, A device for quantizing, grouping and coding amplitude modulated pulses. Master’s thesis, Dept. of Electrical Engineering, M.I.T., Cambridge, Mass., 1949.
16.D. Graham-Rowe, A search for meaning, New Scientist, 29 January 2005, p.21.
17.Slashdot, From January 29, 2005: http://science.slashdot.org /article.pl?sid=05/01/29/1815242tid=217tid=14
18.Chih-Chung Chang and Chih-Jen Lin, LIBSVM : a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/ cjlin/libsvm
19.P. Cimiano, S. Staab, Learning by googling, ACM SIGKDD Explorations Newsletter, 6:2 (December 2004), 24 – 33
20.H. Muir, Software to unzip identity of unknown composers, New Scientist, 12 April 2003.
21.K. Patch, Software sorts tunes, Technology Research News, April 23/30, 2003.
22.D. B. Lenat. Cyc: A large-scale investment in knowledge infrastructure, Comm. ACM, 38:11(1995),33–38.
23.F Keller, M Lapata, Using the web to obtain frequencies for unseen bigrams, Computational Linguistics, 29:3(2003), 459–484.
24.A.N. Kolmogorov. Three approaches to the quantitative definition of information, Problems Inform. Transmission, 1:1(1965), 1–7.
25.M. Li, J.H. Badger, X. Chen, S. Kwong, P. Kearney, and H. Zhang, An information-based sequence distance and its application to whole mitochondrial genome phylogeny, Bioinformatics, 17:2(2001), 149–154.
26.M. Li, X. Chen, X. Li, B. Ma, P. Vitanyi. The similarity metric, Iaa EEE Trans. Information Theory, 50:12(2004), 3250- 3264.
27.M. Li, P. M. B. Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications, 2nd Ed., Springer-Verlag, New York, 1997.
28.M. Li and P.M.B. Vitanyi. Algorithmic Complexity, pp. 376– 382 in: International Encyclopedia of the Social & Behavioral Sciences, N.J. Smelser and P.B. Baltes, Eds., Pergamon, Oxford, 2001/2002.
29.M. Li and P.M.B. Vitanyi, Reversibility and adiabatic computation: trading time and space for energy, Proc. Royal Society of London, Series A, 452(1996), 769-789.
30.S. L. Reed, D. B. Lenat. Mapping ontologies into cyc. Proc. AAAI Conference 2002 Workshop on Ontologies for the Semantic Web, Edmonton, Canada. http://citeseer.nj.nec.com/509238.html
31.D.H. Rumsfeld, The digital revolution, originally published June 9, 2001, following a European trip. In: H. Seely, The Poetry of D.H. Rumsfeld, 2003, http://slate.msn.com/id/2081042/
32.C. E. Shannon. A mathematical theory of communication. Bell Systems Technical J., 27(1948), 379–423 and 623–656.
33.G.A. Miller et.al, WordNet, A Lexical Database for the English Language, Cognitive Science Lab, Princeton University, http://www.cogsci.princeton.edu/ wn
34.E. Terra and C. L. A. Clarke. Frequency Estimates for Statistical Word Similarity Measures. HLT/NAACL 2003, Edmonton, Alberta, May 2003. 37/162
35.M.E. Lesk, Word-word associations in document retrieval systems, American Documentation, 20:1(1969), 27–38.
36.P.-N. Tan, V. Kumar, J. Srivastava, Selecting the right interestingness measure for associating patterns. Proc. ACM-SIGKDD Conf. Knowledge Discovery and Data Mining, 2002, 491–502.
37.T. Landauer and S. Dumais, A solution to Plato’s problem: The latent semantic analysis theory of acquisition, induction and representation of knowledge, Psychol. Rev., 104(1997), 211–240.
38.Corpus collosal: How well does the world wide web represent human language? The Economist, January 20, 2005. http://www.economist.com/science /displayStory.cfm?story id=3576374

Citation

MLA

Cilibrasi, R., and P. M. B. Vitanyi. “The Google Similarity Distance”. R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383, 2004, http://arxiv.org/abs/cs/0412098v3.

APA

Cilibrasi, R., & Vitanyi, P. M. B. (2004). The Google Similarity Distance. R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383. http://arxiv.org/abs/cs/0412098v3

Chicago

Cilibrasi, R., and P. M. B. Vitanyi. 2004. “The Google Similarity Distance”. R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383. http://arxiv.org/abs/cs/0412098v3.

Harvard

Cilibrasi, R. and Vitanyi, P.M.B. (2004) “The Google Similarity Distance”, R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383 [Preprint]. Available at: http://arxiv.org/abs/cs/0412098v3.

Vancouver

1. Cilibrasi R, Vitanyi PMB (2004) The Google Similarity Distance. R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383

BibTeX

@article{cilibrasi2004the,
  title = {The Google Similarity Distance},
  author = {Cilibrasi, Rudi and Vitanyi, Paul M. B.},
  year = {2004},
  journal = {R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383},
  url = {http://arxiv.org/abs/cs/0412098v3},
  eprint = {cs/0412098}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

The Google Similarity Distance

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Normalized Google Distance

Knowl 2 — Mathematical Properties of Normalized Google Distance

Knowl 3 — Universality of the Google Distribution

Knowl 4 — Universality of Normalized Google Distance

Knowl 5 — SVM-NGD Feature Representation for Concept Classification

Knowl 6 — WordNet Semantic Benchmark Performance

Knowl 7 — Bilingual Lexicon Translation via NGD Matrix Correlation

Knowl 8 — Hierarchical Clustering via NGD Distance Matrices

Knowl 9 — SVM-NGD Learning on Domain Tasks: Emergencies and Primes

Knowl 10 — Computational and Practical Limitations of Web Search Distance

References

Citation

BibTeX

Source Code

Access the Paper