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.
- C. C. Aggarwal. On Effective Classification of Strings with Wavelets. ACM KDD Conference, 2002. Google ScholarDigital Library
- C. C. Aggarwal, J. Han, J. Wang, P. S. Yu. On Demand Classification of Data Streams. ACM KDD Conference, 2004. Google ScholarDigital Library
- R. Agrawal, R. Srikant. Fast Algorithms for Mining Association Rules. VLDB Conference, 1994. Google ScholarDigital Library
- G. J. Barton. Protein Multiple Sequence Alignment and Flexible Pattern Matching. Methods in Enzymology, 183, 403--428, 1990.Google Scholar
- G. A. Churchill. Stochastic Models for Heterogeneous DNA Sequences. Bull. Math Biol, 59, pp. 79--91, 1989.Google ScholarCross Ref
- M. Deshpande, G. Karypis. Evaluation of Techniques for Classifying Biological Sequences. Technical report, TR 01-33, University of Minnesota, 2001.Google Scholar
- P. Domingos, G. Hulten. Mining High-Speed Data Streams. ACM SIGKDD Conference, 2000. Google ScholarDigital Library
- D. Gusfield. Algorithms on Strings, Trees and Sequences. Press Syndicate of the University of Cambridge, 1997. Google ScholarDigital Library
- D. Haussler, A. Krogh, I. S. Mian, K. Sjolander. Protein Modeling using Hidden Markov Models: Analysis of Globins. Technical Report UCSC-CRL-92-23, University of California at Snta Cruz Computer Science, Santa Cruz, CA, 1992. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- G. Hulten, L. Spencer, P. Domingos. Mining Time-Changing Data Streams. ACM KDD Conference, 2001. Google ScholarDigital Library
- K. Karplus, C. Barrett, R. Hughey. Hidden Markov Models for Detecting Remote Protein Homologies. Bioinformatics, 14(10): pp. 846--856, 1998.Google ScholarCross Ref
- A. Krogh, M. Brown, T. S. Mian, K. Sjolander, D. Haussler. Hidden Markov Models in Computational Biology: Applications to Protein Modeling. University of California Technical Report UCSC-CRL-93-32, 1993. Google ScholarDigital Library
- V. Borkar, K. Deshmukh, S. Sarawagi. Automatic Segmentation of Text into Structured Records. SIGMOD Conference, 2001. Google ScholarDigital Library
- W. R. Taylor. The Classification of Amino Acid Conservation. Journal of Theoretical Biology, 119, 205--218, 1986.Google ScholarCross Ref
- A. J. Viterbi. Error Bounds for Convolutional Codes and an Asymptotically Optimal Decoding Algorithm. IEEE Transactions on Information Theory, IT-13, 260--269, 1967.Google ScholarDigital Library
- M. S. Waterman. Sequence Alignments. Mathematical Methods for DNA Sequences, Waterman M. S. ed. CRC Press, 1989.Google Scholar
- ftp://ircache.nlanr.net/Traces/Google Scholar
Index Terms
- On string classification in data streams
Recommendations
Inferring an indeterminate string from a prefix graph
An indeterminate string (or, more simply, just a string) x = x 1 . . n ] on an alphabet Σ is a sequence of nonempty subsets of Σ. We say that x i 1 ] and x i 2 ] match (written x i 1 ] x i 2 ] ) if and only if x i 1 ] x i 2 ] . A feasible array is an ...
How many runs can a string contain?
Given a string x=x[1..n], a repetition of period p in x is a substring u^r=x[i+1..i+rp], p=|u|, r>=2, where neither u=x[i+1..i+p] nor x[i+1..i+(r+1)p+1] is a repetition. The maximum number of repetitions in any string x is well known to be @Q(nlogn). A ...
How many double squares can a string contain?
Counting the types of squares rather than their occurrences, we consider the problem of bounding the number of distinct squares in a string. Fraenkel and Simpson showed in 1998 that a string of length n contains at most 2 n distinct squares. Ilie ...
Comments