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 | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.jcss.2010.06.018 | Software - Practice and Experience |
Keywords | DocType | Volume |
nonapproximability.,complexity property,theoretical notion,theoretical precursor,kolmogorov complexity,real-world compression program,practical application,practical purpose,normalized information distance,lower semicomputable,index terms— normalized information distance,normalized compression distance,indexing terms,pattern recognition,data mining | Journal | 77 |
Issue | ISSN | Citations |
4 | 0022-0000 | 7 |
PageRank | References | Authors |
0.59 | 12 | 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 |