Alan P. Sprague

Associate Professor


Research Interests

Grammar Inference

  • Inferring a context free grammar for a domain specific language, given (positive) samples of the language.
  • Project web page

    Data Mining

  • Application to hospital infection control surveillance. A powerful motivator here is the increasing resistance by bacteria to antibiotics.
  • Theory which is inspired by applications. The work here so far has centered on algorithms for finding frequent sets.

    Graph Algorithms (plus also other discrete algorithms)

  • Algorithms for special classes of graphs. The emphasis here is on efficiency. Often, this involves exploring the "border" between polynomial time problems and NP-complete problems.
  • Disjoint paths in graphs.

    Education

    Ph.D. Computer Science, Ohio State University, 1988
    Advisor: Ten-Hwang Lai.
    Ph.D. Mathematics, Ohio State University, 1973
    Advisor: Dijen K. Ray-Chaudhuri.

    Recent Publications

    Grammar Inference

    Softcom Grammar Inference publications page

    Data Mining

    C. Wei, A.P. Sprague, and G. Warner. Clustering malware-generated spam emails with a novel fuzzy string matching algorithm. Submitted.

    Y. Liu and A.P. Sprague. Outlier detection and evaluation by network flow. Intl. J. Computer Applications in Technology (to appear).

    C. Wei, A.P. Sprague, and G. Warner. Detection of network blocks used by the Stormworm botnet. In Proc. ACM Southeast Conf. (ACMSE) , 2008.

    C. Wei, A.P. Sprague, G. Warner, and A. Skjellum. Mining spam email to identify common origins for forensic application. In Proc. ACM Symp. on Applied Computing (SAC) , pages 1432-1436, 2008.

    Y. Liu, X. Chen, C. Zhang, and A.P. Sprague. Semantic clustering for region-based image retrieval. In Proc. IEEE Intl. Symposium on Multimedia (ISM) , pages 167--172, 2007.

    Y. Liu, X. Chen, C. Zhang, and A.P. Sprague. An interactive region-based image clustering and retrieval platform. In Proc. IEEE Intl. Conf. on Multimedia and Expo (ICME) , pages 929--932, 2006.

    Y. Chen, K.D. Reilly, and A.P. Sprague. SEQOPTICS: a protein sequence clustering method. In Proc. Eighteenth Intl. Conf. Software Engg. and Knowledge Engg. (SEKE'06), pages 363-368, 2006.

    N. Garge, G. Page, A. Sprague, B. Gorman, and D. Allison. Reproducible clusters from microarray research: whither? BMC Bioinformatics, Vol 6 Supplemental issue 2, record No. S10, 2005.

    A.P. Sprague. On the computational complexity of two frequent set generation algorithms. In Proc. Intl. Conf. Machine Learning & Appl. (ICMLA) , pages 344-350, 2004. Expanded version: [pdf]

    D. Liu, A.P. Sprague, and J. Gray. PolyCluster: an interactive visualization approach to construct classification rules. In Proc. Intl. Conf. Machine Learning & Appl. (ICMLA) , pages 280-287, 2004.

    Y. Liu and A.P. Sprague. Outlier detection and evaluation by network flow. In Proc. Intl. Conf. Machine Learning & Appl. (ICMLA) , pages 436-442, 2004.

    D. Liu and A.P. Sprague. Mining multi-dimensional data with visualization techniques. In Lecture Notes on C. S. (Pacific Rim Intl. Conf. on A.I.: PRICAI), volume 3157 pages 934-935, 2004.

    D. Liu, A.P. Sprague, and J. Gray. Dynamically constructing classification rules with visualization techniques. In Intl. Conf. on Inf. and Knowledge Engg. (IKE), pages 126-131, 2004.

    Y. Chen, A.P.Sprague, and K.D. Reilly. MABAC - Matrix Based Clustering Algorithm. In Intl. Conf. on Algorithmic Math. and C. S. (AMCS), pages 439-443, 2004.

    J. Fisher and A.P. Sprague. Anchors: a technique of pre-classification and its effects on hidden Markov models. In Proc. ACM Southeast Conf., pages 234-239, 2004.

    Y. Chen and A.P. Sprague. Exploration on the commonality of hierarchical clustering algorithms. In Proc. ACM Southeast Conf., pages 246-247, 2004.

    Y. Liu, A.P. Sprague, and E. Lefkowitz. Network flow for outlier detection. In Proc. ACM Southeast Conf., pages 402-403, 2004.

    F. Javed, B.R. Bryant, M. Crepinsek, M. Mernik, and A.P. Sprague. Context-free grammar induction using genetic programming. In Proc. ACM Southeast Conf., pages 404-405, 2004.

    D. Liu, A.P. Sprague, and U. Manne. An interactive tool for data mining visualization. In Proc. ACM Southeast Conf., pages 442-447, 2004.

    J.E. Fisher, F. Hernandez, and A.P. Sprague. Language patterns: comparison and prediction using hidden Markov models. In Proc. ACM Southeast Conf., pages 246-250, 2003.

    S.E. Brossette, S.A. Moser, A.P. Sprague, J.M. Hardin, and W.T. Jones. DMSS: A knowledge discovery system for epimemiologic surveillance. In Proc. ACM Southeast Conf., pages 39-43, 2001.

    S.E. Brossette and A.P. Sprague. Medical surveillance, frequent sets, and closure operations. J. Combinatorial Optimization, 5: 81-94, 2001.

    S.E. Brossette, A.P. Sprague, W.T. Jones, and S.A. Moser. A data mining system for infection control surveillance. Methods of Information in Medicine, 39:303-310, 2000.

    S.E. Brossette, A.P. Sprague, J.M. Hardin, K.B. Waites, W.T. Jones, and S.A. Moser. Association rules and data mining in hospital infection control and public health surveillance. J. Amer. Medical Informatics Assn., 5:373-381, 1998.

    A.P. Sprague. Extracting optimal association rules over numeric attributes. In Proc. ACM Southeast Conf., pages 59-63, 1998.

    Graph Algorithms (plus also other discrete algorithms)

    R.E. Jamison and A.P. Sprague. Symmetry of extended representations of mix graphs and sum-product graphs. Congressus Numerantium , 182:111-128, 2006.

    A.P. Sprague. O(1) query time algorithm for all pairs shortest distances on permutation graphs. Discrete Appl. Math. , 155:365-373, 2007.

    T. Takaoka and A.P. Sprague. O(1) time algorithm for all pairs shortest distances on interval graphs. Intl. J. Foundations of Comput. Sci., 10:465-472, 1999.

    A.P. Sprague. NP-completeness of the domatic number problem on circular arc graphs. In Proc. ACM Southeast Conf., CD-ROM, 1999.

    H. Kim and A.P. Sprague. Optimal parallel matching on bipartite permutation graphs. Parallel Algo. Applic., 10:165-176, 1997.

    H. Kim and A.P. Sprague. Disjoint paths algorithms on cographs. Congressus Numerantium, 122:215-221, 1996.

    S. Natarajan and A.P. Sprague. Disjoint paths in circular arc graphs. Nordic J. Computing, 3:256-270, 1996.

    D.G. Corneil, H. Kim, S. Natarajan, S. Olariu, and A.P. Sprague. Simple linear time recognition of unit interval graphs. Inform. Process. Lett., 55:99-104, 1995.

    A.P. Sprague. Recognition of bipartite permutation graphs. Congressus Numerantium, 62:151-161, 1995.

    Finite State Automaton (Nondeterministic) Simulator