Sally A. Goldman, Ph.D.
The Edwin H. Murty Professor of Engineering
Department of Computer Science and Engineering
Campus Box 1045
Washington University
One Brookings Drive
St. Louis, Missouri 63130-4899
Department: (314) 935-6160
FAX: (314) 935-7302 
Currently on leave at Google Research.

New Book: A Practical Guide to Data Structures and Algorithms Using Java, Sally A. Goldman and Kenneth J. Goldman

"I highly recommend this book for both practioneers and students learning data structures and algorithms." Andries van Dam, Professor of Computer Science, Brown University.

"This is no ordinary textbook on algorithms and data structures. In fact, it really is not a textbook at all but rather an extraordinarily powerful and practical reference book." Robert Schapire, Professor of Computer Science, Princeton University.

"The Goldmans' new book is a tour de force of data structures and associated algorithms, accomplishing more than any single author could hope to achieve. ... I intend to make sure my students consult it before launching into any significant implementation." Ellen Witte Zegura, Professor and Associate Dean, Division Chair, Computing Science and Systems Division, Georgia Institute of Technology.

"This is the first book I know of that teachs the theory and practice of algorithm and data structures in a clear and comprehensive way." Monika Henzinger, Director of Research at Google and Professor of Computer and Communication Science at Ecole Polytechnique Federale de Lausanne, Switzerland.

If you are an instructor considering this book for a class, contact Susie Carlisle ( for a 45 day review copy.


Accio! -- A Localized Content-Based Image Retrieval System

Multiple Instance Data Sets

Research Interests
Professional Activites
Recent Publications
Journal Publications
Graduate Students
Research Funding
Brief Biography

Research Interests

Professional Activities

Recent Publications (not yet published in a journal)

o MI-Winnow: A New Multiple-Instance Learning Algorithm. In Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pages 336-343, November 2006. (With Sharath Cholleti and Rouhollah Rahmani).

o Local Image Representation Using Pruned Salient Points with Applications to CBIR. In Proceedings of the 14th Annual ACM International Conference on Multimedia (ACM Multimedia), pages 287-296, October 2006. (With Hui Zhang, Rouhollah Rahmani, and Sharath Cholleti).

o Image Segmentation Using Salient Points-Based Object Templates. In Proceedings of the 13th International Conference on Image Processing (ICIP), pages 765-768, October 2006. (With Hui Zhang.)

o MISSL: Multiple-Instance Semi-Supervised Learning. In Proceedings of the 23rd International Conference on Machine Learning (ICML), pages 705-712, June 2006. (With Rouhollah Rahmani.)

o Meta-Evaluation of Image Segmentation Using Machine Learning In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1138-1145, June 2006. (With Hui Zhang, Sharath Cholleti, and Jason Fritts.)

o Perceptual Information of Images and the Bias in Homegeneity-based Segmentation In Proceedings of the 5th IEEE Workshop on Perceptual Organization in Computer Vision (POCV), June 2006. (With Hui Zhang.)

o Localized Content-Based Image Retrieval (invited paper). In Proceedings of ACM Workshop on Multimedia Image Retrieval, pages 227-236, November 2005. (With Rouhoullah Rahmani, Hui Zhang, John Krettek, and Jason Fritts.)

o A Co-evaluation Framework for Improving Segmentation Evaluation. In Proceedings of IS&T/SPIE's Deense and Security Symposium -- Signal Processing, Sensor Fusion and Target Recognition XIV, SPIE Vol. 5809, March 2005. (With Hui Zhang and Jason Fritts).

o A Fast Texture Feature Extraction Method for Region-based Image Segmentation. In Proceedings of IS&T/SPIE's 16th Annual Symposium on Image and Video Communication and Processing, SPIE Vol. 5685, January 2005. (With Hui Zhang and Jason Fritts).

o Democratic Co-Learing. In Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2004), pages 594-602, November 2004. (With Yan Zhou).

o An Entropy-based Objective Evaluation Method for Image Segmentation. In Proceedings of IS&T/SPIE's 16th Annual Symposium on Electronic Imaging Conference on Storage and Retrieval Methods and Applications for Multimedia, SPIE Vol. 6307, pages 682-689, January 2004. (With Hui Zhang and Jason Fritts).

o Content-Based Image Retrieval Using Multiple-Instance Learning published in the Proceedings of the Nineteenth International Conference on Machine Learning (ICML 2002), pages 682-689, July 2002. (With Qi Zhang, Wei Yu, and Jason Fritts).

o EM-DD: An Improved Multiple-Instance Learning Technique published in the Proceedings of Neural Information Processing Systems (NIPS 2001), 2001 (With Qi Zhang).

o Enhancing Supervised Learning with Unlabeled Data. In the Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), pages 327-334, June 2000. (With Yan Zhou.)

Journal Publications

o Localized Content Based Image Retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, Special Issue, November 2008, in press. (with Rouhollah Rahmani, Hui Zhang, Sharath R. Cholleti, and Jason E. Fritts.)

o Image Segmentation Evaluation: A Survey of Unsupervised Methods. Computer Vision and Image Understanding, 10(2):260-280, May 2008. (with Hui Zhang and Jason E. Fritts.)

o Smartacking: Improving TCP Performance from the Receiving End. Journal of Internet Engineering, 1(1):6-21, January 2007. (with Daniel K. Blandford, Sergey Gorinsky, Yan Zhou, and Daniel R. Dooly.)

o Real-Valued Multiple-Instance Learning with Queries. Journal of Computer and System Sciences, 72(1): 1-15, February 2006. (with Daniel R. Dooly and Stephen S. Kwek.)

o Multi-Instance Learning of Real-Valued Geometric Concepts. Annals of Mathematics and Artificial Intelligence, 39(3): 259-290, November 2003. AMAI Special Issue on Knowledge Discovery and Learning. (With Stephen D. Scott.)

o Learning From Examples With Unspecified Attribute Values. Information and Computation, 180(2):82-100, January 2003. (With Stephen S. Kwek and Stephen D. Scott.)

o Multiple-Instance Learning of Real-Valued Data. Journal of Machine Learning Research, 3: 651-678, December 2002. Special Issue on ICML 2001. (With Robert A. Amar, Daniel R. Dooly, and Qi Zhang.)

o On Learning Unions of Pattern Languages and Tree Patterns in the Mistake Bound Model. Theoretical Computer Science, 288(2):237-254, October 2002. Special Issue on ALT 1999. (With Stephen S. Kwek).

o Daniel R. Dooly, Sally A. Goldman and Stephen D. Scott. On-line Analysis of the TCP Acknowledgement Delay Problem. Journal of the ACM, 48(2): 243-273, March 2001.

o Sally A. Goldman, Stephen S. Kwek and Stephen D. Scott. Agnostic Learning of Geometric Patterns. Journal of Computer and System Sciences, 62(1): 123-151, February 2001.

o Sally A. Goldman, Jyoti Parwatikar, and Subhash Suri. On-line Scheduling with Hard Deadlines. Journal of Algorithms, 34(2): 370-389, February 2000.

o Sally A. Goldman and Stephen D. Scott. A Theoretical and Empirical Study of a Noise-Tolerant Algorithm to Learn Geometric Patterns. Machine Learning, 37(1): 5-49, October 1999.

o Nader H. Bshouty, Paul W. Goldberg, Sally A. Goldman, and H. David Mathias. Exact Learning of Discretized Geometric Concepts. SIAM Journal on Computing, 28(2): 674-699, April 1999.

o Nader Bshouty, Sally Goldman, and David Mathias. Noise-Tolerant Parallel Learning of Geometric Concepts. Information and Computation, 147(1): 89-110, November 1998.

o Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, and Hisao Tamaki. Noise-Tolerant Distribution-Free Learning of General Geometric Concepts. Journal of the ACM, 45(5): 863-890, September 1998.

o Avrim Blum, Prasad Chalasani, Sally Goldman, and Donna Slonim. Learning with Unreliable Boundary Queries. Journal of Computer and System Sciences, 56(2):209-222, April 1998. (COLT '95 Special Issue).

o Paul Goldberg, Sally Goldman, and Stephen Scott. PAC Learning of One-Dimensional Patterns. Machine Learning, 25(1): 51-70, October 1996.

o Mike Frazier, Sally Goldman, Nina Mishra, and Lenny Pitt. Learning From a Consistently Ignorant Teacher. Journal of Computer and System Sciences, 52(3):472-492, June 1996. (COLT '94 Special Issue ).

o Nader H. Bshouty, Sally A. Goldman, Thomas R. Hancock, and Sleiman Matar. Asking Questions to Minimize Errors. Journal of Computer and System Sciences, 52(2):268-286, April 1996. (COLT '93 Special Issue ).

o Sally A. Goldman and H. David Mathias. Teaching a Smarter Learner. Journal of Computer and System Sciences, 52(2):255-267, April 1996. (COLT '93 Special Issue ).

o Sally A. Goldman and Manfred K. Warmuth. Learning Binary Relations Using Weighted Majority Voting. Machine Learning, 20(3):245-271, September 1995.

o Sally A. Goldman and Robert H. Sloan. Can PAC Learning Algorithms Tolerate Random Attribute Noise? Algorthmica, 14(1):70-84, July 1995.

o Sally A. Goldman, Michael J. Kearns, and Robert E. Schapire. On the Sample Complexity of Weak Learning. Information and Computation, 117(2):276-287, March 1995.

o Sally A. Goldman and Michael J. Kearns. On the Complexity of Teaching. Journal of Computer and System Sciences, 50(1):20-31, February 1995.

o Sally A. Goldman and Robert H. Sloan. On the Power of Self-Directed Learning. Machine Learning, 14(3):271-294, March 1994.

o Sally A. Goldman, Ronald L. Rivest, and Robert E. Schapire. Learning Binary Relations and Total Orders. SIAM Journal on Computing, 22(5):1006-1034, October 1993.

o Sally A. Goldman, Michael J. Kearns, and Robert E. Schapire. Exact Identification of Circuits Using Fixed Points of Amplification Functions. SIAM Journal on Computing, 22(4):705-726, August 1993.

o Sally A. Goldman. A Space Efficient Greedy Triangulation Algorithm. Information Processing Letters, 31(4):191-196, May 1989.


Doctoral Students (Past and Current)

Undergraduate/Masters Students (Past and Current)

Research Funding

    NSF Award IDM-0329241, "Applying Multiple-Instance Learning to Content-Based Image Retrieval," 2003-2206 with an REU supplement.

    Boeing-McDonnell Foundation Grant, "Using Unlabeled Data to Improve Supervised Learning Algorithms," 2000-2002.

    NSF Award CCR-9988314 "Learning from Multiple-Instance and Unlabeled Data," 2000-2003 with two REU supplements.

    NSF Award, "Applying Learning Theory to Networking Problems," 1998-2000.

    NSF National Young Investigator (NYI) Award, 1993-1998.
    Matching Funds from Xerox Corporation, Palo Alto Research Center and WUTA.
    Additional support provided by a Southwestern Bell Foundation grant.

    NSF Research Initiation Award, "The Role of the Environment in On-Line Learning," 1991-1993.

    GE Foundation Junior Faculty Grant, 1990-1991.

Brief Biography

I was born and raised in
St. Louis, Missouri, where I met my husband Ken. We both attended Brown University where we earned Sc.B. degrees from the Department of Computer Science. At M.I.T., we earned M.S. and Ph.D. degrees, both working in the theory group of the Laboratory in Computer Science .

We finished at M.I.T. in the summer of 1990 and returned home to join the Department of Computer Science at Washington University in St. Louis.

Would you like to take a tour of Washington University ?