Jaideep Srivastava - US grants

Description: This project supports travel of fifteen U.S. scientists to the Institute of Electrical and Electronic Engineers (IEEE) Region 10 Conference (TENCON), planned for November 22-24, 1989 in Bombay, India. The Indian Technical Co-Chairman is Dr. M. V. Pitke at the Tata Institute of Fundamental Research (TIFR) in Bombay. The Conference theme is "Information Technologies for the 90's, " and will deal with advances in: networks; communication systems; signal processing; computers and applications; circuits and devices and energy. The IEEE Region 10 comprises countries of South East Asia, far East and Australasia, including India, Pakistan, Japan, South Korea, Taiwan, Hong Kong, PR China, Singapore, Indonesia, Phillipines, Australia and New Zealand. The meeting will have representatives from most of these countries and also from various regions in India. The organizers include some of the U.S. and India's leaders in electrical, electronics and communication engineering. They also have as advisors experts from major U.S. laboratories in industry and academia, as well as others from Europe and Japan. Scope: Region 10 of the IEEE has a large potential for high technology in terms of manpower which will greatly benefit from this conference. The U.S. stands to gain from tapping scientific advances in the region in areas such as probability and statistics and their applications to eletronics and communications, including control theory and signal processing. The U.S. participants will interact with leading research organizations in India, and learn of specific problems in technology, adaptation and research efforts in developing countries' settings.

This research address the problem of relational query optimization for general purpose parallel machines. The principle objective of this project to develop query optimizer that will generate efficient query plans for parallel machines. The three main components of a database query optimizer are its query plan representation, its cost model, and its search algorithm. This project addresses the issue of developing a plan representation that incorporates intra- and inter-operator parallelism, as well as pipelining. Furthermore, cost models will be developed which distinguish between the total work done, i.e. the (sequential) time it would take on a uni-processor and total (parallel) time taken on a multi-processor. The cost model depends on the query and database parameters, as well as architecture parameters. A cost-based search algorithm selects efficient (low cost) query plans. Since the search space is much larger than that found in uni-processor query optimization, this research will develop new heuristics to prune the search space. Furthermore, since a multiprocessor is available, the research will also investigate applicability of parallel processing to the optimization process itself. The results of this research will have an impact on efficient query processing in parallel relational databases.

9554517 Sameh This proposal outlines a plan for recruiting and training a set of high-quality graduate students focusing on the important area of information discovery on the information super-highway through human interface design for access to computers and networked information. The plan builds upon faculty excellence in this area to create a focused program of research that will make Minnesota a leader in this emerging area. The plan also contains several inlovative components that will ensure that we can recruit top- quality students, including women and students of color, who are currently severely underrepresented in computer science. And, it provides a complete graduate experience for these students including industrial internships, training and practice in teaching, and a supportive, mentored environment. At its completion, this program will produce PhDs that are fully capable of becoming productive faculty members at research universities and top- ranked colleges. In the process, we hope to establish a pipeline bringing the best graduates from Howard University and Vassar College to the University of Minnesota for graduate degree.

9818338
Tripathi, Anand
Zhang, Zhi-Li
University of Minnesota - Twin Cities

CISE Research Instrumentation: Research in Networked Information Systems

This research instrumentation enables research projects in:
- Scalable and QoS-Aware Multimedia Systems
- Agent-Based Distributed Computing
- High Performance Geographic Information Systems, and
- High Performance Data Mining

To support the aforementioned projects, this award contributes to the purchase, consisting mainly of a CISCO Catalyst 5505 network switch, two Sun Enterprise, and various Sun Ultra, by the Department of Computer
Science and Engineering at the University of Minnesota. This instrumentation will support research in new paradigms, system architectures, and algorithms for network computing involving distributed multimedia systems, mobile Internet agents, geographic information systems (GIS), and data mining and information search over the Internet. The research in distributed multimedia systems is investigating scalable server
architectures, specification of QoS measures, and mapping of QoS measures to resource allocation and scheduling decisions. The research in agent-based Internet computing focuses on programming abstractions and their underlying mechanisms for secure and robust agent-based computing. Several agent based applications are being investigated by this project, including a multimedia based active mail system. The research activity in GIS is investigating parallelization and other approaches for efficient execution of range query and map overlay operations. This research, together with the activities in distributed multimedia, is addressing QoS problems for the presentation of graphics and images resulting from GIS queries. The research in data mining is investigating parallel algorithms for large data sets obtained from various Internet sites. The synergy among the various activities of these projects is realized through several
focal-point applications. These applications are related to agent-based multimedia mail system, Digital Earth initiative, and the Sky Survey project.

Rare events occur very infrequently and are thus very difficult to detect. However, when they do occur, their consequences can be quite dramatic quite often in a negative sense. Examples include network intrusions and security breaches, cardiac events, credit card and other types of financial fraud, telecom circuit overloads, and traffic accidents. Timely and accurate detection of rare events is critical. Recent years have seen an explosive growth in the speed of data collection and storage devices. Most organizations collect quantities of data about various processes in their computer systems, at various levels of abstraction, including hardware, operating and communication systems, database query logs, etc. These comprehensive event logs provide a wealth of data, analysis of which has the potential to identify the rare events described earlier. The project includes investigation of the issues in rare class analysis, and development of a suite of techniques to address them. The focus of this project is on supervised learning methods for rare class analysis. Specific tasks include development of novel feature selection schemes and robust predictive models especially suited for rare class problems, and adapting rare class learning algorithms to data streams. The research results will be made publicly available at the project website (http://www.cs.umn.edu/~kumar/rare.html). The techniques developed, as part of this research will be applicable across a wide spectrum of applications in which one is interested in finding those few, unusual, special cases which are highly significant and of potentially very high value.

In 1960, Jane Goodall began the first long-term field study of the closest living relatives of humans, chimpanzees (Pan troglodytes), in Gombe National Park, Tanzania to describe their behavior by making extensive observations in their natural habitat. This study, which continues today, has made many contributions to understand chimpanzee behavior and human evolution, and has also inspired people around the world to study science and work toward wildlife conservation. Analysis of the complete observational dataset from Gombe and other field studies, such as the Kanyawara chimpanzee project, has the potential of providing new insights into many unanswered behavioral ecology questions, e.g. the influence of social relationships within the group on territorial behavior.

However, this observational paradigm is extremely labor-intensive and only a small part of the Gombe dataset has been analyzed so far. The goal of this project is to begin developing data analysis tools and techniques to reduce the time and effort required to analyze observation datasets. Expected results include a cartridge for mining concept patterns, a computationally efficient execution environment for concept pattern mining, and spatial semi-supervised learning algorithms to improve classification performance in creating maps. Expected results will not only benefit behavioral ecologists, but also contribute to research in many other spatio-temporal application domains, including location based services, transportation and epidemiology. Dissemination plans include development of instructional tools based on the Gombe data to motivate younger students to learn science and information technology as well as a workshop to increase collaboration between Computer Scientists and Behavioral Ecologists.

Abstract
This major inter-disciplinary research effort will use virtual worlds as an exploratorium to theoretically extend and empirically model the dynamics of group behavior. In the process it will develop novel computational techniques for analyzing large-scale networks, which will have applicability across a wide variety of domains.

The most important and complex decisions made by governments and organizations occur in group contexts. A central challenge, spurred by new developments in information technologies (IT), is that the nature of groups and how they operate has changed radically. Today, many groups ? in social, political, and economic contexts - are ad hoc, agile, transient entities that emerge from a larger primordial network of relationships. For a short time, these groups accomplish a variety of tasks, and then they dissolve, only to be reconstituted later with a different configuration. While there is growing awareness of the socio-economic consequences of these groups, our understanding of how they form and their impact on effectiveness is severely limited.

This project will address this limitation by developing a theoretical framework that reflects the contemporary conceptualizations of groups. It proposes a network approach to modeling the eco-system of overlapping and constantly changing groups that constitute the fabric of contemporary society. It recognizes that empirically testing such a model poses formidable data collection challenges. However, a unique resource available to the research team is access to all behavioral traces (server logs) from one of the world''s largest Massively Multiplayer Online (MMO) games, EverQuest 2, which is particularly well-suited to theorize and empirically model the dynamics of group behavior. MMOs comprise tens of thousands of players who are at any one point in time coalescing in thousands of groups to accomplish """"""""quests"""""""" and """"""""raids"""""""" that involve a variety of activities similar to tasks we undertake in real life ? finding information or materials, making, selling or buying products and services.

Beyond the data collection challenge, the scale of the proposed research enterprise also poses significant computational challenges in uncovering and analyzing the complexities that govern the dynamics of group behavior in these virtual worlds. Using advanced computing applications and technologies, this project seeks to capture, infer, and model the networks that explain how groups emerge and how they function. Specifically, the researchers will use temporally evolving graphs to model such networks, and develop scalable algorithms to compute metrics of group behavior on them. Tying these complex and shifting individual and networked behaviors to traditional forms of analyses represents a novel interdisciplinary challenge in both scope and complexity.

The project will expand our knowledge of how groups form and operate in larger ecosystems of groups, individuals, and organizations. The analysis of logs generated from Virtual Worlds poses novel challenges from a computational perspective. This interdisciplinary investigation will result in new (1) information models for modeling the Virtual World, (2) data structuring and algorithmic techniques for data access and analysis, and (3) techniques for computational efficiency.

The knowledge and tools developed in this research will allow researchers to understand more fully, and practitioners to cultivate more effectively, the emergence and performance of ad hoc groups in contemporary society. It will also provide other disciplines with new computational and statistical modeling methodologies and tools, which should have considerable positive implications for future research in other disciplinary areas. The findings and deliverables of the proposed research will be immediately generalizable to training and education related to groups (beyond just MMOs or Virtual Worlds), social networks, and online games.

This award provides support to approximately fifteen graduate students in the
United States to attend the 2007 SIAM Conference on Data Mining (SDM 2007), held in Minneapolis, USA from April 28th to April 30th, 2007 (http://www.siam.org/meetings/sdm07/). This technical conference is the premiere venue for presenting new research results in the area of data mining, and is widely attended by researchers and practitioners in the field.

Attending this conference is of paramount importance for the development of graduate students. Participants have the opportunity to present their work, attend panel and keynote sessions, and interact with other graduate students as well as hundreds of other leading researchers in the area of data mining. The travel support targets graduate students with accepted papers and in particular women and under-represented minority students in order to enhance their educational experience and foster diversity in the data mining research area.

The investigator will use the funds from this grant to support the travel of students to the 2008 SIAM Data Mining (SDM 2008) Conference on Data Mining. This conference will be held in Atlanta, USA from April 24th to April 26th, 2008 (http://www.siam.org/meetings/sdm08/).
Jointly organized by computer scientists and statisticians, this technical conference is a premiere venue for presenting new research results in the area of data mining, and is widely attended by researchers and practitioners in the field. Selection of award recipients will be done on the basis of quality of their research progress, as well as the potential to benefit from attending this meeting. Special emphasis will be given to graduate students, and in particular women and under-represented minority students, since attending conferences is an important part of their educational experience, and they often have limited travel funds.

Attending conferences such as SDM is of paramount importance for the development of graduate students. Participants have the opportunity to present their work, attend panel and keynote sessions, and interact with hundreds of others performing leading-edge research in the field.
Such experiences help students in a number of ways ways. First, it enables them to get exposure to a wide range of cutting edge ideas in their field, beyond what they are likely to be exposed to in their home institutions and research groups. Second, it provides them an opportunity to meet established researchers, which can potentially lead to long term interactions and mentoring relationships. Third, in case they are presenting a paper, it provides an opportunity for early feedback on their thesis research and presentation skills from a broad audience. All of these benefits are invaluable in ensuring the development of research excellence, leading to a productive career in innovative research. Given that cutting edge innovation is critical to the United States' economic preeminence in the world, and a future workforce trained to be innovative is critical for it, the proposed project is well aligned with the national agenda.

The objective of this research is to bring high levels of system reliability and integrity to application domains that cannot afford the cost, power, weight, and size associated with physical redundancy. The approach is to develop complementary monitoring algorithms and novel computing architectures that enable the detection of faults. In particular, there is a significant opportunity to reduce the reliance on physical redundancy by combining model-based and data-driven monitoring techniques. Implementing this approach to fault detection would be difficult with existing software and computing architectures. This motivates the development of a general purpose monitoring framework through monitoring-aware compilers coupled with enhancements to multi-core architectures.

The intellectual merit of the project is twofold. First, it has the potential to lead to a novel fault detection approach that blends complementary monitoring algorithms. Second, advances in multi-core processors are leveraged to enable implementation of these fault detection approaches. This addresses key themes in cyber-physical systems by investigating the fundamental issue of fault detection for physical systems and by developing a generic processor architecture for monitoring.

With respect to broader impact, project offers the potential for positive influences on industrial practice and education. If successful, the design ideas from this project can be incorporated into low-cost multi-core architectures suitable for embedded systems. The potentially transformative performance improvement offered by this framework could also impact current research in run-time verification and on-line monitoring. The research is to be incorporated into the course "Design, Build, Simulate, Test and Fly Small Uninhabited Aerial Vehicles" for senior undergraduate and first-year graduate students.

Terra Populus: A Global Population/Environment Data Network (TerraPop) will develop organizational and technical infrastructure that will integrate, preserve, and disseminate data describing changes in the human population and environment over time. A plethora of high-quality environmental and population datasets are available, but they are widely dispersed, have incompatible or inadequate metadata, and have incompatible geographic identifiers. The project will enable researchers to identify and merge data from heterogeneous sources to study the relationships between human behavior and the natural world.

TerraPop will focus on four specific kinds of data: (1) census and survey microdata describing the characteristics of individuals and their families and households; (2) aggregate census and survey data, describing the characteristics of places, including aggregate population characteristics, land use, and land cover; (3) remote-sensing data describing land cover and other environmental characteristics; and (4) climate data describing temperature, precipitation, and other climate-related variables. All four data types have an important temporal dimension; most of the data span the past five decades, and some sources reach back to the nineteenth century. TerraPop will make these data interoperable across time and space, disseminate them to the public and to multiple research communities, and preserve them for future generations.

Understanding of interactions between population and the environment has been hampered by the dearth of internationally comparable data. This infrastructure will expand the quality and quantity of such data while making them highly interoperable and easily accessible. Population data closely integrated with data on the environment will allow us to describe the unfolding transformation of human and ecological systems. Data on the human population are crucial for understanding changes in the Earth?s biological and climate processes; equally important, data on climate and land provide essential tools for understanding the impact of environmental change on human behavior. By creating a framework for locating, analyzing, and visualizing the world's population and environment in time and space, TerraPop will provide unprecedented opportunities for investigating the agents of change, assessing their implications for human society and the environment, and developing policies to meet future challenges. The data collection and its analysis tools will contribute to education and public understanding. It will allow teachers to integrate research and teaching, bringing the excitement of discovery into the classroom from primary school to graduate school. More broadly, TerraPop will be a model for the sustainable expansion, maintenance, and improvement of a global data resource.

This research project will develop a theoretical and computational framework to understand and enable the socio-technical dynamics shaping the assembly of teams in distributed global contexts. The main barrier to understanding and explaining the role of human centered computing in team assembly is finding a suitable research environment where (1) geographically distributed individuals from potentially different cultures are assembling in teams of varying sizes to accomplish a variety of tasks over varying durations; (2) their actions, interactions and transactions are captured with precise time-stamps; and (3) their outcomes would be recorded with well-defined metrics. Massively multiplayer online role-playing games offer a research environment that meets all of these requirements. EVE Online, a massively multiplayer online role-playing game, offers a potentially suitable research opportunity to study the assembly of teams and ecosystems of teams. It is notable for allowing as many as tens of thousands of people to interact simultaneously on a single server cluster, from around the world, through a well-developed economic system and serious long-term coalitions, in a more flexible action framework than many other popular games possess.

This high-risk high-payoff project will explore the feasibility of using data from EVE Online to identify the socio-technical and cultural mechanisms that explain the assembly of teams more generally. If successful, the study will serve as a model for larger scale studies that, in addition to identifying the assembly mechanisms also assess the impact of these mechanisms on the performance of global teams. The most important and complex decisions in society are made in teams. And yet, assembling effective teams is a daunting task. While there is an awareness of how team collaborations can spearhead socio-economic change, we still have sparse sociotechnical knowledge of how globally distributed cross-cultural teams and systems of teams are assembled. This project seeks to address this limitation. First, the proposed research offers the promise to launch a new generation of theorizing and research on the assembly mechanisms of teams and ecosystem of teams. The empirical data that will be used to develop and test these theories will be a high risk effort but with potential for unprecedented scale, size, and completeness. Second, the research will arguably be the first effort in the field of social networks to develop hypergraph techniques to study assembly of teams and ecosystems of teams.

The knowledge and tools developed in this research will allow practitioners to cultivate more effectively the emergence and performance of ad hoc teams in business, science and gaming. It will also provide other scientific disciplines with new computational statistical modeling methodologies and tools to model hypergraphs.

Rapid growth in the amount and richness of online interactions through social networking applications is creating data at unprecedented scales. This includes data about individual's characteristics as well as their connections and interactions. Many real-world applications have complex group dynamics involving multiple people. The analysis of such group interactions has the potential to revolutionize social sciences, business, and commerce domains. The goal of this project is to develop a novel computational framework to support scalable analysis of group dynamics in large social networks. The key idea is to explicitly model groups of individuals rather than simply capturing links between pairs of individuals. The broader impacts of this project will consist of enabling richer analysis of complex interactions in real-world networks. It will also enhance the University of Minnesota Computer Science curriculum through courses and research experiences with synergy between the areas of computer systems and data mining.

To model group interactions in networks, this project will use hypergraphs, a generalization of graphs, where hyperedges represent relations between one or more entities. Hypergraphs have the potential to provide higher modeling accuracy for many group phenomena, as well as higher storage and computational efficiency, compared to their graph counterparts. This project will develop an analysis framework called MESH: Minnesota Engine for Scalable evolving Hypergraph analysis, that will provide algorithms and system components to support scalable analysis of evolving hypergraphs. The MESH algorithms will be designed to model and compute several common data-driven questions related to group dynamics in real-world networks. The MESH system-level techniques will be designed to support the execution of these algorithms in a distributed and scalable manner.

For further information see the project web site at: http://mesh.cs.umn.edu