2012/12/31 by Andrew R. Cohen, Paul Vitányi, Paul M. B. Vitanyi · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Machine Learning and Algorithms #cs.CV #cs.IT #math.IT #physics.data-an
paper · pdf · doi:10.1109/tpami.2014.2375175
published as IEEE Trans. Pattern Analysis and Machine Intelligence, 37:8(2015), 1602-1614 · LaTeX 28 pages, 3 figures. This version is changed from the preliminary version to the final version. Updates of the theory. How to compute it, special recepies for classification, more applications and better results (see abstract and especially the detailed results in the paper). The title was changed to reflect this. In v4 corrected the proof of Theorem III-7
arxiv created 2013/03/29 · openalex publication_date 2014/11/26 · arxiv updated 2016/01/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Pairwise normalized compression distance (NCD) is a parameter-free, feature-free, alignment-free, similarity metric based on compression. We propose an NCD of multisets that is also metric. Previously, attempts to obtain such an NCD failed. For classification purposes it is superior to the pairwise NCD in accuracy and implementation complexity. We cover the entire trajectory from theoretical underpinning to feasible practice. It is applied to biological (stem cell, organelle transport) and OCR classification questions that were earlier treated with the pairwise NCD. With the new method we achieved significantly better results. The theoretic foundation is Kolmogorov complexity.