The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Clustering by Compression
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The neighbor-joining method: a new method for reconstructing phylogenetic trees.
(1987) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040454 · Cited by 59,715
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Chiang, L. H., Russell, E. L., & Braatz, R. D. (2001) · Advanced Textbooks in Control and Signal Processing · doi:10.1007/978-1-4471-0347-9_3 · Cited by 5,003
Nonmetric Multidimensional Scaling: A Numerical Method
Kruskal, J. B. (1964) · Psychometrika · doi:10.1007/bf02289694 · Cited by 4,846
A Novel Coronavirus Associated with Severe Acute Respiratory Syndrome
Ksiazek, T. G., Erdman, D., Goldsmith, C. S., Zaki, S. R., Peret, T., Emery, S., Tong, S., Urbani, C., Comer, J. A., Lim, W., et al. (2003) · New England Journal of Medicine · doi:10.1056/nejmoa030781 · Cited by 4,344
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (2019) · Texts in Computer Science · doi:10.1007/978-3-030-11298-1 · Cited by 3,681
Musical genre classification of audio signals
Tzanetakis, G., & Cook, P. (2002) · IEEE Transactions on Speech and Audio Processing · doi:10.1109/tsa.2002.800560 · Cited by 2,798
Pattern Classification (2nd Edition)
Duda, R. O., Hart, P. E., & Stork, D. G. (2000) · Wiley-Interscience eBooks · Cited by 2,070
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (1997) · Springer eBooks · doi:10.1007/978-1-4757-2606-0 · Cited by 1,775
Genome-scale approaches to resolving incongruence in molecular phylogenies.
Rokas, A., Williams, B. L., King, N., & Carroll, S. B. (2003) · Nature · doi:10.1038/nature02053 · Cited by 1,512
Feature extraction methods for character recognition-A survey
Due Trier, Ø., Jain, A. K., & Taxt, T. (1996) · Pattern Recognition · doi:10.1016/0031-3203(95)00118-2 · Cited by 1,264
A philosophical essay on probabilities
(1952) · Journal of the Franklin Institute · doi:10.1016/0016-0032(52)90656-x · Cited by 1,136
Li, M., Chen, X., Li, X., Ma, B., & Vitanyi, P. M. B. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.838101 · Cited by 1,062
Self-citationAutomatically Categorizing Written Texts by Author Gender
Koppel, M. (2002) · Literary and Linguistic Computing · doi:10.1093/llc/17.4.401 · Cited by 623
Towards parameter-free data mining
Keogh, E., Lonardi, S., & Ratanamahatana, C. A. (2004) · Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1014052.1014077 · Cited by 567
An information-based sequence distance and its application to whole mitochondrial genome phylogeny
Li, M., Badger, J. H., Chen, X., Kwong, S., Kearney, P., & Zhang, H. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.2.149 · Cited by 527
Bennett, C. H., Gacs, P., Li, M., Vitanyi, P. M. B., & Zurek, W. H. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.681318 · Cited by 506
Self-citationKURTZMAN, C. (2003) · FEMS Yeast Research · doi:10.1016/s1567-1356(03)00175-2 · Cited by 460
Benedetto, D., Caglioti, E., & Loreto, V. (2002) · Physical Review Letters · doi:10.1103/physrevlett.88.048702 · Cited by 364
Shared Information and Program Plagiarism Detection
Chen, X., Francia, B., Li, M., McKinnon, B., & Seker, A. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.830793 · Cited by 251
Salomon, D. (1997) · Cited by 246
Conflict Among Individual Mitochondrial Proteins in Resolving the Phylogeny of Eutherian Orders
Cao, Y., Janke, A., Waddell, P. J., Westerman, M., Takenaka, O., Murata, S., Okada, N., Pääbo, S., & Hasegawa, M. (1998) · Journal of Molecular Evolution · doi:10.1007/pl00006389 · Cited by 234
Automatic recognition of handwritten numerical strings: a recognition and verification strategy
Oliveira, L. S., Sabourin, R., Bortolozzi, F., & Suen, C. Y. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2002.1046154 · Cited by 218
A Machine Learning Approach to Musical Style Recognition
Dannenberg, R. B., Thom, B., & Watson, D. (2018) · Figshare · doi:10.1184/r1/6587573 · Cited by 139
Communication complexity of document exchange
Cormode, G., Paterson, M. S., Şahinalp, S. C., & Vishkin, U. (2026) · Symposium on Discrete Algorithms · doi:10.82444/warw.33642076 · Cited by 128
Jiang, T., Kearney, P., & Li, M. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799361683 · Cited by 121
Hierarchical Clustering Based on Mutual InformationPreprint
Kraskov, A., Stögbauer, H., Andrzejak, R. G., & Grassberger, P. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.q-bio/0311039 · Cited by 118
Chain Letters and Evolutionary Histories
Bennett, C. H., Li, M., & Ma, B. (2003) · Scientific American · doi:10.1038/scientificamerican0603-76 · Cited by 111
Killian, J. K., Buckley, T. R., Stewart, N., Munday, B. L., & Jirtle, R. L. (2001) · Mammalian Genome · doi:10.1007/s003350020026 · Cited by 93
Janke, A., Magnell, O., Wieczorek, G., Westerman, M., & Árnason, Ú. (2002) · Journal of Molecular Evolution · doi:10.1007/s00239-001-0019-8 · Cited by 83
Discussion of Teleomorphic and Anamorphic Ascomycetous Yeasts and Yeast-like Taxa
Kurtzman, C. P. (2011) · Elsevier eBooks · doi:10.1016/b978-0-444-52149-1.00013-6 · Cited by 72
Information categorization approach to literary authorship disputes
Yang, A. C., Peng, C., Yien, H. W., & Goldberger, A. L. (2003) · Physica A Statistical Mechanics and its Applications · doi:10.1016/s0378-4371(03)00622-8 · Cited by 64
Ascomycetous Yeasts and Yeastlike Taxa
Kurtzman, C. P., & Sugiyama, J. (2001) · Springer eBooks · doi:10.1007/978-3-662-10376-0_9 · Cited by 27
Li, M., & Vitanyi, P. M. B. (2001) · Elsevier eBooks · doi:10.1016/b0-08-043076-7/00550-7 · Cited by 7
Self-citation
Cited by
The Google Similarity Distance
Cilibrasi, R. L., & Vitanyi, P. M. B. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.48 · Cited by 1,760
Self-citationA survey of modern authorship attribution methods
Stamatatos, E. (2009) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.21001 · Cited by 1,176
Li, M., Chen, X., Li, X., Ma, B., & Vitanyi, P. M. B. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.838101 · Cited by 1,062
Self-citationFormal theory of creativity, fun, and intrinsic motivation (1990–2010)
Schmidhuber, J. (2010) · IEEE Transactions on Autonomous Mental Development · doi:10.1109/tamd.2010.2056368 · Cited by 747
TSclust: An R Package for Time Series Clustering
Montero, P., & Vilar, J. A. (2014) · Journal of Statistical Software · doi:10.18637/jss.v062.i01 · Cited by 430
Metadata
- Authors
- Cilibrasi, R., & Vitanyi, P. M. B.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2005-04
- Volume
- 51
- Issue
- 4
- Pages
- 1523-1545
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2128859735
- Cited by
- 1,188
- References
- 34
- FWCI
- 56.79
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.