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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
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
Connecting users across social media sites: a behavioral-modeling approach
Zafarani, R., & Liu, H. (2013) · Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2487575.2487648 · Cited by 408
COMET: adaptive context-based modeling for ultrafast HIV-1 subtype identification
Struck, D., Lawyer, G., Ternes, A.-M., Schmit, J.-C., & Bercoff, D. P. (2014) · Nucleic Acids Research · doi:10.1093/nar/gku739 · Cited by 381
A Comparison of Personal Name Matching: Techniques and Practical Issues
Christen, P. (2006) · Sixth IEEE International Conference on Data Mining - Workshops (ICDMW'06) · doi:10.1109/icdmw.2006.2 · Cited by 331
Paulovich, F. V., Nonato, L. G., Minghim, R., & Levkowitz, H. (2008) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2007.70443 · Cited by 316
A study of deep convolutional auto-encoders for anomaly detection in videos
Ribeiro, M., Lazzaretti, A. E., & Lopes, H. S. (2018) · Pattern Recognition Letters · doi:10.1016/j.patrec.2017.07.016 · Cited by 308
Springer Handbook of Science and Technology Indicators
(2019) · Springer Handbooks · doi:10.1007/978-3-030-02511-3 · Cited by 300
Graph Summarization Methods and Applications: A Survey
Liu, Y., Safavi, T., Dighe, A., & Koutra, D. (2019) · ACM Computing Surveys · doi:10.1145/3186727 · Cited by 274
A comparison of code similarity analysers
Ragkhitwetsagul, C., Krinke, J., & Clark, D. (2018) · Empirical Software Engineering · doi:10.1007/s10664-017-9564-7 · Cited by 122
Prediction and prevention of hypoglycaemic events in type-1 diabetic patients using machine learning
Vehí, J., Contreras, I., Oviedo, S., Biagi, L., & Bertachi, A. (2020) · Health Informatics Journal · doi:10.1177/1460458219850682 · Cited by 76
Firdaus, A., Anuar, N. B., Razak, M. F. A., Hashem, I. A. T., Bachok, S., & Sangaiah, A. K. (2018) · Journal of Medical Systems · doi:10.1007/s10916-018-0966-x · Cited by 73
Efficient DNA sequence compression with neural networks
Silva, M., Pratas, D., & Pinho, A. J. (2020) · GigaScience · doi:10.1093/gigascience/giaa119 · Cited by 57
FigurA11y: AI Assistance for Writing Scientific Alt Text
Singh, N., Wang, L. L., & Bragg, J. (2024) · Proceedings of the 29th International Conference on Intelligent User Interfaces · doi:10.1145/3640543.3645212 · Cited by 42
Compression ensembles quantify aesthetic complexity and the evolution of visual art
Karjus, A., Canet Solà, M., Ohm, T., Ahnert, S. E., & Schich, M. (2023) · EPJ Data Science · doi:10.1140/epjds/s13688-023-00397-3 · Cited by 32
Predicting phenotype transition probabilities via conditional algorithmic probability approximations
Dingle, K., Novev, J. K., Ahnert, S. E., & Louis, A. A. (2022) · Journal of the Royal Society Interface · doi:10.1098/rsif.2022.0694 · Cited by 13
Yoshizawa, S., Terano, T., & Yoshikawa, A. (2012) · IEEE Transactions on Professional Communication · doi:10.1109/tpc.2011.2172833 · Cited by 11
Detecting translations of the same text and data with common source
Koroutchev, K., & Cebrián, M. (2006) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2006/10/p10009 · Cited by 9
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.