Name
Abstract | ||
|---|---|---|
Normalized information distance (NID) uses the theoretical notion of
Kolmogorov complexity, which for practical purposes is approximated by the
length of the compressed version of the file involved, using a real-world
compression program. This practical application is called 'normalized
compression distance' and it is trivially computable. It is a parameter-free
similarity measure based on compression, and is used in pattern recognition,
data mining, phylogeny, clustering, and classification. The complexity
properties of its theoretical precursor, the NID, have been open. We show that
the NID is neither upper semicomputable nor lower semicomputable. |
Year | Venue | Keywords |
|---|---|---|
2010 | Computing Research Repository | semicomputability.,kolmogorov complexity,index terms— normalized information distance |
Field | DocType | Volume |
Discrete mathematics,Normalization (statistics),Kolmogorov complexity,Similarity measure,Information distance,Normalized compression distance,Algorithm,Cluster analysis,Mathematics | Journal | abs/1006.3 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sebastiaan A. Terwijn | 1 | 186 | 21.06 |
| Leen Torenvliet | 2 | 290 | 41.73 |
| Paul Vitányi | 3 | 2130 | 287.76 |