Data Mining Molecular Computation and Bioinformatics Computational Complexity

Data Mining and Machine Learning

  1. C. Zhang, K. Kelsey, X. Shen, C. Ding, M. Hertz, and M. Ogihara. Program-level adaptive memory management. In Proceedings of the International Symposium on Memory Management (ISMM'06).
  2. C. Zhang, Y. Zhong, C. Ding, and M. Ogihara. A hierarchy model of data locality. In Proceedings of the 33rd Annual ACM Symposium on Principles of Programming Languages (POPL'06).
  3. T. Li and M. Ogihara. Toward intelligent music information retrieval. IEEE Transactions on Multimedia, in press.
  4. T. Li and M. Ogihara. Music genre classification with taxonomy. In Proceedings of the 2005 International Conference on Acoustic, Speech, and Signal Processing (ICASSP'05), pages V198-201, 2005.
  5. T. Li and M. Ogihara. Semi-supervised learning for music artist clasification. In Proceedings of the IEEE Conference on Information and Knowledge Management (CIKM'04), pages 152-153, 2004.
  6. T. Li, S, Ma, and M. Ogihara. On combining multiple clusterings. In Proceedings of the IEEE Conference on Information and Knowledge Management (CIKM'04), pages 294-303, 2004.
  7. T. Li and M. Ogihara. Music artist style identification by semisupervised learningmusic artist clasification. In Proceedings of the IEEE Conference on Information and Knowledge Management (CIKM'04), pages 152-153, 2004.
  8. T. Li, S. Ma, and M. Ogihara, Document clustering via adaptive subspace iteration. In Proceedings of the 12th ACM International Conference on Multimedia (MM'04), pages 364-367, 2004.
  9. T. Li, S. Ma, and M. Ogihara. Entropy-based criterion for categorical data clustering. In Proceedings of the 21st International Conference on Machine Learning (ICML'04), pages 536-543.
  10. T. Li and M. Ogihara. Content-based music similarity search and emotion detection. In Proceedings of the 2004 International Conference on Acoustic, Speech, and Signal Processing (ICASSP'04) IEEE Computer Society Press, pages V705-V708, 2004.
  11. T. Li and M. Ogihara. Semi-supervised learning from different information sources: an experimental investigation. KAIS Journal, in press.
  12. T. Li, S. Zhu, and M. Ogihara. Using Discriminant Analysis for Multi-class Classification. In Proceedings of the 2003 International Conference on Data Mining , pages 589-592, 2003.
  13. T. Li, S. Zhu, and M. Ogihara, Efficient multi-way text categorization via generalized discrimiant analysis. In Proceedings of the Twelfth International Conference on Information and Knowledge Management, pages 317-324, 2003.
  14. T. Li and M. Ogihara, Detecting emotion in music. In Proceedings of the Fifth International Symposium on Music Information Retrieval, pages 239-240, 2003.
  15. T. Li, M. Ogihara, and Q. Li, A comparative study on content-based music genre classification. In Proceedings of the 26th Annual International ACM Conference on Research and Development in Information Retrieval (SIGIR'03), pages 282-289. ACM Press, 2003.
  16. T. Li, S. Zhu, and M. Ogihara, Topic hierarchy generation via linear discrimant projection. In Proceedings of the 26th Annual International ACM Conference on Research and Development in Information Retrieval (SIGIR'03), pages 421-422. ACM Press, 2003.
  17. T. Li, S. Zhu, and M. Ogihara, A new distributed data mining model based on similarity. In Proceedings of the 18th Annual ACM Symposium on Applied Computing (SAC'03), pages 432-436, ACM Press, 2003.
  18. T. Li, Q. Li, S. Zhu, and M. Ogihara, A survey on wavelet applications in data mining. SIGKDD Explorations 4(2):49-68, 2003.
  19. T. Li, S. Zhu, and M. Ogihara, Algorithms for clustering high dimensional and distributed data. Intelligent Data Analysis 7(4):305-326, 2003.
  20. T. Li, M. Ogihara, and S. Zhu, Association-based similarity testing and its applications. Intelligent Data Analysis 7(3):209-232, 2003.
  21. T. Li, S. Zhu, M. Ogihara, and Y. Chen, Estimating joint probabilities from marginal ones. In Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery, pages 31-41. Springer-Verlag Lecture Notes in Computer Science Vol. 2454, 2002.
  22. S. Zhu, T. Li, M. Ogihara, and Y. Chen, CoFD: an algorithm for non-distance based clustering in high dimensional spaces. In Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery, pages 52-62. Springer-Verlag Lecture Notes in Computer Science Vol. 2454, 2002.
  23. T. Li, S. Zhu, and M. Ogihara. Mining patterns from case-based analysis. In ICDM'01 Workshop on Integrating Data Mining and Knowledge Management.
  24. S. Parthasarathy, M. J. Zaki, M. Ogihara, and W. Li. Parallel data mining for association rules on shared-memory systems. Knowledge and Information Systems 3(1):1-29, 2001.
  25. S. Parthasarathy, M. J. Zaki, M. Ogihara, and S. Dwarkadas, Sequence mining in dynamic and interactive environments. In W. Abramowicz and J. Zurada, eds., Knowledge Discovery for Business Information Systems, Chapter 16, pages 377--376. Kluwer Academic Publishers, 2001.
  26. M. J. Zaki, N. Lesh, and M. Ogihara. Predicting failures in event sequences. In R. Grossman, C. Kamath, P. Kegelmeyer, V. Kumar, and R. R. Namburu eds. Data Mining for Scientific and Engineering Applications Kluwer Academic Publishers, 2001.
  27. N. Lesh, M. J. Zaki, and M. Ogihara. PlanMine: predicting plan failures using sequence mining. Artificial Intelligence Review Special Issue on the Applications of Data Mining. 14(6):421-445, 2001.
  28. S. Parthasarathy and M. Ogihara. Exploiting dataset similarity for distributed mining. In J. P. Rolim et al., eds., Parallel and Distributed Processing, 15 IPDPS 2000 Workshops Proceedings, pages 390--398. Springer-Verlag Lecture Notes in Computer Science Volume 1800, 2000.
  29. S. Parthasarathy and M. Ogihara. Clustering distributed homogeneous datasets. In D. A. Zighed, H. J. Komorowski, and J. M. Zytkow, eds., Proceedings of the Fourth European Conference on Principles of Data Mining and Knowledge Discovery, pages 566--574. Springer-Verlag Lecture Notes in Computer Science Volume 1910, 2000.
  30. S. Parthasarathy, S. Dwarkadas, and M. Ogihara. Active Mining in a Distributed Setting.. In (M. Zaki and C. Ho, eds.), Large-Scale Parallel Data Mining, pages 65-82. Springer-Verlag Lecture Notes in Computer Science Volume 1759, 2000.
  31. N. Lesh, M. J. Zaki, and M. Ogihara. Scalable feature mining for sequential data. IEEE Transactions on Intelligent Systems and Their Applications, 15(2):48-55, 2000.
  32. S. Parthasarathy, M. J. Zaki, M. Ogihara, and S. Dwarkadas. Incremental and interactive sequence mining., In Proceedings of the 199 ACM International Conference on Information and Knowedge Management, pages 251--258, 1999.
  33. N. Lesh, M. J. Zaki, and M. Ogihara. Mining features for sequence classification. In Procedings of the 5th IEEE Conference on Knowledge Discovery and Data Mining, pages 342-346, 1999.
  34. M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. LI. Parallel algorithms for discovery of association rules. In P. Stolorz and R. Musick, eds., Scalable High Performance Computing for Knowledge Discovery and Data Mining. Kluwer Academic Publishers, 1998.
  35. M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. LI. Parallel algorithms for discovery of association rules. Data Mining and Knowledge Discovery 1:343--373, 1998.
  36. M. J. Zaki, N. Lesh, and M. Ogihara. PLANMINE: sequence mining for plan failures. In Proceedings of the 4th IEEE Conference on Knowledge Discovery and Data Mining, pages 369--373, 1998.
  37. M. J. Zaki and M. Ogihara. Theoretical foundation of association rules. Workshop on Data-Mining and Knowledge Discovery '98.
  38. M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. In Proceedings of the 3rd IEEE Conference on Knowledge Discovery and Data Mining, pages 283--286, 1997.
  39. M. J. Zaki, S. Parthasarathy, W. Li, and M. Ogihara. Evaluation of sampling for data mining of association rules. In Seventh IEEE International Workshop on Research Issues in Data Engineering, pages 42--50, 1997.
  40. M. J. Zaki, M. Ogihara, S. Parthasarathy, and W. Li. Parallel data mining for association rules on shared-memory multiprocessors. In Supercomputing '96.

Molecular Computation and Bioinformatics

  1. T. Li, C. Zhang, and M. Ogihara. A comparative study of feature selection and multiclass classification methods for tissue classification based on gene expression. Bioinformatics, 20:2421-2428, 2004.
  2. T. Li, S. Zhu, Q. Li, and M. Ogihara, Gene functional classification by semmi-supervised learning from heterogeneous data. In Proceedings of the 18th Annual ACM Symposium on Applied Computing (SAC'03), pages 78-82, ACM Press, 2003.
  3. R. Bijlani, Y. Cheng, A. Brooks, D. Pearce, and M. Ogihara. A biologically relevant classification approach to microarray data analysis: Independently Consistent Expression Discriminator (ICED). Bioinformatics19(1):69-80, 2003.
  4. M. Ogihara and A. Ray, The minimum-model DNA computation on a sequence of probe arrays. In Proceedings of the Third International Conference on Unconventional Models of Computation, pages 38-49. Springer-Verlag Lecture Notes in Computer Science #2509, 2002.
  5. S. Diaz, J. L. Esteban, and M. Ogihara, A DNA-based random walk method for solving k-SAT. Proceedings of the Sixth International Workshop on DNA-based Computers, Springer-Verlag Lecture Notes in Computer Science, 2000. GZIP-ed postscripted file GZIP-ed PDF file

  6. M. Ogihara and A. Ray, DNA computing on a chip. Nature 403:143--144, 2000.

  7. M. Ogihara, Relating the minimum model for DNA computation and Boolean circuits. Proceedings of the Genetic and Evolutionary Computation Conference, pages 1817--1821, Morgan Kaufman Publishers, San Francisco, CA, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  8. M. Ogihara and A. Ray, Executing parallel logical operations with DNA. Proceedings of the Congress on Evolutionary Computation, pages 972--979, IEEE Computer Society Press, Piscataway, NJ, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  9. M. Ogihara and A. Ray, Biomolecular computing---recent theoretical and experimental advances, SIGACT News , 30(2):22-30, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  10. M. Ogihara and A. Ray, DNA-based parallel computation by counting. In DNA Based Computers III, (H. Rubin and D. H. Wood, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 48 , The American Mathematics Society Press, pages 255--264, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  11. M. Ogihara and A. Ray, DNA-based self-propagating algorithm for solving bounded-fan-in Boolean circuits Third Conference on Genetic Programming, pages 725--730, Morgan Kaufman Publishers, San Francisco, CA, 1998. GZIP-ed postscripted file GZIP-ed PDF file

  12. M. Ogihara and A. Ray, Circuit evaluation: thoughts on a killer application in DNA computing, In Computing with Bio-Molecules. Theory and Experiments, G. Paun, ed., pages 111--126, Springer-Verlag, Singapore, 1998. GZIP-ed postscripted file GZIP-ed PDF file

  13. M. Ogihara and A. Ray, The minimum DNA computation model and its computational power. Unconventional Models of Computation (C. S. Calude, J. Casti, and M. J. Dinneen, eds.), pages 309--322, Springer, Singapore, 1998. GZIP-ed postscripted file GZIP-ed PDF file

  14. M. Ogihara and A. Ray, Simulating Boolean circuits on a DNA computer. First Annual Conference on Computational Molecular Biology, pages 326--331, ACM Press, 1997. The final version: Algorithmica 25:239--250, 1999. GZIP-ed postscripted file GZIP-ed PDF file

  15. M. Ogihara, A. Ray, and K. Smith, DNA computation---a shape of computing to come SIGACT News 28(3), pages 2--11, 1997. GZIP-ed postscripted file GZIP-ed PDF file

  16. M. Ogihara, Breadth first search 3SAT algorithms for DNA computers. Technical Report TR-629, Department of Computer Science, University of Rochester, July 1996. GZIP-ed postscripted file GZIP-ed PDF file


Computational Complexity Theory

  1. C. Glasser, M. Ogihara, A. Pavan, A. Selman, and L. Zhang. Autoreducibility, mitoticity, and immunity. In Proceedings of the 30th International symposium on Mathematical Foundations of Computer Science (MFCS'05), pages 387--398, 2005.
  2. P. Faliszewski and M. Ogihara. Separating the notions of self- and autoreducibility. In Proceedings of the 30th International symposium on Mathematical Foundations of Computer Science (MFCS'05), pages 308--315, 2005.
  3. L. Hemaspaandra , M. Ogihara, M. J. Zaki, and M. Zimand, The complexity of finding top-Toda-equivalence-class members. Theory of Computing SystemsSiences , in press.
  4. J. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara, Computing provers yield improved Karp-Lipton collapse results. Accepted for publication in Information and Computation.
  5. T. Tantau and M. Ogihara, On the Reducibility of Sets Inside NP to Sets with Low Information Content. Journal of Computer and System Sciences, 69(4):499-524, 2004.
  6. A. Beygelzimer M. Ogihara The enumerability of P collapses P to NC. In Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science, Springer-Verlag Lecture Notes in Computer Science Volume 3153, pages 364-355, 2004. Journal version, Theoretical Computer Science 345(2-3):248-259, 2005.
  7. R. Lipton, M. Ogihara, and Y. Zalcstein, A note on square rooting of time functions of Turing machines. Theory of Computing Systems 36(3):295-299, 2003. Also, available as Georgia Institute of Technology, College of Computing Technical Report GIT-CC-02-04.
  8. M. Ogihara and Y. Zalcstein, Testing simultaneous similarity of matrices and related problems for matrix semigroups Georgia Institute of Technology, College of Computing Technical Report GIT-CC-02-01.
  9. M. Liskiewicz, M. Ogihara, and S. Toda, Counting self-avoiding walks in some regular graphs. SIGACT News 34(3):26-39, 2003.

  10. A. Beygelzimer and M. Ogihara, The (non)enumerability of the determinant and the rank. Theory of Computing Systems 36(4):359-374, 2003. An earlier version is available as ECCC Technical Report TR02-016.

  11. J. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara, Some Karp-Lipton-Type Theorems Based on Sp2. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, pages 535-546, LNCS #2607, 2003.

  12. M. Liskiewicz, M. Ogihara, and S. Toda, The Complexity of Counting Self-Avoiding Walks in Subgraphs of Two-Dimensional Grid Graphs and in Hypercubes. Theoretical Computer Science 304(1-3):129-156, 2003.

  13. M. Ogihara and S. Toda, The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, pages 585--597. Springer-Verlag Lecture Notes in Computer Science Volume 2136, 2001.

  14. L. Hemaspaandra, M. Ogihara, and G. Wechsung, Reducing the number of solutions of NP functions. Proceedings of the Mathematical Foundations of Computer Science, Springer-Verlag Lecture Notes in Computer Science, vol. 1893, pages 394-404, 2000.

  15. J. Goldsmith, M. Ogihara, and J. Rothe, Tally NP sets and easy census functions. Information and Computation 158:29-52, 2000.
  16. E. Allender, R. Beals, and M. Ogihara, The complexity of matrix rank and feasible systems of linear equations , Computational Complexity 8:99--126, 1999.
  17. M. Ogihara, The PL hierarchy collapses. SIAM Journal of Computing 27:1430--1437, 1998.
  18. I. Macarie and M.Ogihara, Properties of Probabilistic Pushdown Automata. Theoretical Computer Science 207:117--130, 1998.
  19. G. Istrate and M. Ogihara, The phase transition in random horn satisfiability. The 5th International Symposium on Artificial Intelligence and Mathematics, 1998.
  20. L. Hemaspaandra, and M. Ogihara, Universally Serializable Computation, Journal of Computer and System Sciences 55:547--560, 1997.
  21. S. Fenner, S. Homer, M. Ogihara, and A. Selman, On using oracles that compute values. SIAM Journal on Computing 26:1043--1065, 1997.

  22. J. Cai and M. Ogihara, Sparse hard sets. In Complexity Theory Retrospective (L. A. Hemaspaandra and A. L. Selman, eds.), pages 53--80, Springer-Verlag, New York, 1997.
  23. D. van Melkebeek and M. Ogihara, Sparse hard sets for P. In Advances in Complexity and Algorithms (D. Du and K. Ko eds.), pages 191--208, Kluwer Academic Press, 1997.
  24. E. Hemaspaandra , A. Naik, M. Ogihara, and A. Selman, P-selective sets, and reducing search to decision vs. self-reducibility. Journal of Computer and System Sciences 53:194--209 (1996).
  25. M. Ogihara, T. Thierauf, S. Toda, and O. Watanabe, On closure properties of #P in the context of PF #P, Journal of Computer and System Sciences 53:171--179 (1996).
  26. L. Hemchandra, A. Hoene, and M. Ogihara, Reducibility classes of P-selective sets, Theoretical Computer Science 155(2):439--446 (1996); erratum: 234(1-2):323 (2000).
  27. M. Ogihara, Functions computable with limited access to NP. Information Processing Letters 58:35--38, 1996.
  28. M. Ogihara, Sparse hard sets for P yield space-efficient algorithms. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 354--361.
  29. M. Ogihara, Polynomial-time membership comparable sets. SIAM Journal on Computing 24(5):1168--1181 (1195).
  30. E. Allender and M. Ogihara, Relationships among PL, #L, and the determinant. RAIRO 30(1):1--21, 1996.
  31. L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman, Computing solutions uniquely collapses the polynomial hierarchy. SIAM Journal on Computing 25(4):597--608 (1996).
  32. M. Ogihara, On helping by parity-like languages. Information Processing Letters 54:41-43 (1995).
  33. J. Cai, R. Lipton, L. Longpré, M. Ogihara, K. Regan, and D. Sivakumar, Communication complexity of key agreement on limited ranges. Proceedings of the Twelfth Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag Lecture Notes in Computer Science #900, pages 38--49, (1995).
  34. L. Hemaspaandra, A. Hoene, A. Naik, M. Ogihara, A. Selman, T. Thierauf, and J. Wang, Nondeterministically selective sets. , International Journal on Foundation of Computer Science 6(4):403--416 (1995).
  35. M. Ogihara, Equivalence of NC^k and AC^{k-1} closures of NP and other classes. Information and Computation, 120(1), 56--59 (1995).
  36. M. Ogihara, On serializable languages. International Journal of Foundations of Computer Science 5(2&3):303-381 (1994).
  37. M. Ogiwara, Generalized theorems on the relationships among reducibility notions to certain complexity classes, Mathematical Systems Theory 27, 189--200 (1994).
  38. L. Hemachandra, M. Ogihara, and S. Toda, Space-efficient recognition of sparse self-reducible languages, Computational Complexity 4, 262--296 (1994).
  39. R. Beigel, R. Chang, and M. Ogiwara, A relationship between difference hierarchies and relativized hierarchies. Mathematical Systems Theory 26 (3), 293--310 (1993).
  40. M. Ogiwara and L. Hemachandra, A complexity theory for feasible closure properties. Journal of Computer and System Sciences 46 (3), 295--325 (1993).
  41. M. Ogiwara and A. Lozano, Sparse hard sets for counting classes. Theoretical Computer Science 112, 255--276 (1993).
  42. M. Ogiwara, A characterization of P^{C=P}. The Transactions of the Institute of Electronics, Information and Communication Engineers E75-D, 44--49 (1992).
  43. E. Allender, L. Hemachandra, M. Ogiwara, and O. Watanabe . Relating equivalence and reducibility to sparse sets. SIAM Journal on Computing 21, 551--539 (1992).
  44. M. Ogiwara and O. Watanabe, On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing 20, 471--483 (1991).