Rudi Cilibrasi

Prof. Rudi Cilibrasi

Petabyte Storage, Walnut Creek, California, USA
orcid

Research Focus & Metrics

Academic Career Length

24Years (2003-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
29 January 2007 in IEEE Transactions on Knowledge and Data Engineering
Verified
Journal Article
Closed access
RCRudi Cilibrasi
Rudi Cilibrasi
PVPaul M.B. Vitanyi
Paul M.B. Vitanyi
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

4 April 2005 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
RCRudi Cilibrasi
Rudi Cilibrasi
PVP.M.B. Vitanyi
P.M.B. Vitanyi
We present a new method for clustering based on compression. The method does not use subject-specific features or background knowledge, and works as follows: First, we determine a parameter-free, universal, similarity distance, the normalized compression distance or NCD, computed from the lengths of compressed data files (singly and in pairwise concatenation). Second, we apply a hierarchical clustering method. The NCD is not restricted to a specific application area, and works across application area boundaries. A theoretical precursor, the normalized information distance, co-developed by one of the authors, is provably optimal. However, the optimality comes at the price of using the noncomputable notion of Kolmogorov complexity. We propose axioms to capture the real-world setting, and show that the NCD approximates optimality. To extract a hierarchy of clusters from the distance matrix, we determine a dendrogram (ternary tree) by a new quartet method and a fast heuristic to implement it. The method is implemented and available as public software, and is robust under choice of different compressors. To substantiate our claims of universality and robustness, we report evidence of successful application in areas as diverse as genomics, virology, languages, literature, music, handwritten digits, astronomy, and combinations of objects from completely different domains, using statistical, dictionary, and block sorting compressors. In genomics, we presented new evidence for major questions in Mammalian evolution, based on whole-mitochondrial genomic analysis: the Eutherian orders and the Marsupionta hypothesis against the Theria hypothesis.

1 December 2004 in Computer Music Journal
Verified
Journal Article
Closed access
RCRudi Cilibrasi
Rudi Cilibrasi
PVPaul Vitányi
Paul Vitányi
RWRonald de Wolf
Ronald de Wolf

3 August 2007 in Algorithmica
Verified
Journal Article
Closed access
PDF file
RCRudi Cilibrasi
Rudi Cilibrasi
LILeo van Iersel
Leo van Iersel
SKSteven Kelk
Steven Kelk
JTJohn Tromp
John Tromp

1 March 2011 in Pattern Recognition
Verified
Journal Article
Closed access
RCRudi Cilibrasi
Rudi Cilibrasi
PVPaul M.B. Vitányi
Paul M.B. Vitányi

1 July 2006
Verified
Conference Paper
Closed access
RCRudi Cilibrasi
Rudi Cilibrasi
PVPaul Vitányi
Paul Vitányi
We consider similarity distances for two types of objects: literal objects that as such contain all of their meaning, like genomes or books, and names for objects. The latter may have literal embodiments like the first type, but may also be abstract like "red" or "Christianity". For the first type we consider a family of computable distance measures corresponding to parameters expressing similarity according to particular features between pairs of literal objects. For the second type we consider similarity distances generated by Web users corresponding to particular semantic relations between the (names for) the designated objects. For both families we give universal similarity distance measures, incorporating all particular distance measures in the family. In the first case the universal distance is based on compression and in the second case it is based on Google page counts related to search terms. In both cases experiments on a massive scale give evidence of the viability of the approaches