The similarity metric

By Ming Li, Xin Chen, Xin Li, Bin Ma, Paul M. B. Vitányi. IEEE Transactions on Information Theory, 2001

1,336 citations recorded by the source corpus.

A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new "normalized information distance," based on the noncomputable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it discovers all computable similarities). We demonstrate that it is a metric and call it the similarity metric . This theory forms the foundation for a new practical tool. To evidence generality and robustness, we give two distinctive applications in widely divergent areas using standard compression programs like gzip and GenCompress. First, we compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree. Secondly, we fully automatically compute the language tree of 52 different languages.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/2238b7dab181e26bbd879946866b2333c0269f38

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

In Molecular Biology

Citations in the corpus

Author ' s personal copy A Fast Quartet tree heuristic for hierarchical clustering (2010, methodology): “The algorithm does not address the problem of how to obtain the quartet topology weights from sequence data [25,30,32], but takes as input the weights of all quartet topologies and executes the step of how to reconstruct the hierarchical clustering from there.”
Detecting visually similar Web pages: Application to phishing detection (2010, background): “4.1 Normalized Compression Distance Normalized Compression Distance (NCD) is described as a parameter-free distance metric that is believed to be able to uncover all similarities with a single metric [Li et al. 2004; Cilibrasi and Vitanyi 2005].”
Causal Inference Using the Algorithmic Markov Condition (2008, background): “To state it we first have to introduce the following graph-theoretical concept.”
Estimating relatedness via data compression (2006, methodology): “…of framing the relationship between compression and re-latedness is to investigate under what conditions a multitask learning algorithm can be used to provide compression, in the style of Schapire (Schapire, 1990), Board and Pitt (Board & Pitt, 1990), Li et al (Li et al., 2003b), and many others.”
Shared information and program plagiarism detection (2004, methodology): “Meanwhile, three problems [22] that plague most of the other metrics may all be viewed as special cases of d(x; y).”
Duplicate and fake publications in the scientific literature: how many SCIgen papers in computer science? (2012, neutral): “Some indices based on compression have also been tested [17].”
Alignment-free sequence comparison: benefits, applications, and tools (2017, background): “Once the complexities of the sequences are calculated, a measure of their differences (e.g., the normalized compression distance [62]) can be easily computed.”
TSclust: An R Package for Time Series Clustering (2014, methodology): “Other dissimilarity measures are aimed to compare levels of complexity of time series (see, e.g., Li, Chen, Li, Ma, and Vit´anyi 2004; Sculley and Brod-ley 2006; Keogh, Lonardi, Ratanamahatana, Wei, Lee, and Handley 2007; Brandmaier 2011; Batista et al. 2011).”
k-Nearest Neighbour Classifiers (2007, background): “[15] refer to this as The similarity metric.”
k-Nearest Neighbour Classifiers - A Tutorial (2020, background): “is an effective measure for capturing similarity between images. Compression-Based Dissimilarity In recent years the idea of basing a similarity metric on compression has received a lot of attention. [30, 24]. Indeed Li et al. [30], refer to this as The similarity metric. The basic idea is quite str”
Measuring semantic similarity between words using web search engines (2007, methodology): “NGD is based on normalized information distance [19] which is defined using Kolmogorov complexity.”
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):”
Automated Classification and Analysis of Internet Malware (2007, background): “[16] as an optimal similarity metric to approximate all other effective similarity metrics.”