On string classification in data streams

ABSTRACT

String data has recently become important because of its use in a number of applications such as computational and molecular biology, protein analysis, and market basket data. In many cases, these strings contain a wide variety of substructures which may have physical significance for that application. For example, such substructures could represent important fragments of a DNA string or an interesting portion of a fraudulent transaction. In such a case, it is desirable to determine the identity, location, and extent of that substructure in the data. This is a much more difficult generalization of the classification problem, since the latter problem labels entire strings rather than deal with the more complex task of determining string fragments with a particular kind of behavior. The problem becomes even more complicated when different kinds of substrings show complicated nesting patterns. Therefore, we define a somewhat different problem which we refer to as the generalized classification problem. We propose a scalable approach based on hidden markov models for this problem. We show how to implement the generalized string classification procedure for very large data bases and data streams. We present experimental results over a number of large data sets and data streams.

REFERENCES

• 1: Charu C. Aggarwal, On effective classification of strings with wavelets, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775071]
• 2: Charu C. Aggarwal , Jiawei Han , Jianyong Wang , Philip S. Yu, On demand classification of data streams, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014110]
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: G. J. Barton. Protein Multiple Sequence Alignment and Flexible Pattern Matching. Methods in Enzymology, 183, 403--428, 1990.
• 5: G. A. Churchill. Stochastic Models for Heterogeneous DNA Sequences. Bull. Math Biol, 59, pp. 79--91, 1989.
• 6: M. Deshpande, G. Karypis. Evaluation of Techniques for Classifying Biological Sequences. Technical report, TR 01-33, University of Minnesota, 2001.
• 7: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 8: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 9: David Haussler , Anders Krogh , Saira Mian , Kimmen Sjolander, PROTEIN MODELING USING HIDDEN MARKOV MODELS: ANALYSIS OF GLOBINS, University of California at Santa Cruz, Santa Cruz, CA, 1992
• 10: D. Haussler, A. Krogh, I. S. Mian, K. Sjolander. Protein Modeling Using Hidden Markov Models: Analysis of Globins. Proceedings of the Hawaii International Conference on System Sciences, IEEE Computer Society Press, 1993.
• 11: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 12: K. Karplus, C. Barrett, R. Hughey. Hidden Markov Models for Detecting Remote Protein Homologies. Bioinformatics, 14(10): pp. 846--856, 1998.
• 13: Anders Krogh , Michael Brown , I. S Mian , Kimmen Sjolander , David Haussler, HIDDEN MARKOV MODELS IN COMPUTATIONAL BIOLOGY: APPLICATIONS TO PROTEIN MODELING, University of California at Santa Cruz, Santa Cruz, CA, 1993
• 14: Vinayak Borkar , Kaustubh Deshmukh , Sunita Sarawagi, Automatic segmentation of text into structured records, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.175-186, May 21-24, 2001, Santa Barbara, California, United States
• 15: W. R. Taylor. The Classification of Amino Acid Conservation. Journal of Theoretical Biology, 119, 205--218, 1986.
• 16: A. J. Viterbi. Error Bounds for Convolutional Codes and an Asymptotically Optimal Decoding Algorithm. IEEE Transactions on Information Theory, IT-13, 260--269, 1967.
• 17: M. S. Waterman. Sequence Alignments. Mathematical Methods for DNA Sequences, Waterman M. S. ed.. CRC Press, 1989.
• 18: ftp://ircache.nlanr.net/Traces/

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
classification, hidden markov models, string