Soundbyte: Spring | Summer 2001

Mining Spatial Data: The University of Minnesota Leads the Way

Image of professor Shekhar's research group
Front Row (left to right): Yan Huang, Wei-Hsin Fu, Shashi Shekhar, Wei-Li Wu;
Middle row: Xiaobin Ma, Hui Xiong, Chang-Tien Lu;
Back row: Ru-Lin (Alan) Liu, Pusheng (Alex) Zhang, Vatsavai Ranga Raju;
Not pictured: Caroline Peterson, Svetoslav Stoykov, Judy Djugash.

Spatial data mining software - code for pattern discovery processes based on geometric structures - is coming soon. When it arrives we will be able to efficiently identify spatial patterns in massive geo-spatial data sets for application domains including public safety (finding crime hot spots), public health (predicting the spread of disease), climatology (effects of El Niño), ecology (protecting endangered species), transportation (detecting local instabilities in traffic), location-based services in the M(mobile)-commerce industry, and national defense (inferring enemy tactics such as flank attacks).

The spatial data mining software results from the research work of Professor Shashi Shekhar and his students. Their research has demonstrated that key assumptions of classical data mining techniques are invalid for geospatial data sets. Though classical data mining and spatial data mining share goals, their domains have different characteristics. First, spatial data is embedded in a continuous space, whereas classical data sets are often discrete. Second, spatial patterns are often local whereas classical data mining techniques often focus on global patterns. Finally, one of the common assumptions in classical statistical analysis is that data samples are independently generated. When it comes to the analysis of spatial data, however, the assumption about the independence of samples is generally false because spatial data tends to be highly self-correlated. For example, people with similar characteristics, occupation and background tend to cluster together in the same neighborhoods. In spatial statistics this tendency is called spatial auto-correlation. Ignoring spatial auto-correlation when analyzing data with spatial characteristics may produce hypotheses or models that are inaccurate or inconsistent with the data set. Thus classical data mining algorithms often perform poorly when applied to spatial data sets. New methods are needed to analyze spatial data to detect spatial patterns.

Roots of spatial data mining lie in spatial statistics, spatial analysis, geographic information systems, machine learning, image analysis, and data mining. Several other departments at the University of Minnesota such as Biostatistics, Forest Resources, Electrical and Computer Engineering, Epidemiology, Geography and Psychology as well as research centers such as the Army High Performance Computing Research Center, the Center for Transportation Studies, the Institute for Mathematics and Its Applications (IMA), the Center for Urban and Regional Affairs, Precision Agriculture, and the Cancer Center are contributing to the field. In fact, the IMA is organizing a workshop on spatio-temporal patterns in the geosciences during the last week of September 2001, and a series of workshops related to the mathematics of geoscience in 2001-2002.

In addition to Shekhar, Computer Science and Engineering faculty members interested in spatial data mining include Professors Dan Boley, Ravi Janardan, George Karypis, Vipin Kumar, Nikos Papanikolopoulos and Paul Schrater. Prominent alumni in this field include Jack Dangermond (President, Environmental Systems Research Institute), Dr. Raju Namburu (Army Research Lab), and Dr. Siva Ravada (Manager, Spatial Data Group, Oracle Corporation).

The main contributions made by Shekhar and his students to spatial data mining include algorithms and data structures that can scale up to massive (terabytes to petabytes) data sets and formalization of new spatio-temporal patterns (e.g. co-locations) which were not explored by other research communities due to high computational complexity. Specific contributions include discovering spatial co-locations, detecting spatial outliers and location prediction.

Figure 1 - co-location discovery process

The co-location pattern discovery process finds frequently co-located subsets of spatial event types given a map of their locations (see Figure1). For example, analysis of habitats of animals and plants may identify co-location of predator-prey species, symbiotic species, and fire events with ignition sources. Readers may find it interesting to analyze the map in Figure 1 to find co-location patterns. There are two co-location patterns of size 2 in this map. Shekhar's group has provided one of the most natural formulations as well as the first algorithms for discovering co-location patterns from large spatial data sets and applying it to climatology data from NASA.

Image of using spatial outliers in traffic measurements

Spatial outliers are significantly different from their neighborhood even though they may not be significantly different from the entire population. For example, a brand new house in an old neighborhood of a growing metropolitan area is a spatial outlier. Figure 2 shows another use of spatial outliers in traffic measurements for sensors on I-35W (north bound) in the Twin Cities metro area for a 24 hour time period. Sensor 9 seems to be a spatial outlier and may be a bad sensor. Note that the figure also shows three clusters of sensor behaviors, morning rush hour, busy daytime, and evening rush hour. Spatial statistics tests for detecting spatial outliers do not scale up to massive data sets such as the Twin Cities traffic data set measured at thousands of locations in 30-second intervals and archived for years. Shekhar's group generalized spatial statistics tests to spatio-temporal data sets and developed scalable algorithms for detecting spatial outliers in massive traffic data sets. This work built on the traditional strength in designing scalable hierarchical routing algorithms and efficient storage methods for roadmaps.

Location prediction is concerned with discovering a model to infer locations of a Boolean spatial phenomenon from the maps of other spatial features. For example, ecologists build models to predict habitats for endangered species using maps of vegetation, water bodies, climate and other related species. Maps of nest location, vegetation and water were used to build a location prediction model for nests of red-winged blackbirds in wetlands on the shores of Lake Erie in Ohio. Classical data mining techniques yield weak prediction models as they do not capture the auto-correlation in spatial data sets. Shekhar's group provided a formal comparison of diverse techniques from spatial statistics (e.g. spatial auto-regression) as well as image classification (e.g. Markov random field based Bayesian classifiers) and developed scalable algorithms for those.

Courses on Scientific Databases (CSci 8705, Fall 2001), Data Mining (a CSci seminar), and Spatial Biostatistics (PubH 8436) are wonderful opportunities to learn more about these topics. Professor Shekhar's upcoming book on Spatial Databases (publisher Prentice Hall, 2002) as well as web sites ( and archiving recent research publications on the topic are additional resources.

-Shashi Shekhar & Bobbie Othmer

Greetings from the Department Head

B&W image of Pen-Chung Yew The academic year 2000-2001 has come to a very successful close for our department, although it was marked by a rather tumultuous and disappointing legislative session at the State Capitol for the University as a whole.

First of all, we want to thank all of our friends, supporters and alumni who launched a fierce campaign in the state legislature for the desperately needed funding and resources for the University and the department. When the chips were down, the University received half of the budget increase it requested and was forced to increase student tuition substantially for the next two years. Our department fared slightly better. Instead of the 17 new faculty positions originally requested, we received 13 new positions spread over four University campuses. I believe we will receive a lion's share of these new positions. We are obviously disappointed we did not receive all of the new positions we requested. However, judging from the difficult circumstances surrounding this year's budget, we have every reason to be pleased with what we received from this legislative session. With these new positions, we will be able to hire faculty members in strategic new areas and further strengthen some of our core areas in computer science and computer engineering during the next two years.

This year for the first time we became the largest undergraduate program in the Institute of Technology, surpassing Mechanical Engineering which has held the title for many years. This has happened despite the fact that the GPA requirement to enter the computer science major has been raised over the past few years and is now tied with Chemical Engineering and Materials Science as the highest in the Institute of Technology. This certainly marks an important milestone for the department. We are very proud that, despite the limited resources we have had over the years, we have managed to continue our growth and excel in both providing quality undergraduate education to our students, and building an impressive research infrastructure and graduate program along the way. We believe the new resources provided by the legislature this year will allow us to continue our phenomenal success for many years to come.

We have also completed another very successful recruiting season. Three new faculty members will be joining the department next academic year. They are Professors Gary W. Meyer in computer graphics, Eric Van Wyk in programming languages and software engineering, and Paul Schrater, who has a joint appointment with the Department of Psychology and who specializes in computer vision and motor control. This has been another very difficult and fiercely competitive recruiting season, with most schools chasing after a smaller pool of top faculty candidates. However, we came through with three very strong faculty recruits. We would like to thank our Faculty Recruiting Committee under the leadership of the Associate Head, Ravi Janardan, and many other faculty members, staff and students in our department. They spent an enormous amount of time and effort to make this a very successful recruiting season. Faculty recruiting is the most important task in our department because these new faculty members will shape the heart and soul of our department for many years to come. With the new positions from this year's budget, we have a tremendous opportunity and a lot of hard work ahead of us. I believe together we will meet that challenge and elevate our department to a higher level of excellence within the next few years.

Our Open House Organizing Committee has been working very hard for several months. The third Open House, celebrating the 32nd anniversary of the department, will be held on October 19, the first day of the University's Homecoming Week. We have an excellent program planned with keynote speakers, research exhibits, alumni reunion, workshops and panels. This year's Computer Science and Engineering Distinguished Alumnus Award will be presented to Professor Arvind of MIT. He is an internationally renowned scholar on high performance computer systems. I would like to extend our warmest invitation to all of our alumni, friends, industrial partners, and supporters, and ask you to join us on this wonderful occasion and to participate in many of these events. I particularly urge our alumni to join us this year as there will be some special events for you. For additional information on the open house, please visit our Web site:

-Pen-Chung Yew

Computer Science and Engineering's Open House
Friday, October 19, 2001
9 a.m.-6 p.m.
Please visit for additional information.

Four CS&E Faculty Members Awarded Promotions

Image of Mats Heimdahl, Shashi Shekhar, and Nikolaos Papanikolopoulos

Assistant Professor Mats Heimdahl (left) was promoted to Associate Professor, and Associate Professors Nikolaos Papanikolopoulos (right), Shashi Shekhar (center), and Anand Tripathi (not pictured) were promoted to Professor.

Mats. Heimdahl earned an M.S. in Computer Science and Engineering in 1988 from the Royal Institute of Technology in Stockholm, Sweden and a Ph.D. in Information and Computer Science in 1994 from the University of California at Irvine. His research interests are in software engineering, software requirements, formal specification languages, and automated analysis of software specifications. In particular, he is interested in software development for safety critical control systems. Professor Heimdahl is the recipient of an NSF Career award and is a McKnight Land-Grant Professor.

Nikolaos P. Papanikolopoulos received the Diploma degree in electrical and computer engineering from the National Technical University of Athens, Greece in 1987, the M.S.E.E. in electrical engineering in 1988, and the Ph.D. in electrical and computer engineering in 1992, both from Carnegie Mellon University, Pittsburgh, PA. His research interests include robotics, computer vision, sensors for transportation applications, and control. He was a McKnight Land-Grant Professor at the University of Minnesota for the period 1995-1997 and has received the NSF Research Initiation and Early Career Development Awards. He was also awarded the Faculty Creativity Award from the University of Minnesota.

Shashi Shekhar received the B. Tech degree in Computer Science from the Indian Institute of Technology, Kanpur, India in 1985, the M.S. degree in Business Administration and the Ph.D. degree in Computer Science from the University of California, Berkeley in 1989. He is currently an active member of the Army High Performance Computing Research Center as well as the Center for Transportation Studies at the University of Minnesota. His research interests include databases, geographic information systems (GIS) and intelligent transportation systems. Shekhar's general area of research is data and knowledge engineering. Currently his work is focused on storage, management and analysis of scientific and geographic data, information and knowledge.

Hung Quang Ngo Awarded the Guidant Fellowship

Image of Hung Quang Ngo

Hung Quang Ngo is the recipient of the first Guidant Fellowship awarded by the Computer Science and Engineering. The Guidant Foundation established a fund in the Institute of Technology to provide fellowships in the departments of Computer Science and Engineering, Electrical and Computer Engineering, and Mechanical Engineering for students of academic merit. The Guidant Corporation is a world leader in the design and development of cardiovascular and medical products.

Hung Ngo is pursuing his Ph.D. under the guidance of Professor Ding Zhu Du, who describes Ngo as one of the best students he has ever had. Mr. Ngo received his B.S. in Computer Engineering from Ho Chi Minh University of Technology in Vietnam, an M.S. in Computer and Information Sciences and an M.S. in Mathematics from the University of Minnesota. Mr. Ngo has been a teaching assistant and research assistant in the department and worked as a software design engineer intern at Microsoft one summer. His research interests are networking and combinatorics, distributed in both system and theory. He has 24 publications, including five book chapters and a book, eight journal papers and seven conference papers. He expects to complete his dissertation within the next year. More information about Mr. Ngo is available on his web site

-Georganne Tolaas

ACM Student Chapter Sponsors Wide Variety of Activities for Students

The University of Minnesota is lucky to have a very active student chapter of the ACM (Association for Computing Machinery). Activities support student success and professionalism and encourage interaction among students and faculty as well as provide a forum for students to meet each other.

Once each semester the ACM hosts a "Meet the Faculty Luncheon." A wonderful buffet of food is provided, and faculty and students eat lunch and discuss classes and research. The chapter provides free introductory Unix classes for students at the beginning of each semester. ACM has its own network which the students administer themselves, its own library with books donated by companies, and a study area, and it sell snacks to members for no profit. ACM has a computer lab, in which there are representative work stations from Sun, SGI, Intel, Apple, etc.

Lectures are sponsored this year. Northstar Financial Group sent a speaker to talk about investing strategies. Unisys sent a speaker who discussed new Intel/Windows enterprise technologies, and Intel sent a speaker who talked about microprocessor manufacturing.

At general meetings, which occur about twice a semester, topics of interest to the members are discussed ranging from events that are upcoming, financial and administrative issues of the Chapter, and what training events are available to students. Pizza is available. Social life is not ignored; two ice cream social/game nights are sponsored each year.

New officers for 2001-2002 are: John Hickey, President; Robert Myers, Vice President; Megan Carney, Membership Officer; Jacob Larson, Treasurer; and Jason Julkowski, Secretary. Membership in the ACM student Chapter is open to everyone: undergrads, grads, and even non-students. Please contact Megan Carney for membership information at .

-Bobbie Othmer

CS&E Staff Profile: Georganne Tolaas

What is the status of my application? How do I file my degree program? What if I don't get into the course I want? I want to join the graduate program but don't have a background in Computer Science so how can I do this? These questions and more are ones Georganne Tolaas attempts to answer for the prospective and current graduate students in Computer Science. Georganne has been with the department for five years. After graduating from the Uof M with an education degree, she started working with the U of M Parents Association. She has done a variety of things since then before joining the Computer Science department. She enjoys working with the students, staff, faculty and alumni and welcomes their questions and comments. She lives with her husband and two children on a small farm in rural Wisconsin.

CS&E '01 Graduates

CS&E '01 Ph.D. Graduates 7/1/00-6/30/01

Ph.D. Recipient Advisor Destination
Donghui Chen Ding-Zhu Du Sycamore Networks
Shituo Han Ding-Zhu Du Oracle Inc
Jonathan L. Herlocker Joseph Konstan Oregon State University
Xuan Liu Shashi Shekhar IBM T.J. Watson Research Center
Bing Lu Ding-Zhu Du Cadence Design Systems, Inc
Badrul Sarwar John Riedl Outride, Inc.
Sejun Song Zhi-Li Zhang & Ding-Zhu Du Cisco Systems
Difu Su Jaideep Srivastava Yahoo! Inc.
Quanzhan Zheng Ding-Zhu Du not available

CS&E '01 Masters Graduates 7/1/00-6/30/01

  • Vishal Agarwal
  • Eric L. Barsness
  • Paul E. Castillo
  • Yiyun Chen
  • Xiuzhen Cheng
  • Sai Venkata Chivukula
  • Calvin Yorn-Tien Chu
  • Anish Vinodkumar Desai
  • Vijay Mohan Deshmukh
  • Ameeta Desphande
  • Pranoop Kumar Erasani
  • Timothy E. Getsch
  • Madhuvan Gupta
  • Man Chung Hon
  • Naresh Jain
  • Steven L. Jensen
  • Moongu Jeon
  • Sirisha S Kaipa
  • Charu Khosla
  • Kondapally S. Kumar
  • Che Hung Richard Kuo
  • Rick Lowe
  • Anjun Lu
  • Arnold Getaro Mayaka
  • David R. McKoskey
  • Thai Quoc Nguyen
  • Kevin S.D. O'Bryan
  • Mark T. O'Connor
  • Ajay Pandey
  • Rohit Rakshe
  • Scott Rogers
  • Paul E. Rybski
  • Gayathri Seetharaman
  • Ajay Kumar Shukla
  • Joon W. Son
  • Pramod Srinivasan
  • Priyank Srivastava
  • Jiannong Sun
  • Imelda Sutedjo
  • Xinhong Tan
  • Hongguo Tian
  • Dayakar Kamesh Chander Tumsi
  • Hong Yi Wang
  • Xiaoan Wang
  • Yan Xiang
  • Fan Yang
  • Jinzhu Yu
  • Kebiao Yuan
  • Hongjing Zeng
  • Chunyu Zhang
  • Ying Zhe
  • Yan Zhen

MCIS '01 Masters Graduates 7/1/00-6/30/01

  • Vijay Bandi
  • Michael J. Brinker
  • Nishikant Kapoor
  • Nanda Krishore Molleti
  • Jing Sun
  • Hongbo Yang

MSSE '01 Graduates

  • Michael Barton, Digi International Inc.
  • Robert Befidi-Mengue, Jr, Ingenix, Inc.
  • Dan Bocko, Rosemount Inc.
  • Cathy Bryant, Artemis Alliance, Inc.
  • Richard Chapman, Digi International Inc.
  • George Coller, Object Partners, Inc.
  • Paul Elletson, GE Capital Fleet Services
  • Steven Flom, Honeywell International Inc.
  • Dave Frankson, Infinite Campus
  • Jennifer Grant, Object Partners Inc.
  • Trevor Gruby, St. Paul Companies Inc.
  • Kris Holt, Consultant
  • Brent Huhta, Graco Inc.
  • Gene Kath, Merrill Corporation
  • Craig Kendall, Ciprico Inc.
  • Shyem Khan, West Group
  • Michael McRoberts, Sapient Corporation
  • Aaron Mohrman, Retek, Inc.
  • Lisa Nebel, Parametric Technology Corporation
  • Karl Nilsson, Appian Bridge Corporation
  • Diego Ramallo, Medtronic Inc.
  • Gerald Schafer, Cyber Systems Engineering
  • Ronald Schloesser, Stratasys Inc.
  • Nathaniel Schutta, Artemis Alliance, Inc.
  • Steven Smeby, Weigh-Tronix Inc.
  • Zeeshan Tariq, Medtronic Inc.
  • Joshua Trutwin, United Defense
  • Tim Valentin, Siebel Systems, Inc.
  • James Walsh, Datacard Group
  • Gordon Weil, University of Minnesota
  • Jennifer Wolff, The Web Practice
  • Larry Zalesky, SIMS Deltec Inc.
  • Pam Zalesky, SIMS Deltec Inc.
  • Michael Zimmerman, United Defense

CS&E Alumni Profile: Ed Huai-hsin Chi

Alumnus Ed Chi of Xerox's Palo Alto Research Center (PARC) has been in the news lately (Time Magazine, The Economist, the Associated Press, and Information Week are some) because of interest in his work on Web usability. He and colleagues at PARC use the concept of information "foraging" to describe the behavior of Web users as they traverse Web links in searching for information, likening this behavior to that of an animal foraging for food in the wild. They also use a concept called "information scent" to give a measure of the cost and value of accessing a Web page. Using these ideas they hope to produce tools to help understand the relationships among user needs, user actions, and Web site design.

Ed was at the U of M in late February participating in an IMA (Institute for Mathematics and its Applications) Workshop on the Digital Library and Information Access, giving a talk about the "Scent of the Web," and visiting friends.

Ed is originally from Taiwan, the child of academic parents. He spent a year in Minnesota when he was in fifth grade and then came back four years later to go to South High, when his mother decided to complete a Ph.D. at the U. He overlapped his bachelor's degree work with high school, completing the requirements for a B.S. in C.S. in two years in '94. During this time, he worked at the Geometry Center on visualizing mathematical structures, and created one of the first visualizations of the Web in 1994. He continued on at the U for his M.S. in C.S., completed in December '96 in computational molecular biology with an emphasis in information visualization. He had thought of going to another school for a Ph.D., but decided to stay at the U, and working with Professor John Riedl as his thesis advisor. He completed his doctorate in March '99 in the areas of visualization, user interfaces, and graphics. For his thesis, Ed developed a spreadsheet for visualization in which each cell can contain a data set represented using interactive graphics. The spreadsheet analogy is continued with the availability of operations on individual cells and among cells.

In '97 Ed was fortunate to get an internship at Xerox PARC. His work had attracted some attention there and he had met Stuart Card at a conference, both of which gave Ed an edge in getting one of these highly competitive internships. He had another internship at PARC, and when he graduated in March of '99, he started work there. Ed finds Xerox PARC a wonderful environment for doing interdisciplinary work. Sometime in the future, he may consider an academic career since he enjoyed teaching, and both parents are academics. But for now, he is very happy to be working at PARC.

One might think that someone who completed his Ph.D. less than seven years after graduating from high school must work all the time. This is not true of Ed who has many interests, including Tae Kwon Do, photography, riding his motorcycle, making pottery, and writing poetry. For more information about Ed, including papers and links to press articles, see his Web site

-Bobbie Othmer

Many Thanks...

We would like to express our thanks to the following alumni and friends. Your support is invaluable in helping the department. We look forward to continuing this partnership in the future. Thank you for your support!


  • 3M Foundation Inc.
  • American Express Foundation
  • Lucent Technologies Foundation
  • Sun Microsystems Inc.
  • The Donaldson Foundation
  • The Medtronic Foundation
  • The N.C.R. Foundation
  • The New York Times Co. Foundation Inc.
  • The Prudential Foundation
  • Trilogy Employee Foundation
  • U.B.S. Corp.


  • Amdt, Rolland B & Marjorie L.
  • Bergum, Gerald E.
  • Blaskowski, Jeanne M.
  • Cabramson, David C.
  • Crowley, Thomas P.
  • Farrell, Richard S.
  • Ganino, Bernadette B.
  • Halverson, Richard P. Jr
  • Hanna, John J.
  • Holt, Jonathan A.
  • Indermauer, Kurt A. & Jennifer M. Timmers
  • Jelatis, George D.
  • Kottke, Michael J.
  • Leppik, David L.
  • McIntyre, Daniel K.
  • McKeever, Blaine W.
  • Mueller, Anthony M.
  • Niccum, Thomas M.
  • Rao, Karuna Ramdas
  • Salo, Timothy J.
  • Sames, Allen J.
  • Smith, Richard E.
  • Smith, Warren R.
  • Strait, John P.
  • Wu, Rita Y.

Twin-SPIN Meets at the University

The first Thursday of every month a dedicated group of software engineering professionals meet at the University of Minnesota to share their experiences and further their knowledge in how to improve the software development processes in their respective companies. It is a meeting of the Twin Cities software process improvement network (Twin-SPIN).

Twin-SPIN is a regional organization established in January of 1996 as a forum for the free and open exchange of software process improvement, experiences and ideas. Representatives from industry, government, academia, other professional organizations, and consultants are welcome to participate. The Twin-SPIN mission is to help sustain commitment and enhance skills in the area of software process improvement through an active program of networking and mutual support. The organization strives to serve as a source of educational and experiential information for its members, other SPIN organizations, and the general community of software professionals.

Since 1999, the Department of Computer Science and Engineering has successfully hosted Twin-SPIN meetings. Average meeting participation has doubled since then, and it is our hope that it will continue to grow in the future. Topics presented and discussed last year included "eXtreme Programming" (Pascal Roy), "The Evolution of a Software Engineering Process Group" (Bobbi Stark and Kris VanHofwegen), "Getting Out of Our Own Way" (Ed Tilford), and many others. Information on recent talks can be found in the Twin-SPIN archive hosted by the Critical Systems Research Group at the U:

Participation in Twin-SPIN is free-of- charge and new participants are always welcome. Twin-SPIN meets the first Thursday of the month, August through June. Meeting announcements are posted on the Twin-SPIN home page (, and more information can be obtained from the Facilitator/Moderator Jesse Freese ( ) or Mats Heimdahl ( ). If your organization is interested in sponsoring the Twin-SPIN meetings (to help cover coffee, cookies, and parking expenses), your donation will be gratefully accepted (

We hope to see you at a Twin-SPIN meeting this fall.

-Mats Heimdahl

Graduate Student Profile: Dan Cosley

Image of Dan Cosley

Dan Cosley, a graduate student in the Ph.D. program in computer science, arrived at the University of Minnesota last fall with a varied academic and work background. He started his post-secondary education studying music and preparing to be a music teacher. Student teaching , particularly the seventh-graders, convinced him that music education was not a good career choice for him at the time, although he has considered going back to it later in life. After a few years of working at a bank, a programming job sparked enough interest to send him back to school at James Madison University in Virginia to get a master's degree in computer science. Dan also taught computer science courses at JMU for two and a half years, a task he enjoyed so much that he decided to get a Ph.D. in computer science so he could become a real professor.

Dan's masters thesis involved collaborative filtering and computer supported collaborative work to develop a system that allows a community of users to jointly compile a collection of Internet resources. GroupLens, led by Professors John Riedl and Joseph Konstan, is the top research lab in the country for collaborative filtering, so where else would Dan go for graduate school? He has had a one quarter time research assistantship in the GroupLens project plus a Graduate School fellowship. Dan has had a paper accepted in the ECSCW Conference (European Computer Supported Cooperative Work.) Written with Mark O'Conner who started the work and graduated with an M.S. in 2000, the paper, PolyLens: A Recommender System for Groups of Users, is about making recommendations for groups of people instead of individuals using capabilities already in MovieLens, a recommender system for movies. (See

Dan moved to Minnesota with his wife, Sue, and their two cats Proton and Electron. So far he is enjoying living in Minnesota, although this summer he is working as an intern for NEC Research in New Jersey. Sue works in the human resources department at Health Partners and is working on a masters degree specializing in career counseling at St. Mary's College. Proton and Electron are satisfied with their current careers as cats. For more about Dan, see ~cosley/.

-Bobbie Othmer

Information Technology Research Grants Awarded by the National Science Foundation

Anand Tripathi

"Dynamic & Secure Distributed Collaborations"

The primary objective of this ITR funded three-year project is to develop techniques for building secure environments for dynamic distributed collaborations. The need to support dynamic collaborations arises in many situations where a group of people, organizations, and resources are dynamically networked to perform tasks towards some common goal or mission. The approach taken in this project is to build a collaboration environment from a high-level description of the collaborative tasks, security policies, and coordination protocols for the mission. This effort would develop a middleware infrastructure to support construction of dynamic collaboration environments based on their descriptions in XML and Java. The use of mobile objects and agents in supporting many of the services of this infrastructure is being investigated in this research using the Ajanta mobile agent system. The proposed infrastructure would support resource discovery based on roles and functionalities of the entities. The resource discovery facility would be designed as a two-level service. The approach is to use application level classification schemes together with XML based query protocols at the higher level. This level would map resource discovery queries to Java interface names. The lower level would be based on Jini to search for services supporting Java interfaces. Access to shared resources and entities would be based on the security policies defined by the resource owner and the privileges granted to a participant would be based on his/her role. Mechanisms would be developed to add, delete, and manage shared resources, and to define security policies. This middleware would provide a service for event monitoring and handling, which is required in a dynamic environment to deal with configuration changes. Protocols for caching and replication of shared objects would be developed for scalability of the infrastructure. These protocols would take into consideration role-based security policies as well as workflow requirements.

Yousef Saad

"New Algorithms for Scalable Modeling in Materials Science"

Yousef Saad, Jim Chelikowsky (Chemical Engineering and Materials Science), and Andreas Stathopoulos (Computer Science, College of William and Mary) are collaborating on this award. Their project is an illustration of what can be achieved by joining forces with researchers from other disciplines. The problems addressed are among the most challenging in computational sciences. In fact, chemists and chemical engineers have always been the biggest users of the large high-performance computers located at the Minnesota Supercomputer Institute.

One of the most significant achievements of the last century has been the development of accurate methods to predict the electronic and structural properties of condensed matter. These methods, based on density functional theory and pseudopotentials, allow exploration of the properties of matter without resorting to experimental input. They allow prediction of new materials and properties based on numerical calculations. For example, it has become possible in the last few decades to predict candidate materials for superhard matter and for superconducting semiconductors. The only inherent limitations of these methods are computational constraints: current electronic structure methods are severely hampered by the high cost of their algorithms. The main goal of the project is to introduce new methodologies, based on efficient algorithms, for stepping beyond current limitations. This type of work cannot be realized by material scientists nor by computer scientists alone.

Zhi-Li Zhang

"Collaborative Research: Scalable Quality-of-Service Control for the Next Generation Internet."

Today's Internet owes its great success to the simple, "hour-glass'" IP network protocol architecture laid out twenty-five years ago. With rapid advances in networking technologies and explosive growth of rich multimedia content in recent years, the networking community finds itself at an important crossroads: what should be the next generation Internet architecture for controlling network resources and providing the quality of service (QoS) needed by emerging multimedia applications? There is a multidimensional spectrum of possible approaches to providing QoS guarantees. The choice of a QoS solution for the next generation Internet will have a substantial impact on both the evolution of the Internet itself, and on what it enables. Making the "right'" choices requires the development of a fundamental understanding of the scalability of QoS controls and the impact of these controls on the efficacy of QoS provisioning.

The goal of this research is to develop a comprehensive, quantitative understanding of the fundamental trade-offs involved in various approaches toward providing scalable QoS guarantees. To this end, coherent theories to systematically address the issue of scalability in QoS controls will be developed. These theories include: 1) an aggregate network calculus to study the impact of aggregate QoS control mechanisms on the performance and complexity of network data plane operations; 2) QoS control laws for capturing the slow time-scale, system-wide behavior of a network; and 3) aggregation rules that address the performance and complexity of network control plane operations under aggregate QoS controls. As an integral part in developing these theories, effective and scalable QoS mechanisms, and tools and techniques for quantifying and evaluating the trade-offs of various QoS solutions will be designed. Based on the results from these efforts, how various QoS solutions can be combined to construct meaningful end-to-end services will be studied. This research will blend formal modeling/analysis, experimentation/ implementation, and evaluation. The understanding and insights gained as a result of this research will lead to the establishment of the theory, design principles, and guidelines for building scalable QoS controls for the future Internet. This, in turn, will allow reasoned and informed choices to be made as the next generation Internet takes shape.

CS&E News Briefs

Three New Faculty Join Department

Gary W. Meyer will join the department Fall 2001 as an associate professor. Professor Meyer received his Ph.D. in computer graphics from Cornell University. His research focuses on color synthesis and color reproduction techniques for computer graphics. He takes advantage of what is known about the human color vision system to improve the efficiency and realism of synthetic image generation techniques and to increase the accuracy and quality of the color reproduction accomplished by computer graphic devices.

Eric Van Wyk, who is currently a postdoctoral research officer at Oxford, will join the department Spring semester 2002 as an assistant professor. Professor Van Wyk received his Ph.D. in Computer Science from the University of Iowa. His research is in the area of programming languages, in particular, on designing concise, high-level, formal and practical ways to specify languages and language processing tasks such as translation and optimization.

Paul Schrater, who will have a joint appointment with the Department of Psychology, will join the department Fall 2001 as an assistant professor. Professor Schrater received his Ph.D. in neuroscience from the University of Pennsylvania. His research interests include human and computer vision, planning and guiding reaches with and without visual information, and the integration of visual, haptic, and motor information during the perception-action cycle. His research approach treats problems in vision and motor control as problems of statistical inference, which has lead to a concurrent interest in statistical methods that includes Bayesian (Belief) Networks, Dynamic Markov Decision Networks, Pattern Theory, Machine Learning, and other topics in statistics and pattern recognition.

Sturtivant Selected as Top Professor

Carl Sturtivant was selected as the top professor from the CS&E department by the students in IT. He was presented with an award at the IT awards banquet on Wednesday, April 11.

Konstan Elected to University Senate

Professor Joseph Konstan was elected to a three-year term in the University Senate.

Gini Chairs Conferences

Professor Maria Gini is the General Co-Chair, with Toru Ishida from Kyoto University, of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS '02). The conference will be held July 15-19, 2002 in Bologna, Italy. The conference will bring together in a single conference three conferences that were previously held as separate conferences (Autonomous Agents, ICMAS, and ATAL).

Gini is also the General Chair for the 7th International Conference on Intelligent Autonomous Systems, a conference devoted to autonomous robotics. The conference will be held March 25-27, 2002 in Marina del Rey, California.

Gini Recognized as Distinguished Women Scholar

Professor Maria Gini received one of the first Distinguished Women Scholar Awards from the University. The awards are sponsored by the Graduate School and the Office for Multicultural Affairs. Two awards are given each year, one in the humanities, social sciences, and the arts, and one in the sciences and engineering. The awardees were honored at a reception at the Weisman Art Museum on April 11.

2000 Lando Scholarship Recipients

The recipients of this year's Lando scholarships are Ning Jia, Vasile Bud, Mark Dufresne, Kristine Paul, Steven Linaberry, Dayou Zhou, Chi Lai, and Paul Larson.

Thompson Awarded Doctoral Dissertation Fellowship

Jeffrey Thompson, an advisee of Professor Mats Heimdahl, has been awarded a Doctoral Dissertation Fellowship by the Graduate School. The Fellowship is intended to enable Ph.D. candidates of particular promise to devote full-time effort to the research and writing of the dissertation during 2001-02.

Ning Helen Jia Wins Award

Ning Helen Jia was awarded the Asian/Medtronic Achievement Award on her 21st birthday.

Minnesota Places First in Microsoft Competition

Two of our undergraduate students, Michael Wyman and Julian Selman, won first prize, $25,000, in Microsoft's first Pocket PC Programming Competition. More than 100 students nationwide participated. The award was presented July 23 at Microsoft's Redmond campus at a ceremony attended by over 300 faculty from around the world. Wyman and Selman won with a game called Slither, patterned after a Nibbles game. The goal is to make a worm grab as many apples as possible as it is moved through a map, before it is eaten by an enemy snake.

Alumni News

Graduate Student Awarded Highly Regarded DOE Fellowship

Ahna Girshick has been awarded a Computational Science Graduate Fellowship from the Department of Energy. The Computational Science Graduate Fellowship is a highly competitive program that provides fellows with benefits including a monthly stipend of $1,800 and payment of all tuition and fees. In return, fellows must complete coursework in a scientific or engineering discipline, computer science, and applied mathematics. Fellows in this program also complete a three-month practicum at a Department of Energy laboratory. Ms. Girshick will be pursuing her graduate degree at the University of Claifornia-Berkeley in the area of computational vision science.

Please send your Alumni News to: .

Cray Distinguished Lecture Series 2001-2002

Jerry DeJong, Univerisity of Illinois
Herbert Edelsbrunner, Duke University
Jim Foley, Georgia Tech
Dennis Gannon, Indiana University
Thomas Henzinger, UC Berkeley

Dates and locations to be announced
For additional information, please visit our Web site at: