Soundbyte: Spring 1999

A LETTER FROM THE DEPARTMENT HEAD

Image of Dr.Yousef Saad
Dr.Yousef Saad

I will begin this note by congratulating two of our best faculty members. Nikos Papanikolopoulos received the department "creative faculty award". This was an award established last year by Dean H. Ted Davis to promote creativity in research and teaching in the Department of Computer Science and Engineering. Nikos and his research were featured in our previous issue of Soundbyte. Mats Per Erik Heimdahl received the McKnight Land Grant professorship one of the most prestigious awards given by the University. As a matter of fact, the department has received only two such awards since its inception in 1971. The previous one, as you may have guessed, went to Nikos Papanikolopoulos (in 1995). Congratulations to Nikos and Mats, not only for these excellent awards, but also for being outstanding researchers as well as ideal citizens of the department!

I would like next to update our readers about the situation with our enrollments. As I entered my office, February 26th, 1999, Liz Freppert, my secretary, greeted me with this remark: "Anand Tripathi's class (internet programming) has filled up to 110 and has a waiting list of 40 - and this is only the second day of registration!" More recently the waiting list for this same class passed the 100 mark -- the first time ever that this has happened. The situation is similar with many of our classes. What is surprising in addition to the lengths of the waiting lists is that this is happening so early in the registration period. Another important problem -- which differentiates us from other departments -- is that our classes tend to be large at all levels across the board. Some of our graduate (8xxx) classes have enrollments of 80 or 100 students.

Enrollments have had a healthy growth in the last few years but the continuation and vigor of this trend is alarming because the department, whose size of 25 faculty members is relatively modest, cannot absorb a growth of this nature. Large classes can have a damaging impact and can erode the gains made by the department in recent years. They affect morale of faculty and reduce our competitiveness in recruiting. They lead to lower quality education, and result in lower quality research because the time that is left available for research for faculty and teaching assistants decreases. For all these reasons, the department as a whole has moved aggressively with a number of initiatives to prevent class enrollments from growing out of control. We have raised the GPA requirement to enter our program from 2.5 to 2.7. This is one of the highest GPA requirements in the college. This will start to have an effect two years after it is instituted. Many of the students in our classes are not computer science majors, so we have also decided to restrict admission to some classes for non-majors. The goal is to keep the size of the upper division classes under 60 students.

On a different front I am happy to report that we are making excellent progress in recruiting. This year started out on a pessimistic note. The communications of the ACM had 180 postings in their November 1998 issue (versus 140 for November 1997) and 255 postings in December 1998 (versus 180 for December 1997). Most of these were multiple postings. It seemed that all of a sudden all colleges took notice of the shortage of workers in Information Technology. Students too became aware of it, and this increased the demand for teachers.

Read on for additional updates, research profiles, and for information on upcoming events and activities. I take this opportunity to remind everyone in particular about our next open house, which will take place on October 27th, 1999.

COMPUTER SCIENCE & ENGINEERING OPEN HOUSE

Wednesday October 27, 1999

Tentative Schedule

1:30 p.m.Coffee/Registration
2:00 p.m.Exhibits
2:30 p.m.Colloquia
4:30 p.m.Tour
5:00 p.m.Reception
5:30 p.m.Presentation of the Distinguished Alumnus Award
6:00 p.m.Dinner/Keynote Speaker: Ted Johnson, Executive Vice President and Chief Technology Officer, Visio Corporation

Registration forms with more detailed information will be mailed in September. Please mark your calendars.

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!

Companies

  • IBM Corporation
  • Intel Corporation
  • Lockheed Martin Corporation
  • National Instruments
  • NCR RDN
  • P.P.G. Industries Fdn.
  • Vallon Inc.

Individuals

  • Jeffrey S. Ahlquist
  • Rolland B. & Margorie Arnt
  • Janifer Y. Au
  • Thomas K. Austin
  • Daniel A. Ball
  • Shirley J.S. Bergum
  • David P. Beyer
  • Todd A. Biegut
  • Jeanne M. Blaskowski
  • Christopher T. Bovitz
  • Bruce W. Clark
  • Brian D. Colvin
  • Benjamin G. Cooper
  • Tim P. Davey
  • Janet M. Drake
  • David P. Gendron
  • Pierre Gendrow
  • Daniel M. Golliet
  • Michael A. Haapala
  • Bennett Hackner
  • Paticia E. Hansen
  • Michael T. Hanson
  • Richard J. Hedger
  • John M. Heinen
  • Russell C. Heinselman
  • David W. Herder
  • George F. Heyne
  • David L. Hintz
  • Dr. J. Andrew Holey
  • Mei-Chu Hsu
  • Robert H. Hu
  • Allen T. Huwiller
  • Kimberly A. & Jeffrey P. Johnson
  • Kelly E. Kimball
  • Kenneth P. Kloncz
  • Marlys A. Kohnke
  • Jeffrey C. Lane
  • James G. Langenberger
  • J.P. Little
  • Jessica K. Lowe
  • Blaine W. McKeever
  • Mitchelle Morehouse
  • Roger P. Nelson
  • Richard A. Olson
  • Dr. Michael A. Palis
  • Joseph L. Pearson
  • Michael P. Quist
  • David E. Rasmussen
  • Kathleen D. Rauchle
  • Paul G. Richmond
  • Frederick W. Roos
  • Karen L. Ryan
  • Allen J. Sames
  • John D. Samow
  • Greg E. Saunders
  • Kurt A. Schneewind
  • Raymond L. Slisz
  • Bradley Stamas
  • Douglas E. Stewart
  • John P. Strait
  • Edward L. Stuart
  • Dr. Yuen Tak-Sun
  • Eric J. Svedberg
  • Leo I. Thome
  • Nancy C. Thurlow
  • Thomas S. Tyler
  • Steve E. Van Allen
  • Robert D. & Elizabeth R. Vavra
  • Lance A. Visser
  • Douglas J. Weber
  • Bruce T. Welch
  • Roy E. Wood
  • Rita Y. Wu
  • Ben L. Yip

SOFTWARE SYSTEMS FACULTY PROFILES

Dr. John V. Carlis

Image of Dr. John V. Carlis
Dr. John V. Carlis

(612) 625-5582
http://www.cs.umn.edu/~carlis

My main research interest is database management systems (DBMS). I am working with biologists and other computer scientists on genome, brain, chimpanzee and soils databases. Data models are the focus of much of my work. A secondary area of interest is computer music.

See Dr. John V Carlis' web page for further information on his research and publications.

Dr. Vipin Kumar

Image of Dr. Vipin Kumar
Dr. Vipin Kumar

(612) 624-8023
http://www.cs.umn.edu/~kumar

My current research interests include data mining, parallel algorithms for scientific computing as well as data intensive applications, and algorithms design models for systems with deep memory hierarchies.

See Dr. Vipin Kumar's web page for further information on his research and publications.

Dr. Shashi Shekhar

Image of Dr. Shashi Shekhar
Dr. Shashi Shekhar

(612) 625-8307
http://www.cs.umn.edu/~shekhar

My general area of research is data and knowledge engineering, with a focus on storage, management and analysis of scientific and geographic data, information and knowledge. My work in geographic information systems includes databases for managing spatial networks, parallelization of GIS, routing algorithms for Advanced Traveler Information Systems, and archival of traffic measurements.

See Dr. Shashi Shekhar's web page for further information on his research and publications.

Dr. James Slagle

Image of Dr. James Slagle
Dr. James Slagle

(612) 625-0329
http://www.cs.umn.edu/faculty/slagle.html

I have worked on researching, designing, and implementing the DATATOOL Data Retrieval and Analysis Tool project. My research also includes work on a Natural Language understanding system, a neural network architecture for control of robot manipulator arms, the Decentralized Decision-Making System, and automated temporal logic. In other research, I am working with a group including doctors in the Bio-Medical Engineering Institute and in the Medical School in designing a home monitoring expert system to aid in the follow-up of lung transplant patients.

See Dr. James Slagle's web page for further information on his research and publications.

Dr. Jaideep Srivastava

Image of Dr. Jaideep Srivastava
Dr. Jaideep Srivastava

(612) 625-4012
http://www.cs.umn.edu/faculty/srivasta.html

My research approach has been to use (a) the special nature of multimedia information, (b) the nature of infrastructure hardware and software, and (c) the perceptual requirements of end users, to develop a number of mechanisms that can be used in next generation operating systems, networks, and databases for multimedia.

See Dr. Jaideep Srivastava's web page for further information on his research and publications.

DATA: A KEY FOUNDATION OF THE DIGITAL AGE

Over half a century of experience with the use of computers has shown that information is key to the functioning of any organization. Furthermore, experience with using information leads to the desire to obtain more of it, invariably leading to a complete metamorphosis of the process using it, as the understanding of the information increases. Information is generated when an interpretation is applied, in the context of a process, to a piece of data, and hence data is our best approximation of reality. This key role of data in modeling reality from a computational perspective has led to the phenomenal success of databases in practically all applications. As the role of data continues to increase in the digital age, there is an increasing need to develop new computational techniques for the storage, management, and analysis of data.

The Department of Computer Science and Engineering has a significant ongoing activity in the areas of databases and data mining, including activities in five laboratories. Faculty members, Professors John Carlis, Vipin Kumar, James Slagle, Shashi Shekhar, and Jaideep Srivastava, each expert in his respective field, direct on-going projects with both graduate and undergraduate students.

John Carlis

Professor John Carlis' main research interest is database management systems (DBMS). Within DBMS he is interested in data modeling, language extensions, and nontraditional applications. Data models are the focus of much of his work. He has built data models for a number of real, complex systems, thereby tempering theory with practice. His current interests include improving the user-DBMS interface, specifically in providing more powerful, natural commands that allow users to confidently and concisely express queries that otherwise may go unasked. The need to integrate separately developed business applications drove the development of DBMS's. Now other application areas (e.g., scientific computation, expert systems, CAD, and software design) are being similarly driven, and DBMS capability must be extended. Professor Carlis is interested in creating data models for such applications, assessing the match between DBMS capabilities and user requirements, and then improving the DBMS. Scientific applications provide fertile ground for database research, and Professor Carlis has three interdisciplinary database projects in progress. He is working with biologists and other computer scientists on plant genome, neuro-scientific, and chimpanzee databases.

Vipin Kumar

In addition to his long-standing interest in high-performance computing, Professor Vipin Kumar has an active interest in data mining. In this area, his research group is developing novel methods for mining information in high dimensionality data that pose major challenges for conventional data mining algorithms. Recent developments include a novel methodology for finding clusters in large high-dimensional data sets. In this scheme, relations among data items are captured using a graph or a hyper-graph, and efficient multi-level graph-based algorithms are used to find clusters of highly related items.

This methodology has been applied successfully to a variety of domains such as stock market data, and DNA data, documents on the Web. These experiments demonstrate that the graph-based approach is applicable and effective in a wide range of domains, and outperforms conventional clustering techniques such as K-Means even when they are used in conjunction with dimensionality reduction methods such as Principal Component Analysis. Graph-based methodology is also being used in nearest neighbor classification scheme in which the importance of discriminating variables is learned using mutual information and weight adjustment techniques. Empirical evaluations on many sets of real world documents demonstrate that this scheme outperforms state of the art classification algorithms such as C4.5, Ripper, Naive-Bayesian, and PEBLS. This research is being done in collaboration with a number of companies such as GTE, Fingerhut, and West Publishing.

James Slagle

Professor Slagle heads the Datatool project, whose overall goal is to apply computer science techniques to traffic engineering. Sponsored by the Minnesota Department of Transportation, the Datatool system provides a graphical user interface to a database management system. This is integrated with data analysis and display facilities. Current work is directed towards applying advanced computer science techniques to error detection and correction in data obtained from highway sensors.

Shashi Shekhar

Professor Shekhar's main research interest is in geographic information systems (GIS), which includes databases for managing spatial networks (e.g. road-maps), parallelization of GIS, routing algorithms for Advanced Traveler Information Systems, and archival of traffic measurements. His research group has developed some of the most efficient indexing methods for large roadmaps and algorithms for path evaluation as well as for computing shortest paths. Connectivity-Clustered Access Method (CCAM), a new storage and access method for spatial networks, has been developed and outperforms alternative schemes in carrying out network computations. In knowledge engineering, work has been done on the problem of discovery in database. Symbolic data mining techniques as well as neural networks have been studied. One of the fastest scalable parallel formulation of back-propagation learning algorithms for neural networks computes over one Giga connections per second. Re-search sponsors include the National Science Foundation, National Aero-nautics and Space Administration, Army Research Laboratories, Control Data Inc., U.S. Department of Trans-portation, Minnesota Department of Transportation, and the ITS Institute.

Jaideep Srivastava

Professor Srivastava's research interests are in databases, data mining, and multi-media computing. One of his current projects investigates the application of data mining techniques to Web data. Sponsored by the National Science Foundation, this project investigates how information about content, structure, and usage of the Web can be mined for knowledge useful to various applications. A critical issue is the modeling of human interaction with the Web. Page hits are at too fine a granularity to provide useful information; and user behavior must be analyzed at a coarser granularity. The approach is to group Web page hits into user transactions, based on clustering, which serve as the units of human interaction with the Web. Ongoing work is using Markov models to approximate the process a user is going through in browsing the Web. Another interesting issue is to mine for interesting usage patterns in Web logs. Hyperlinks in Web pages capture the author's view of pieces of information linked together, while browsing patterns capture the users' view of it. A usage pattern is interesting if there is significant disagreement between the two views. The framework of logic with supports is being used to model the beliefs in this environment, and information about content, structure, and usage of Web pages is used to estimate the degrees of these beliefs.

For additional information on these faculty members, please visit the Software Systems Faculty Profiles page.

THE CISCO LAB OPENS...

Image of Irene Jacobson showing the equiment in the CCIE lab
Systems staff member Irene Jacobson
shows the equiment in the CCIE lab to some
of the guests attending the Open House.

The Departments of Computer Science and Engineering and Networking and Telecommunications Services at the University of Minnesota, in conjunction with Cisco Systems, Inc. have opened a Cisco Certified Internetwork Expert (CCIE) Practice Laboratory.

The CCIE Practice Laboratory is ideal for networking professionals wanting to practice for the CCIE lab exam. They will have a chance to configure Cisco routers and other networking equipment in an environment similar to what they will see when they take the real CCIE lab exam.

The laboratory is equipped with two PCs, several types of Cisco routers and switches, as well as ISDN lines, a Frame Relay switch, V.35 patch panels, 10-Megabit hubs and token ring MAU's. A CCIE Practice Multiprotocol Skills practice exam, developed by Cisco Systems, is used to make the practice session as close as possible to the actual CCIE lab exam.

On May 5th Cisco sponsored an Open House for the CCIE Practice Lab and approximately 50 representatives from some of Minnesota's largest companies attended. The Open House included presentations from Computer Science and Engineering Department Head, Yousef Saad, Networking and Telecommunications Department Director Carolyn Parnell, and CCIE program team leader Jeff Buddemeier. Refreshments in the CCIE Practice Lab followed the presentations. This lab is beneficial for both Cisco and the CS&E department. The department gets to use state-of-the-art equipment in its research, local industry has a top-notch facility at which their employees can train, and Cisco provides a service to their customers who want to have CCIE certification. The cost of the lab is $500 per day; Cisco recommends at least two days in the practice lab before attempting the actual CCIE lab exam

For further information, please contact either Irene Jacobson at 612-625-8526, , or Jim MacDonald at 612- 625-5803, .

CS&E NEWS BRIEFS

Faculty Receive Awards

Image of Dr. Joseph Konstan
Dr. Joseph Konstan

Joseph Konstan received the George Taylor Career Development Award. This award recognizes exceptional contributions to teaching by a candidate being considered for tenure at the rank of associate professor and carries with it a $5,000 award to be used for professional development in teaching and research.

Image of Dr. Mats Heimdahl
Dr. Mats Heimdahl

Mats Per Erik Heimdahl was named a 1999 McKnight Land-Grant professor. This award provides the recipient with a research grant of $24,000 the first year and either an additional $24,000 grant or a 50% paid leave the second year. In addition, two months of summer salary are provided.

Nikolaos Papanikolopoulos was the first recipient of the department's Creative Faculty Award, receiving $2500 in discretionary funding. The award was created last year by Dean H. Ted Davis. The department is looking for industrial sponsorship for the award in future. years. If you are interested in providing sponsorship, please contact Jaideep Srivastava at 612-625-4012.

Wei-Chung Hsu Joins the Department

Dr. Wei-Chung Hsu will join the department in January 2000 as an associate professor in the Digital Technology Center. Dr. Hsu received his B.S. in Computer Science and his M.S. in Computer Engineering from the National Chiao-Tung University in Taiwan and his Ph.D. in Computer Science from the University of Wisconsin at Madison. He comes to the department with experience as a computer architect at Cray Research Inc. at Chippewa Falls, Wisconsin, and a run-time optimization architect and senior technical contributor to the Enterprise Servers Group at the Hewlett Packard Company of Cupertino, California. His interests include processor and system architectures, processor and system performance, compiler optimizations, and run-time optimization systems.

George Karypis Accepts Digital Technology Position

Dr. George Karypis was offered a position as part of the technology initiative. Dr. Karypis is already a member of the department paid from grantfunds. His new appointment is a re-newable 3-year contract which is tied specifically to research in genomics." Dr. Karypis earned a Ph.D. in Com-puter Science from the University of Minnesota in 1996. His research has been focussed on algorithms for scientific computing and is currently ex-panding to related topics such as data mining, and genomics. His Ph.D. work on graph partitioning has had a major impact in several areas, but most notably in high-performance computing.

One of Dr. Karypis's biggest accomplishments has been to develop an efficient graph partitioning algorithm - called MeTis - and to distribute it freely on the Web. There are probably tens of thousands of users of MeTis in applications that include CAD, high-performance computing, databases, and genomics. Dr. Karypis is also known worldwide for the book on parallel algorithms which he co-authored with Kumar, Grama, and Gupta. This is currently the best book on the market on parallel algorithms. Widely used to teach this topic of increasing importance on campuses around the world, it has become a de-facto reference.

Dr. Karypis has been recruited in part because of his recent strong interest in applying computer science concepts and techniques to the field of genomics. This extremely important new research direction, in which many other universities are also seeking a presence, fits in perfectly with the mission of the Digital Technology Center.

Jon B. Weissman Arrives Fall Semester 1999

Professor Jon B. Weissman will join the faculty Fall Semester 1999 as an assistant professor. Professor Weiss-man received his B.S. in applied mathematics from Carnegie-Mellon and his M.S. and Ph.D. in computer science from the University of Virginia. He has been an assistant professor at the University of Texas at San Antonio since 1995. His research interests include distributed systems, metacomputing, scheduling and resource management, I/O, software fault tolerance, parallel processing, scientific applications and operating systems. Professor Weissman holds a National Science Foundation CAREER award which supports his scheduling research.

Student Projects Needed for Computer Science Course 5115

Professor Joseph A. Konstan invites companies, non-profit organization, community groups, and others to propose projects for students enrolled in Computer Science 5115: User Interface Design, Evaluation, and Implementation. This course is a redesign of CSci 5110, with a new focus on getting students out to meet real users and solve real problems.

Students work on projects in groups of three to five, usually including on non-major from a design, psychology, or engineering discipline. These groups will interview and observe users, perform task analysis, and design and evaluate two to three interface prototypes. These prototypes will be evaluated using usability engineering processes including user tests.

To be considered for the course, a project must provide access to the current or eventual users of the system. The project must also focus on interface issues, rather than data processing or other back-end computation. Good projects include, but are not limited to, web sites and applications with interactive content, new graphical interfaces to existing text-based applications, and applications for computerizing paper processes. Students will select 15-20 of the proposed projects in the first weeks of September 1999, and will complete and present their designs in December.

If you have an idea of a project that would benefit your company or organization, please contact Jake Vo at to request a project proposal kit or call Professor Konstan at 612-625-1831.

Recently Received Grants

  • "High Performance Algorithms for Electronic Materials," to Yousef Saad and James Chelikowsky (Chemical Engineering and Materials Science), from National Science Foundation, $234,000, 02/15/99-01/31/2000.
  • "An Investigation of New Approaches to Critical-Systems Survivability," to Mats Heimdahl, from M.I.T./DARPA, $97,070, 01/01/99-12/07/99.
  • "Mechanisms for Secure and Robust Agent-Based Distributed Computing - REU Supplement," to Anand Tripathi, from the National Science Foundation, $5,000, 06/15/99-09/30/00.
  • "Application Design and Workflow Synthesis from Business Process Models," to Mats Heimdahl, from Camelot IS-2 International, Inc., $5,754, 03/01/99-05/31/99.
  • "Scheduling Algorithms and Applications Development," to Vipin Kumar and George Karypis, from NASA, $80,000, 04/01/99-10/31/99.
  • "Electronic Commerce," to David H.C. Du, from Talent Information Management LLC, $25,967, 02/15/99-07/15/99.

MSSE PROGRAM GRADUATES ITS FIRST CLASS

In the Fall of 1997, the Department of Computer Science and Engineering launched its Master of Science of Software Engineering (MSSE) program. We started the program as a response to industry's demand for highly skilled software engineers. To assure a high-quality learning experience, the program has a limited enrollment (no more than 35 students) and provides a curriculum focused on software engineering and software systems. The program has been a huge success and the first year of students, the class of 1999, graduated this spring.

For more information on the program, please visit the MSSE homepage http://www.msse.umn.edu/.

Congratulations Class of 1999!!! It has been a pleasure working with you over the past two years.

MSSE Class of 1999

  • Natalie Bennett, United Defense
  • Andrew Bergstrom, Datacard Group
  • Michael Breckenridge, Lifetouch Portrait Studios
  • Chad Brown, Datacard Group
  • Michael Calvo, Citronella Software
  • Kun-Feng Chen, Cyrus InterSoft Inc.
  • Nghi Chu, VTC Inc.
  • Glen Clarkson, Magenic Technology
  • Gloria Congdon, IBM Corp.
  • David Fraatz, 3M
  • Arvind Ganesan, Datacard Group
  • Maryanne Gay, Datacard Group
  • James Graham, CodeWeavers, Inc.
  • Megan Graham, Guidant Corp.
  • Traci Harwell, Medtronic Inc.
  • Tao He, Mycogen
  • Julie Hendrickson, Software AG Americas
  • Men Kim Hong, Lockheed-Martin Tactical Defense Systems
  • Shailendra Jain, Wynedge Software Inc.
  • Shawn Lambeth, IBM Corp.
  • Kevin Larsen, IBM Corp.
  • Michael Lissick, Wynedge Software, Inc.
  • Danian Liu, United Health Group Corp.
  • G. Joseph Morin, Onan Corp.
  • Kien Quan, University of Minnesota
  • Milinda Rambel Stone, University of Minnesota
  • Stephanie Sevcik, University of Minnesota
  • Arulmozhi Vijayakumar, Lawson Software Inc.
  • Janardhanam Vijayakumar, Renaissance Worldwide
  • Duo Wang, Honeywell Inc.
  • David Washburn, Seagate Technology Inc.

CREDITS

Soundbyte is published twice a year by the Department of Computer Science and Engineering, Institute of Technology, University of Minnesota. Please direct comments or questions to:

Soundbyte Editor
Department of Computer Science and Engineering
4-192 EE/CS Building
200 Union Street S.E.
Minneapolis, MN 55455

Department: (612) 625-4002
Fax: (612) 625-0572
Email:

Yousef Saad
Department Head

Vipin Kumar
Associate Department Head

Haesun Park
Director of Graduate Studies

John Carlis
Director of Undergraduate Studies

Website Designer
Vijay Ramanathan

The University of Minnesota is an equal
employment opportunity educator and employer