Special Issue: Implementation and Application of Automata: Invited PapersNo Access

INFORMATION DISTANCE AND ITS APPLICATIONS

MING LI

David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ont. N2L 3G1, Canada. .

https://doi.org/10.1142/S0129054107004905Cited by:9 (Source: Crossref)

Abstract

We have been developing a general theory of information distance and a paradigm of applying this theory to practical problems.[3, 19, 20] There are several problems associated with this theory. On the practical side, among other problems, the strict requirement of triangle inequality is unrealistic in some applications; on the theoretical side, the universality theorems for normalized information distances were only proved in a weak form. In this paper, we will introduce a complementary theory that resolves or avoids these problems.

This article also serves as a brief expository summary for this area. We will tell the stories about how and why some of the concepts were introduced, recent theoretical developments and interesting applications. These applications include whole genome phylogeny, plagiarism detection, document comparison, music classification, language classification, fetal heart rate tracing, question answering, and a wide range of other data mining tasks.

Some preliminary results and writings of this paper appeared in CIAA'06 and KDD'07.

Keywords:

References

C. Ané and M. J. Sanderson, Systematic Biology 54(1), 146 (2005). Crossref, Web of Science, Google Scholar
T. Arbuchle et al. , Software documents: comparison and measurement , SEKE 2007 . Google Scholar
C. H. Bennettet al., IEEE Trans. Inform. Theory 44(4), 1407 (1998), DOI: 10.1109/18.681318. Crossref, Web of Science, Google Scholar
C. H. Bennett, M. Li and B. Ma, Scientific American 288(6), 76 (2003). Crossref, Web of Science, Google Scholar
D. Benedetto, E. Caglioti and V. Loreto, Phys. Rev. Lett. 88(4), 048702 (2002), DOI: 10.1103/PhysRevLett.88.048702. Crossref, Web of Science, Google Scholar
X. Chenet al., IEEE Trans. Information Theory 50(7), 1545 (2004), DOI: 10.1109/TIT.2004.830793. Crossref, Web of Science, Google Scholar
A. V. Chernovet al., Theoret. Comput. Sci. 271, 69 (2002), DOI: 10.1016/S0304-3975(01)00032-9. Crossref, Web of Science, Google Scholar
R. Cilibrasi, P. Vitányi and R. de Wolf, Comput. Music J. 28(4), 49 (2004), DOI: 10.1162/0148926042728449. Crossref, Web of Science, Google Scholar
R. Cilibrasi and P. Vitányi, Automatic semantics using Google, manuscript, 2005. http://arxiv.org/abs/cs.CL/0412098 (2004) . Google Scholar
R. Cilibrasi and P. Vitányi, IEEE Trans. Inform. Theory 51(4), 1523 (2005), DOI: 10.1109/TIT.2005.844059. Crossref, Web of Science, Google Scholar
M. Cuturi and J. P. Vert, Neural Networks 18(4), 1111 (2005), DOI: 10.1016/j.neunet.2005.07.010. Crossref, Web of Science, Google Scholar
K. Emanuel, S. Ravela, E. Vivant, C. Risi, A combined statistical-deterministic approach of hurricane risk assessment, manuscript, Program in Atmospheres, Oceans, and Climate, MIT, 2005 . Google Scholar
R. Fagin and L. Stockmeyer, Int'l. J. Comput. Vision 28(3), 219 (1998). Web of Science, Google Scholar
E. Keogh, S. Lonardi and C. A. Ratanamahatana, Towards parameter-free data mining, KDD'2004 pp. 206–215. Google Scholar
S. R. Kirk and S. Jenkins, J. Systems and Software 72, 179 (2004), DOI: 10.1016/S0164-1212(03)00217-6. Crossref, Web of Science, Google Scholar
A. Kraskovet al., Europhys. Lett. 70(2), 278 (2005), DOI: 10.1209/epl/i2004-10483-y. Crossref, Google Scholar
A. Kocsoret al., Bioinformatics 22(4), 407 (2006), DOI: 10.1093/bioinformatics/bti806. Crossref, Web of Science, Google Scholar
N. Krasnogor and D. A. Pelta, Bioinformatics 20(7), 1015 (2004), DOI: 10.1093/bioinformatics/bth031. Crossref, Web of Science, Google Scholar
M. Liet al., Bioinformatics 17(2), 149 (2001), DOI: 10.1093/bioinformatics/17.2.149. Crossref, Web of Science, Google Scholar
M. Liet al., IEEE Trans. Information Theory 50(12), 3250 (2004), DOI: 10.1109/TIT.2004.838101. Crossref, Web of Science, Google Scholar
M. Li and P. Vitányi, An introduction to Kolmogorov complexity and its applications, 2nd edn. (Springer-Verlag, 1997) p. xx+637. Crossref, Google Scholar
An. A. Muchnik, Theoretical Computer Science 271(1), 97 (2002), DOI: 10.1016/S0304-3975(01)00033-0. Crossref, Web of Science, Google Scholar
An. A. Muchnik and N. K. Vereshchagin, Logical operations and Kolmogorov complexity II, Proc. 16th Conf. Comput. Complexity (2001) pp. 256–265. Google Scholar
H. H. Otu and K. Sayood, Bioinformatics 19(6), 2122 (2003), DOI: 10.1093/bioinformatics/btg295. Crossref, Web of Science, Google Scholar
H. K. Pao and J. Case , Computing entropy for ortholog detection , Int'l Conf. Comput. Intell. . Google Scholar
D. Parry , Use of Kolmogorov distance identification of web page authorship, topic and domain , Workshop on Open Source Web Inf. Retrieval ( 2005 ) , http://www.emse.fr/OSWIR05/ . Google Scholar
C. Costa Santos et al. , Clustering fetal heart rate tracings by compression , Proc. 19th IEEE Intn'l Symp. Computer-Based Medical Systems . Google Scholar
A. K. Shen and N. K. Vereshchagin, Theoret. Comput. Sci. 271, 125 (2002), DOI: 10.1016/S0304-3975(01)00035-4. Crossref, Web of Science, Google Scholar
W. Taha, S. Crosby, and K. Swadi, A new approach to data mining for software design, manuscript, Rice Univ. 2006 . Google Scholar
J. S. Varre, J. P. Delahaye and E. Rivals, Bioinformatics 15(3), 194 (1999), DOI: 10.1093/bioinformatics/15.3.194. Crossref, Web of Science, Google Scholar
R. C. Veltkamp, Shape Matching: Similarity Measures and Algorithms, invited talk, Proc. Int 'l Conf. Shape Modeling Applications (2001) pp. 188–197. Google Scholar
N. K. Vereshchagin and M. V. V'yugin, Theoret. Comput. Sci. 271, 131 (2002), DOI: 10.1016/S0304-3975(01)00036-6. Crossref, Web of Science, Google Scholar
M. V. V'yugin, Theoret. Comput. Sci. 271, 145 (2002). Crossref, Web of Science, Google Scholar
X. Zhang et al. , Information distance from a question to an answer , 13th ACM SIGKDD Int'l Conf. Knowledge Discovery Data Mining . Google Scholar