Colloquium Series Spring 2002

Sanguthevar Rajasekaran

With the widening gap between processor speeds and disk access speeds, the I/O bottleneck has become critical. In this era when every application demands the processing of voluminous data, the I/O bottleneck takes even more significance. Parallel Disk Systems (PDS) have been introduced to alleviate the problems associated with this bottleneck.

In this talk we give a brief introduction to PDS and summarize algorithms that have been developed for various basic operations. In particular, we consider the sorting and selection (including quantiles finding) problems. These algorithms are not only relevant to the PDS but also to many other parallel models of computing.

Weili (Lily) Wu

Spatial data mining is a process to discover interesting, potentially useful, and high utility patterns embedded in spatial databases. Efficient tools for extracting information from spatial data sets can be of importance to organizations which own, generate, and manage large spatial data sets. The current approach towards solving spatial data mining problems is to use classical data mining tools after ``materializing'' spatial relationships. However, the key property of spatial data is that of spatial autocorrelation. Like temporal data, spatial data values are influenced by values in their immediate vicinity. Ignoring spatial autocorrelation in the modeling process leads to results which are a poor-fit and unreliable. In this talk, a new approach, PLUMS (Predicting Locations Using Map Similarity), will be presented for supervised spatial data mining problems. PLUMS searches the space of solutions using a map-similarity measure which is more appropriate in the context of spatial data. It will be showed that compared to state-of-the-art spatial statistics approaches, PLUMS achieves comparable accuracy but at a fraction of the computational cost. Furthermore, PLUMS provides a general framework for specializing other data mining techniques for mining spatial data. This work is joint with S. Shekhar et al.

Dimitris Margaritis

Probabilistic models are useful for modeling non-deterministic data generation processes. Examples of these can be found in genetic domains representing gene expression interactions, socio-economic domains representing stock market prices influences by current events, and many others. The greatest problem in modeling such processes is determining the structure of the model. In my talk I will present work I have done at Carnegie Mellon towards inferring the structure of a specific class of models called Bayesian networks (BNs). I will present the GS ("grow-shrink") algorithm which uses conditional independence tests to determine the BN structure. I will also present a statistical independence test that shows progress towards a conditional independence test for domains with continuous variables, a problem currently unsolved in its generality. I will also show some results of an application that uses Bayesian network models to answer count queries from very large databases. My approach features constant time in the size of the database, a small space overhead, and linear preprocessing time. Moreover it is easily parallelizable and can be readily used for data-mining purposes, at no extra cost.

Tom Daniels

Network attacks and misuse are becoming increasingly devastating partly because attackers use sophisticated methods for hiding the origin of the attack. Network origin identification systems reduce an investigator's uncertainty of the source of network traffic thereby allowing filtering of the traffic, prosecution of the attacker, or other countermeasures.

Network origin identification systems are needed because there exist mechanisms in networks that effectively conceal the source of network traffic. For instance, past research has been very successful at developing anonymity systems for protecting privacy with little thought to holding users of the system accountable after the fact. As network attacks become more prevalent and devastating, attackers are concealing their location using mechanisms common in general purpose networks.

Our model of network origin concealment unifies network anonymity systems and ad hoc techniques. The model describes the mechanisms used to conceal the origin of network flows in both anonymity and ad hoc systems and how these mechanisms affect the measurable properties of network flows. Based on this, we demonstrate the difficulty of origin identification even when using ad hoc mechanisms.

In response to the problem of network origin concealment, recent research has developed network origin identification systems (NOIS). NOIS's use traffic analysis and other techniques to increase confidence in the source of flows. To better understand suggested origin identification techniques, we have developed a taxonomy of NOIS's that lends itself to describing past work as well as suggesting future areas of interest. In our recent work, we have chosen to concentrate on one subgroup of the taxonomy, passive NOIS. Given assumptions about network behavior and our ability to correlate traffic, we will present some worst and average case bounds on our ability to passively identify the origin in a number of network topologies. We hope that this and future work will guide network designers in choosing topologies and monitoring techniques for origin identification.

Srikanta Tirthapura

Distributed Queuing is a fundamental distributed coordination problem, arising in a variety of applications such as managing concurrent accesses to a mobile object, and scalable ordered multicast.

In the distributed queuing problem, processors in a network asynchronously and concurrently request to join a distributed queue. A distributed queuing protocol organizes these requests into a single queue, and each request learns the identity of its neighbors in the queue.

We focus on the Arrow protocol, a simple and popular solution based on path reversal on a network spanning tree. The Arrow protocol has been observed to perform well in practice, especially under high contention. To date, however, there has been no systematic analysis of this protocol's concurrent performance or its inherent scalability.

In this talk, I will present the first competitive analysis of the Arrow protocol in situations of high contention, showing that its performance is never far from an idealized "optimal" protocol. This analysis yields a surprising connection to the nearest neighbor Traveling Salesperson heuristic on a tree metric.

Time permitting, I will talk about the application of distributed queuing to ordered multicast, and on extending distributed queuing to low-latency distributed object management using pointer jumping.

Shelly Zhang

Multi-linked negotiation describes a situation where one agent needs to negotiate with multiple agents about different issues, and the negotiation over one issue influences the negotiations over other issues. Multi-linked issues will become important for the next generation of more complicated Multi-Agent Systems. However, most current negotiation research looks only at single issue negotiation and thus does not present techniques to reason and manage multi-linked issues. In this talk, I present a formalized model of the multi-linked negotiation problem, and describe a search algorithm based on this model for finding the best ordering of negotiation issues and their parameters. Using this algorithm, an agent can evaluate and compare different negotiation approaches and choose the best one. A technique based on the use of a partial-order schedule enables an agent to reason explicitly about the interactions among multiple negotiation issues. Experimental work is presented which shows that this management technique for multi-linked negotiation leads to improved performance.

Satinder Singh Baveja

The field of reinforcement learning (RL) has introduced into AI many abstract mathematical formulations of the problem of building agents that can learn to act in unknown, uncertain and dynamic environments, mostly by borrowing them from the fields of operations research and adaptive control. These RL formulations have allowed us to ask and answer precise questions about many important AI issues as well as to bring a (mostly) principled design methodology to many application areas. I will illustrate these twin advantages through two examples from my work. In the first part of the talk I will provide an answer to a formulation of the "exploitation-exploration" tradeoff: should an agent exploit what it already knows or should it explore in the hope of learning something that leads to even greater long-term return? In the second part of the talk, I will describe why and how RL offers a powerful methodology for designing many human-computer interaction systems. I will illustrate this methodology through our design, construction and empirical evaluation of NJFun (a system that provides telephonic access to a database of fun activities in NJ), and show that RL measurably improves NJFun's performance.

Carlotta Domeniconi

The nearest neighbor technique is a simple and appealing approach to pattern classification. It relies on the assumption of locally constant class conditional probabilities. This assumption however becomes invalid in high dimensions with finite samples due to the curse of dimensionality. Severe bias can be introduced under these conditions when using the nearest neighbor rule. We propose a technique that computes a locally flexible metric based on Chi-squared distance analysis to try to minimize bias. Our method produces neighborhoods that are highly adaptive to query locations: neighborhoods are elongated along less relevant feature dimensions, and constricted along most influential ones. As a result, the class conditional probabilities tend to be smoother in the modified neighborhoods, whereby better classification performance can be achieved. The efficacy of our method is validated and compared against other techniques using both simulated and real world data.

Kiri Wagstaff

One goal of research in artificial intelligence is to automate tasks that currently require human expertise. Unsupervised machine learning algorithms have had some impressive successes in this respect. For example, the Autoclass program analyzed a large body of infrared spectral data and discovered a sub-class of stars previously unknown to astronomers. Data mining algorithms are regularly used in the corporate world to extract useful information from large customer data bases. However, the majority of these algorithms are limited in what they can achieve. They can detect general trends and patterns in data, but they cannot make use of additional knowledge specific to the problem at hand, as a human expert would.

In this talk, I will describe a general method of enhancing clustering algorithms so that they can make use of domain-specific information. I will show how this technique can be used to make two commonly used clustering algorithms, k-means and COBWEB, more "intelligent". The modified algorithms are able to access and leverage problem-specific information expressed as a set of instance-level constraints about the relationships between items in the data set. Finally, I will describe the performance improvements these algorithms achieve when applied to two very different, challenging real-world problems from the domains of automated map refinement and natural language processing.

Maurice Herlihy

Miller Distinguished Lecture in Computer Science

In the past several years, a number of researchers have successfully applied techniques from Algebraic Topology to solve a number of long-standing open problems in the theory of distributed and concurrent computing. This talk will describe some basic problems in distributed computing, and how to solve them using notions from elementary Algebraic Topology. We will describe some open problems and possible future directions. This talk is intended for a general audience.

Laura Arns

In virtual environments, users are no longer passive observers of information, but active participants that have leaped through the computer screen and are now part of the information. This has tremendous implications on how users interact with computer information in the virtual world.

Perhaps the most common form of interaction in a virtual environment is locomotion. The term locomotion is used to indicate a user's control of movement through the virtual environment. Because virtual reality is a relatively young field, no standard interfaces exist for interaction, particularly locomotion. There have been few attempts to formally classify the ways in which virtual locomotion can occur.

Our work creates a new classification system for virtual locomotion methods. Such a classification can provide guidelines for designers of new VR applications, on what types of locomotion are best suited to the requirements of the new application. This talk will cover the classification system, and an experiment designed to validate selected portions of the classification system. This talk is intended to be of interest to both a general audience and VR specialists.

Barton P. Miller

Distinguished Lecture in Electrical & Computer Engg

Programs in execution have long been considered to be immutable objects.Object code and libraries are emitted by the compiler, linked and then executed; any changes to the program require revisiting the compile or link steps. In contrast, we consider a running program to be an object that can be examined, instrumented, and re-arranged on the fly. The DynInst API provides a portable library for tool builders to construct tools that operate on a running program. Where previous tools might have required a special compiler, linker, or run-time library, tools based on DynInst can operate directly on unmodified binary programs during execution. I will discuss how this technology can be used to subvert system security and present an interesting scenario for security vulnerability in Grid computing. The example comes from an attack that we made on the Condor distributed scheduling system.

For this attack, we created "lurker" processes that can be left latent on a host in the Condor pool. These lurker processes lie in wait for subsequent Condor jobs to arrive on the infected host. The lurker then uses Dyninst to attach to the newly-arrived victim job and take control. Once in control, the lurker can cause the victim job to make requests back to its home host, causing it execute almost any system call it would like.

Using techniques similar to those in intrusion detection, I show how to automatically construct a nondeterministic finite automata from the binary code of the Condor job, and use this NFA while the job is executing to check that it is not acting out of character.

Elizabeth D. Liddy

With the ever-increasing availability of statistical information on the Web, it is important to understand why and how people seek and use statistical information, and to develop and test prototype interfaces that aid in finding, understanding, and using tables. Our research, funded by NSF's Digital Government Program, aims at empowering users to ask questions quite naturally, the same way they do when submitting email queries to a virtual reference service, but here with dynamic interaction with the tables possible. This methodology uses Natural Language Processing to interpret and represent a user's needs and to match this representation against the metadata representation of tables' contents to find the requested data.

Our research utilized 1,000 email queries gathered from logs of users' seeking statistical information. These were analyzed in order to determine the dimensions of interest in typical statistical queries, as well as the linguistic regularities that can be captured in a statistical-query sublanguage grammar. We developed an ontology of query dimensions using this data-up analysis of the queries, and extended the ontology where necessary with values from actual tables. Next we developed an NLP statistical-query sublanguage grammar that enables the system to semantically parse users' queries and produce a template-based internal query representation, which will next be used to map these dimensions into the tables' metadata.

Joseph R. Kiniry

I'll present a new logic called ``kind theory'' that is meant to help represent and reason about the basic, intuitive semantics of reusable assets. The formalism is somewhat unusual in that it was designed with the user in mind, it has a loose, adaptable semantics that can be refined for new problem domains, and it is grounded in the epistemological foundations of knowledge and software reuse in open, collaborative environments. I'll also briefly discuss a complementary set of toolsthat realize and utilize the theory. These include a basic theorem prover, a reusable asset repository, and a design model checker.

Jin Tian

This talk concerns the assessment of the effects of actions or policy interventions, called ``causal effects'', from a combination of: (i) data and (ii) substantive assumptions. The assumptions are encoded in the form of a directed acyclic graph, called ``causal graph'', in which some variables are presumed to be unobserved.

Sufficient graphical conditions for ensuring the identification of causal effects were established by several authors, and a set of inference rules (Pearl's $do$-calculus) has been developed for inferring causal effects. However, there is no systematic method of applying $do$-calculus so as to decide whether a causal effect is identifiable or not.

In this talk, I will show a new method for identifying causal effects. I will show new graphical criteria for ensuring the identification of causal effects that generalize and simplify existing criteria in the literature. I will present algorithms that systematically decide the identifiability of causal effects and express those identifiable in terms of the observational joint distribution.

Sanguthevar Rajasekaran obtained his B.E. and M.E. degrees from the Indian Institute of Science in 1981 and 1983, respectively. He was awarded the Ph.D. degree in Computer Science in 1988 at Harvard University. Since then he has held faculty positions at the University of Pennsylvania and the University of Florida (where he was promoted to full professorship in 1999). Currently he is on leave from UF and is serving as the Chief Scientist at Arcot Systems, Santa Clara.

Visit Sanguthevar Rajasekaran's hompage here.

BACK

Weili (Lily) Wu

Weili Wu received her B.S. major in mechanical engineering in 1989 from Fuxin University, China, her M.S. major in economics in 1995 from the University of Wisconsin, USA, and her M.S. major in computer science in 1997 from the University of Minnesota, USA. She currently is a Ph.D. candidate in the Department of Computer Science and Engineering, University of Minnesota and is expected to receive her Ph.D. in Spring of 2002. Her main research interest is database systems. She has produced a number of research papers in spatial data mining, distributed database systems, and algorithm design. She is also a co-editor for a book in clustering and information retrieval.

Visit Weili (Lily) Wu's hompage here.

BACK

Dimitris Margaritis

Dimitris Margaritis is a Ph.D. student at the department of Computer Science at Carnegie Mellon University. He holds a BS in Physics from the University of Athens, Greece and a MS in Computer Science from SUNY Stony Brook. In the past he has worked on a diverse number of projects such as multi-agent modeling, computational DNA sequencing by hybridization, image database retrieval, and 3D computer vision for robots. More recently his work is on developing a multiresolution statistical independence test for continuous variables, and implementing fast, approximate querying of count information from very large databases, using Bayesian network techniques.

His current interests are in machine learning, probability theory, decision theory, and statistics, with a focus on Bayesian network structure induction. He is particularly interested in innovative applications of machine learning techniques to difficult problems. Mr. Margaritis is a member of AAAI, the Hellenic Artificial Intelligence Society, and Sigma Xi.

Visit Dimitris Margaritis's hompage here.

BACK

Tom Daniels

Tom Daniels is a graduate student in Computer Science at Purdue University, and expects to graduate with a Ph.D in Summer 2002.

He received his Bachelor's degree in Computer Science from Southwest Missouri State University in 1995 and his Master's degree (also in Computer Science) from Purdue University in 1998. His research interests include network security, network traffic tracking and management, and detecting message patterns in distributed object systems.

Visit Tom Daniels's hompage here.

BACK

Srikanta Tirthapura

Srikanta Tirthapura is a graduate student in Computer Science at Brown University, and expects to graduate with a Ph.D in Summer 2002.

He received his Bachelor's degree in Computer Science from the Indian Institute of Technology, Madras in 1996 and his Master's degree (also in Computer Science) from Brown University in 1998. His research interests include distributed computing, scalable multicast and algorithms for massive data sets.

Visit Srikanta Tirthapura's hompage here.

BACK

Shelly Zhang

Xiaoqin (Shelley) Zhang is a PhD Candidate in the Computer Science Department at the University of Massachusetts at Amherst. She received a B.S. in Computer Science from University Of Science & Technology Of China in 1995, and a M.S. in Computer Science from the University of Massachusetts, Amherst in 1998. Her research interests include multi-agent systems, sophisticated negotiation and cooperation, intelligent agent architecture designing, information gathering, e-commerce, distributed systems and artificial intelligence.

BACK

Satinder Singh Baveja

Satinder Singh Baveja received his Bachelor's degree in Electrical Engineering from Indian Institute of Technology, New Delhi in 1987. He received his Master's degree in 1991 and Ph.D degree in 1993, both in Computer Science from University of Massachusetts. He then served as a Postdoctoral Fellow at the Center for Biological and Computational Learning in Massachussets Institute of Technology until 1995. He has been an Assistant Professor in the Department of Computer Science at the University of Colarado, Boulder. He has also served as Principal Technical Staff Member in the Artificial Intelligence Department at AT&T Labs-Research. He is currently Chief Scientist in Syntek Capital.

His research focuses on developing theory, algorithms and technology for building agents that can learn by interaction in complex, dynamic and uncertain environments. His deepest involvement and contribution is to the field of reinforcement learning or automated decision making. More recently, he has been taking seriously the challenge of building agents that can interact with other agents and even humans in both artificial and natural environments.

Visit Satinder Singh Baveja's hompage here.

BACK

Carlotta Domeniconi

Carlotta Domeniconi is a Ph.D. candidate in the Department of Computer Science and Engineering at the University of California, Riverside. She received her M.A.Sc. degree in Information and Communication Technologies at the International Institute for Advanced Studies, Italy in 1997, and her B.A.Sc. degree in Computer Science at the University of Milano, Italy in 1992. Her research interests are in the areas of machine learning, pattern recognition, and data mining. Pattern classification has been the main focus of her research work. She is particularly interested in the development of locally adaptive metric techniques for high performance classifiers. She is also interested in developing efficient techniques for classifying data streams on-line, possibly by means of kernel methods such as SVMs. She intends to pursue the development of new machine learning techniques for real life problems, such as stream data models for networking problems, and data mining techniques for the analysis of gene expression array data.

Visit Carlotta Domeniconi's hompage here.

BACK

Kiri Wagstaff

I grew up in southeastern Utah and received my B.S. in Computer Science from the University of Utah in 1997. I then came to Cornell as a PhD candidate, and have spent my summers either teaching at Cornell or working as an intern (at the Jet Propulsion Laboratory and at DaimlerChrysler's Research and Technology Center in Palo Alto, CA). I am working on a minor in Astronomy, and I have a strong interest in planetary studies in particular. I also participate in competitive ballroom dancing and I am a brown belt in shito-ryu karate.

Visit Kiri Wagstaff's hompage here.

BACK

Maurice Herlihy

Maurice Herlihy's research interests focus around practical and theoretical aspects of designing, implementing, and reasoning about concurrent and distributed systems. He has an degree in Mathematics from Harvard University, and a Ph.D. degree in Computer Science from M.I.T. He has been a faculty member in the Computer Science Department at Carnegie Mellon University, and a member of research staff at Digital Equipment Corporation's Cambridge Research Lab. In 1994, he joined the Computer Science Department at Brown University.

Visit Maurice Herlihy's hompage here.

BACK

Laura Arns

Laura Arns is currently a Ph.D. candidate in the Department of Computer Science at Iowa State University. She is expected to received her Ph.D. in Spring of 2002. She holds a MS in Computer Science from Iowa State, and a BA in Computer Science and Mathematics from Wartburg College. Her primary areas of interest are applied virtual environments, and human factors and usability in virtual environments.

Visit Laura Arns's hompage here.

BACK

Barton P. Miller

Barton Miller is Professor of Computer Sciences at the University of Wisconsin, Madison. He leads the Paradyn Parallel Performance Tool project, which is investigating performance and instrumentation technologies for parallel and distributed applications and systems. His research interests include parallel and distributed program measurement, computer security, extensible operating systems, and mobile computing.

Miller's research is supported by the U.S. Department of Energy, National Science Foundations, Office of Naval Research, and various corporations.

Miller was Program co-Chair of the 1998 ACM/SIGMETRICS Symposium on Parallel and Distributed Tools, and General Chair of the 1996 ACM/SIGMETRICS Symposium on Parallel and Distributed Tools. He also twice chaired the ACM/ONR Workshop on Parallel and Distributed Debugging. Miller was on the editorial board of IEEE Transactions on Parallel and Distributed Systems, and is currently on the Boards of Concurrency and Computation Practice and Experience, Computing Systems, and the Int'l Journal of Parallel Processing. Miller has chaired numerous workshops and has been on numerous conference program committees. He is a member of the Los Alamos National Laboratory Computing, Communications and Networking Division Review Committee, and has been on the Advisory Committee for Tuskegee University's High Performance Computing Program and the Advisory Board for the International Summer Institute on Parallel Computer Architectures, Languages, and Algorithms in Prague. Miller was (and continues to be) an active participant in the European Union APART performance tools initiative.

Miller received his Ph.D. degree in Computer Science from the University of California, Berkeley in 1984. He is a Fellow of the ACM.

Visit Barton P. Miller's hompage here.

BACK

Elizabeth D. Liddy

Dr. Elizabeth D. Liddy is a Professor in the School of Information Studies at Syracuse University and Director of its Center for Natural Language Processing, where she leads a team of 18 researchers focused on developing human-like language-understanding software technologies. Dr. Liddy's research has been continuously focused on applying linguistic theories and technologies to improving information access since her dissertation research in 1988 that won 3 prestigious international awards for pioneer work in the successful application of linguistic theory to information retrieval.

Since that time, Dr. Liddy has successfully applied Natural Language Processing to information access technologies, such as: data-mining, question-answering, automatic multiple-document summarization, cross-language retrieval, knowledge management, and 2-stage web-based retrieval. Her technology has been applied in the domains of business, banking, alternative medicine, patents, travel, public health, international security, crisis management, government statistics, engineering, and education.

Dr. Liddy's research agenda has been continuously supported by both government and corporate funders on a total of 43 projects. Her research has resulted in 80+ professional papers and hundreds of presentations, both here and abroad. Additionally, Dr. Liddy is the inventor on 7 patents in the area of Natural Language Processing.

Visit Elizabeth D. Liddy's hompage here.

BACK

Joseph R. Kiniry

Joseph Roland Kiniry is a Ph.D Candidate in the Department of Computer Science at the California Institute of Technology. He received a B.S. in Mathematics and a B.S. in Computer Science from Florida State University in 1992, followed by a M.S. in Computer Science from the University of Massachusetts, Amherst in 1995, and a M.S in Computer Science from the California Institute of Technology in 1998. His research interests include formal methods, foundations of mathematics, software engineering, distributed systems, object-oriented systems and languages, components, knowledge representation, systems modeling, artifical life, and the many different theoretical underpinnings of computing.

Visit Joseph R. Kiniry's hompage here.

BACK

Jin Tian

Jin Tian is a candidate for a faculty position in the Department of Computer Science at ISU. Jin Tian's research interests include artificial intelligence, probabilistic and causal reasoning, and causal discovery from data. His doctoral research on Causal Inference, in collaboration with Professor Judea Pearl has resulted in several publications in UAI and AAAI. Jin Tian received a B.S. in Physics from Tsighua University, and an M.S. in Physics and Astronomy from UCLA. He expects to receive his Ph.D. in Computer Science from the University of California at Los Angeles.

Visit Jin Tian's hompage here.

BACK

---

Miller Distinguished Lecture

The Miller Lecture Series is made possible by the generosity of F. Wendell Miller, who left his entire estate jointly to Iowa State University and the University of Iowa. Mr. Miller, who died in 1995 at age 97, was born in Altoona, Illinois, grew up in Rockwell City, graduated from Grinnell College and Harvard Law School and practiced law in Des Moines and Chicago before returning to Rockwell City to manage his family's farm holdings and to practice law. His will helped to establish the F. Wendell Miller Trust, the annual earnings on which, in part, helped to support this activity.

---

Archives

• Fall 2001
• Spring 2001
• Fall 2000
• Spring 2000
• Fall 1999
• Spring 1999
• Fall 1998
• Summer 1998
• Spring 1998
• Fall 1997
• Spring 1997

(Top)

---

Contacts

Thank you for visiting this page. Please send your suggestions and comments to one of us in the Computer Science colloquium committee.

• Soma Chaudhuri . chaudhur@cs.iastate.edu
• Xiaoqiu Huang. xqhuang@cs.iastate.edu
• Anantharaman Kalyanaraman. ananthk@cs.iastate.edu

(Top)

---

ananthk@cs.iastate.edu