Ambuj K. Singh - US grants

In spite of the wide variety of synchronization problems and their broad-ranging solutions, some fundamental questions regarding the nature and classification of synchronization have remained unanswered. Led by the observation that any synchronization necessarily involves some kind of arbitration among the participating processes. The notion of the "rank" of a process that serves as the basis for arbitration has been formulated, and an underlying mechanism, called the "ranker", that computes the ranks for the processes has been identified. In order to carry out any kind of arbitration, the ranks that are computed by the ranker module should satisfy certain requirements. By identifying these properties, four different specifications are obtained for the ranker module; these four rankers form a hierarchy. Based on the correspondence between a synchronization problem and the weakest ranker that can be used to solve it, a classificiation of synchronization problems is obtained. This classification subsumes the other classification proposed in the literature. The problem of implementing rankers on various architectures will be considered and the project intends to devise algorithms for translating programs across different architectures.

Communication and synchronization among processes is of fundamental importance in parallel and distributed systems. Together, they have an impact on the efficiency, the design, and the understanding of concurrent programs. This research aims at examining shared variable and message passing systems with respect to mechanisms for interprocess communication and synchronization. In the case of shared variable systems, the question of cache coherence and the appropriateness of non-atomic shared memory is considered. Proof techniques and programming methodologies are developed for dealing with non-atomic memories. In the case of message passing systems, the question of locality of computations is investigated. Complexity measures that measure locality and efficient algorithms for commonly occurring synchronization problems are developed. The impact of failures and dynamic networks on algorithms and tight lower bounds on various performance measures are explored. Finally, the research examines mixed programming paradigms that support both shared memory and message passing. As a part of this research, efficient simulations of shared memory on an underlying message passing architecture are designed.

EIA-0080134
Singh, Ambuj
University of California - Santa Barbara

CISE Research Infrastructure: Digital Campus: Scalable Information Services on a Campus-Wide Wireless Network

Researchers at the University of California at Santa Barbara will implement a wireless-networked, distributed heterogeneous environment on campus and use it to conduct research in databases, networking, distributed systems, and multimedia. The PIs will focus on large-scale systems in which data is the critical resource and system services are based on various data manipulation functions including data collection, movement/delivery, aggregation/processing, and presentation. A significant part of the research will be conducted using a digital classroom, a remote classroom, and individual and team kiosks. Services such as lecture on demand, virtual offices, and remote learning will be provided using this infrastructure. Specific research issues that will be investigated include content-based access, personalized views, multi-dimensional indexing, smart end-to-end applications, joint source-network coding, scalable storage, reliable network service, information summarization, distributed collaboration, multimedia annotation, and interactivity.

EIA-9986057
Kenneth Rose
Univ. of California-SB

CISE Research Instrumentation: Research in Computational Multimedia

The departments of Computer Science and Electrical Engineering at the University of California, Santa Barbara will purchase the following infrastructure equipment: an SGI 2100 multimedia server with three client SFI 02 workstations to manage, process and stream multimedia data onto a wireless local area network with several PC's on the backbone Ethernet and mobile computers (laptop computers and handheld devices); an MPEG-2 encoder from Optivision, still and video cameras as input devices, and high resolution monitors and a color laser printer for display and presentation. This equipment will be dedicated to support research in computer and information science and engineering with the main focus on computational multimedia research related to multimedia signal processing, databases, networking and communications. The equipment will be used by several interrelated research projects. These projects include: clustering, indexing, and data mining in high dimensional feature spaces; scalable audio and video over IP and wireless networks; data warehousing in mobile environments; and shared multimedia objects in mobile environments.

This collaborative project brings together a strong multi-institutional interdisciplinary team of investigators to study and advance the current understanding of cellular and sub-cellular events. Continuing technological advances in fluorescence and atomic-force microscopy allow scientists to observe molecular function, distribution, and interrelationships in living cells. However, a full understanding of tens of thousands of proteins and the complex molecular processes they engage in requires a voluminous amount of image data, which currently must be analyzed by visual inspection. To facilitate such an analysis, researchers from the four participating institutions are focusing on three main research thrusts. First, next-generation intelligent imaging involves information processing at the sensor level to enable high-speed and super-resolution imaging. The goal is to enable biologists to study cellular processes at resolutions in time and space that are not possible with current technologies. The second research thrust is pattern recognition and data mining as applied to bio-molecular image collections. Salient features that characterize the underlying patterns in cells and tissues need to be computed for the vast volumes of images acquired through automated microscopy. Third, a distributed database of bio-molecular images is being created. The merging of pattern-recognition and data-mining tools with new, powerful methods for indexing, data modeling, and collaboration, is aimed at creating a unique infrastructure that greatly facilitates image bioinformatics, thus complementing recent revolutionary advances in genomics.

The outcome of this research will lead to new and novel information-processing methods for bio-molecular image data. Efficient and effective representation of such data will enable researchers to search and browse through large collections of image and video data and look for similar patterns in such datasets, thus facilitating information discovery. During its five-year duration, this project will develop, test, and deploy a distributed database of bio-molecular image data accessible to researchers around the world. The impact of the distributed database will be through large-scale biology in which the results of a single experiment can be globally correlated with the results from other groups of scientists, thus accelerating discovery of dynamic relationships between structure and function in complex biological systems.

The project will develop new courses, and will facilitate student exchanges, semi-annual meetings, and workshops, benefiting students at all levels. This project will train a new generation of biologists, computer scientists and engineers well versed in the imaging and information-processing sciences at the forefront of next-generation biotechnology. Partnership will be established with institutions with large populations of students from groups underrepresented in science and engineering, such as the California State Universities at Fresno and San Bernardino and the Universidad Metropolitan in Puerto Rico, for undergraduate recruitment and outreach. An effective mode of outreach for students is to educate their teachers, and the project will offer summer fellowships for elementary, high-school, college, and university teachers.

A number of scientific endeavors are generating data that can be modeled as graphs: high-throughput biological experiments on protein interactions, high-throughput screening of chemical compounds, social networks, ecological networks and food webs, database schemas and ontologies. Mining and analysis of these annotated and probabilistic graphs is crucial for advancing the state of scientific research, accurate modeling and analysis of existing systems, and engineering of new systems. The goal of this research project is to develop a set of scalable querying and mining tools for graph databases by integrating techniques from the fields of databases, bioinformatics, machine learning, and algorithms. New algorithms are being developed, and these are being examined for their quality and running time on real datasets. The first set of algorithms addresses subgraph and similarity querying in graph databases. The second set considers the mining of significant subgraphs or motifs. A novel significance model which transforms graphs into histograms of primitive components and examines the significance of motifs in the transformed domain is being developed. The third set of algorithms targets the discovery of well-connected clusters in large probabilistic graphs. The project integrates research and education by introducing the results of the research into undergraduate and graduate courses. Robust open-source tools based on the developed algorithms will be released for other researchers. These will be helpful in the study of the structure and organization of large networks that are becoming increasingly common.

Elements of uncertainty are inherent to management and analysis of complex image data for scientific and engineering applications. The work builds on previous multidisciplinary work for storage, management, and analysis of biological images of cellular architectures in the vertebrate central nervous system and sub-cellular environments, but the techniques are general and target other areas, such as environmental management, geographical information science, remote sensing and interactive digital multimedia. Imaging is at the cores of many scientific discoveries, with information captured in terms of raw pixel intensities and in multiple channels for color or hyperspectral imagery. The work includes generation of probabilistic measurements and quantified uncertainties from image analysis methods, pattern classification methods generating information that can be stored as probabilistic feature tables and new approaches to visualization of probabilistic information. The proposed work will be integrated within the UCSB BioImage Search and Query environment, part of the campus data infrastructure, and the software developed will be made available as open source.

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).

Recent advances in imaging have enabled multimodal/multiscale observations of complex natural systems. Annotating, harvesting, extracting, and correlating the information contained in these vast image volumes is critically dependent on new information-processing tools as well as robust workflow implementation of well-established tools. In cases such as bioimaging, image data comes from different physical samples from different specimens and needs to be statistically harmonized. Though piecewise computational workflows in data collection are often highly automated, little progress has been made in effective and efficient knowledge discovery. The lack of processing and discovery tools to navigate data of such complexity and magnitude is a critical bottleneck.

The project's computational efforts focus on a biological system that represents a unique combination of high complexity and accessibility for imaging: the vertebrate retina. The retina has a very complex yet highly structured architecture consisting of an unknown number of repeated neural circuits. Though it has been a focus of intense anatomical and physiological studies for over a century, no complete retinal map exists today. In fact, contrary to common misunderstanding, not even all of the retinal cell types have been discovered, much less mapped into functional circuitry. A retinal map is the critical anatomical ground truth that is needed in building realistic models of the earliest stage in visual processing. Building such a cell map requires advances in several areas, including imaging and molecular marker technologies, statistical pattern recognition, and databases. However, the critical barrier at this time is in analyzing the vast amount of images that will be generated from such a project, from samples coming from different retinal cross sections of different animals, and the need to integrate this information in a statistically robust manner to build a retinal map. It is expected that this project will advance not only the image-based information processing technologies but will also have a significant impact on neuroscience research.

The project is interdisciplinary and brings together researchers at the University of Utah and UCSB. Students on the project will get a broad training in retinal neurobiology, computer science and electrical engineering. This project will integrate research and education by introducing the results of the research into courses taught by the PIs on image processing, databases, bioinformatics, and pattern recognition.

A number of scientific endeavors generate data that can be modeled as graphs: high-throughput biological experiments on protein interactions, high throughput screening of chemical compounds, social networks, ecological networks and food-webs, database schemas and ontologies. Access and analysis of the resulting annotated and probabilistic graphs are crucial for advancing the state of scientific research, accurate modeling and analysis of existing systems, and engineering of new systems. This project aims to develop a set of scalable querying and mining tools for graph databases by integrating techniques from databases and data mining. The proposed research work is theoretical as well as empirical. New theoretical ideas and algorithms are being developed and these are being applied to the domains of Cheminformatics and Bioinformatics.

The first research thrust examines primitives for graph data management and graph mining. A declarative query language for graphs is being investigated. This language is based on a formal language for graphs and a graph algebra, and separates the concerns of specification and implementation. Scalability of techniques for similarity search on graphs and mining for significant patterns is being investigated as a part of this thrust.

The second research thrust applies the developed techniques to the domain of Cheminformatics. Specific tasks that are being examined are search for similar compounds, mining for significant motifs, diversity analysis, and analysis of macromolecular complexes.

The final research thrust applies the developed methods to the domain of Bioinformatics. There has been an explosion of data of widely diverse biological data types, arising from genome-wide characterization of transcriptional profiles, protein-protein interactions, genomic structure, genetic phenotype, gene interactions, gene expression, proteomics, and other techniques. Techniques being developed can integrate and analyze data from multiple sources and models efficiently, while accelerating (interaction and function) prediction, and pathway discovery.

Further information about the project can be found at the project web page http://www.cs.ucsb.edu/~dbl/0917149.php.

Many applications generate data that can be modeled as graphs: Biological networks, social networks, ecological networks and food-webs, among others. Traditional graph theory and most current research in graph modeling, querying, and mining concentrates on problems where the graph structure is inherently static and does not change with time. But networks in the real world are dynamic in nature with a wide range of temporal changes. While the topology of networks such as social networks and transportation networks undergoes gradual change (or evolution), the content (information flow, annotations) changes more rapidly.

Against this background, this project aims to develop a set of scalable querying and mining tools for dynamic graphs by integrating techniques from databases, data mining, and algorithms. The first research thrust examines inherent properties for characterizing dynamic graphs, specifically the dynamic reachability structure of nodes. It also investigates high-fidelity methods for generating dynamic graphs based on these properties. The second research thrust aims to develop summarization techniques for dynamic graph structures. These techniques can be used to compress large graph datasets, to make predictions about future values, and to query information cascades under partial observation. The third research thrust aims to develop techniques for mining significant dynamic subgraphs under different constraints of connectivity such as fixed subgraph structure, connected subgraphs, and smooth subgraphs. The goal is here to find anomalous patterns in dynamic graph datasets using a statistical characterization of background behavior. The final research thrust reconsiders the first three research thrusts from the point of view of content and topic models in order to understand the relationship between content of a message and its flow in a network. The developed methods will be evaluated using a number of real-world data sets including email datasets such as Enron, re-tweeting activity data sets on Twitter, Facebook wall posts, and transportation networks.

An important result of this work is a theoretically well-founded and empirically verifiable framework for modeling, querying and mining of dynamic graphs. Aspects of dynamic behavior in which both the structure of networks and their content (information flow, annotations, etc.) change will be considered. The study of such dynamic networks and how information flows through them is essential to developing a theory of dynamic networks and their evolution. This work helps answer questions such as power-law applies to dynamic behavior, whether content of a message can predict its flow and vice versa, whether anomalies in a dynamic network can be mined effectively by building either an empirical summary or a generative model. Robust open source tools based on the developed algorithms will be released for research, academic and non-profit endeavors. The research is expected to yield new techniques in graph algorithms, graph databases, and graph mining, and realize a collection of tools that can be used by scientists, and ultimately lead to a theory for dynamic graphs.

Broader Impacts: The proposed project will integrate research and education by introducing the results of the project into a graduate seminar, and a graduate course on information management. The project will support a postdoctoral researcher and train graduate students. The project offers enhanced opportunities for research-based training of graduate and undergraduate students, including members of under-represented groups e.g., females in Computer Science at the University of California at Santa Barbara. For high school students, the CNSI Apprentice Research Program at UCSB brings in high school students every summer. The open source implementations of algorithms resulting from this work will be freely disseminated to the community.

DESCRIPTION (provided by applicant): We propose an interdisciplinary effort linking computational and experimental methods to analyze and model two processes integral to C. elegans physiology: programmed cell death and the regulation of the germline stem cell proliferation decision boundary. The broad aims are to quantify phenotypic variation using image analysis and pattern recognition tools, to use the extracted features and gene expression data to develop a causal model for the regulatory processes, and to validate the model experimentally. The first aim is focused on data collection and the automated scoring of phenotypes in the form of high throughput image acquisition and processing. The scope of the phenotypic data encompasses recombinant progeny from two parental C. elegans strains. The complex regulatory processes under investigation involve cellular-level attributes that are typically assayed via microscopy. We propose pattern recognition algorithms to automate phenotypic scoring. The second aim proposes novel methodology to build integrative models over the joint genotypic, expression and phenotypic datasets. We discuss how the combined genomic data offer immense potential for learning causal models. We propose a learning framework based on a novel modular Bayesian network platform that effectively reduces noise and data complexity. We elaborate on the use of complex optimization techniques designed to avoid local optima in the model scoring procedure. The third aim involves using our models to direct experimentation in efforts to dissect the genetic bases underlying the phenotypes. The causal models provide an explanation of how genetic variations lead to phenotypic change by modulating gene expression. Thus, the causal models can be thought of as biological hypotheses, and promising experimental candidates can be inferred from the models. The proposed research will develop new techniques for synthesizing information from multiple data sources and will integrate these methods with experimental studies of genetic variation in a model research animal, C. elegans. The synergistic interplay of computational methods and experimental analyses will provide a paradigm for greatly accelerating biological discovery. The proposed research is transformative not only in the functionality that it offers to domain scientists but also in the innovative computational research that forms the basis for the work. PUBLIC HEALTH RELEVANCE: We will develop computational models for the analysis of complex biological regulatory processes using recent high-throughput biological data, including measurements of gene expression, parental genotype and physiological traits. Our models are designed to explain how various physiological traits change depending on the state of gene expression and parental genotype. The worm C. elegans offers a rich source of interesting physiological traits that are highly complex in terms of genetics. Therefore, these models will be useful for understanding complex diseases such as cancer.

This Integrative Graduate Education and Research Traineeship (IGERT) award provides Ph.D. students at the University of California at Santa Barbara with the skills to design more efficient and robust empirical networks based on their analyses of large data sets derived from existing networks. By training students to examine multiple types of networks, such as genetic, economic, and social networks, this program aims to advance the field of Network Science.

Intellectual Merit: This traineeship program is a collaboration among seven graduate departments (Computer Science, Communication, Ecology, Evolution & Marine Biology, Electrical & Computer Engineering, Geography, Mechanical Engineering, and Sociology), which will enable trainees to learn computational methods to engineer, control, measure, and predict the dynamics of large networks. Through the program?s Network Science Laboratory, trainees will participate in team-based modules and obtain hands-on experience with software, empirical data sets, and interdisciplinary science. Additionally, trainees will participate in weekly seminars, summer internships, workshops, and an innovation program focused on problem solving and creative thinking.

Broader Impacts: By providing students with interdisciplinary training in Network Science, this program will advance the emerging field of Network Science and will serve as a model for similar academic programs across the nation. Moreover, this program aims to recruit, retain, and mentor 70% women and underrepresented minority students from University of California at Santa Barbara undergraduates as well as students from four partner institutions: California State University at San Bernardino, California State University at Los Angeles, University of California at Merced, and University of New Mexico, all of which are Hispanic Serving Institutions.

IGERT is an NSF-wide program intended to meet the challenges of educating U.S. Ph.D. scientists and engineers with the interdisciplinary background, deep knowledge in a chosen discipline, and the technical, professional, and personal skills needed for the career demands of the future. The program is intended to establish new models for graduate education and training in a fertile environment for collaborative research that transcends traditional disciplinary boundaries, and to engage students in understanding the processes by which research is translated to innovations for societal benefit.

This project will develop novel methods for analyzing and modeling
heterogeneous dynamic networked data. Network data arises in a number of
application domains ranging from Internet of Things, cloud computing, software analysis,
neuroscience, biology, geography, to social sciences. Accordingly, network
analysis has emerged as a major paradigm for exploring complex processes
behind observed data. Compared to high dimensional data, analysis of network
data is more challenging due to interdependencies between entities, the
presence of attributes, and the natural evolution of networks over time. The
goal of the project will be to understand and model the heterogeneity of
behaviors in dynamic networks. The project will have a transformative impact
on big data problems that are enabled by a network-centric approach to
exploiting dynamic, heterogeneous data, such as brain networks. The project
will integrate research and education by introducing methods and results of the
project into courses and seminars, and train a diverse group of undergraduate
and graduate students.

The project's focus will be on heterogeneity in dynamic networks:
heterogeneity of node behaviors across network structure and time,
heterogeneity of the coupling of structure and attributes, and heterogeneity
across networks. Against this backdrop, the project will consider the basic
problems of clustering (partitioning), classification/regression, decomposition
of networks into its basis elements, and the problem of explaining global
network behaviors by small network fragments. These problems will be
considered for a single network and for multiple networks. Within a network,
heterogeneity is observed when nodes or clusters exhibit different behaviors,
for instance due to hidden or missing data. Across networks, heterogeneity is
observed in the diversity of subject populations or among network instances.
The first research thrust will apply spectral theory for partitioning attributed
and dynamic networks. The second research thrust will apply convex
optimization to find clusters while tolerating heterogeneity across network
structure and time. It will also develop methods for estimating graphical models
for multiple dynamic networks. The final research thrust will focus on the
discovery of succinct sub-networks that are predictive and that evolve
concurrently with the underlying networks.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Due to the societal and technological advances made possible by data-driven science, there is a strong demand for professionals versed in the tools and techniques needed for manipulating and understanding data. This project will develop an undergraduate curriculum in data science that spans and connects the three main public higher education systems in California: the research-driven University of California system, the practical and career-oriented California State University system, and the two-year California Community Colleges. The collaborative program will establish pathways for data science training through coursework and real-world projects. This project will impact students from diverse social, ethnic, cultural, and economic backgrounds and will improve the feeder pipelines from two-year colleges to four-year universities. This multi-campus approach to building a data science training program will foster collaborations for training a diverse workforce in data science. The resulting course materials and project outcomes will be made available so that other institutions can adopt best practices.

The partnership consists of four academic institutions on the West Coast: University of California, Santa Barbara (UCSB), California Polytechnic State University, San Luis Obispo (Cal Poly), Santa Barbara City College (SBCC), and California State University, San Bernardino (CSUSB). The alliance will expand training at UCSB and Cal Poly by building on existing strengths through a sequence of new capstone courses, as well as lay the groundwork for data science curriculum development at SBCC and CSUSB, whose students will participate in a summer internship program at UCSB. Over 100 undergraduate students will be supported by stipends during the course of the project. The developed courses will emphasize programming and data inference within the context of application domains that is critical to training in data science. Students will be taught the underlying principles of data science, including data-generating processes and the role of measurement, ethics and privacy, information-processing tools for harnessing the power of big data, and the oral and written communication skills necessary for pursuing effective professional careers in the field. The program will culminate in a year-long capstone course for seniors, who will synthesize and apply previously learned data science tools and techniques in a large-scale project in a chosen domain area.

NSF's Harnessing the Data Revolution Data Science Corps program focuses on building capacity for harnessing the data revolution at the local, state, national, and international levels to help unleash the power of data in the service of science and society. Projects in this program are being jointly funded by the NSF's Harnessing the Data Revolution Big Idea; the Directorate for Computer and Information Science and Engineering, Division of Information and Intelligent Systems; the Directorate for Education and Human Resources, Division of Undergraduate Education; the Directorate for Mathematical and Physical Sciences, Division of Mathematical Sciences; and the Directorate for Social, Behavioral and Economic Sciences, Office of Multidisciplinary Activities and Division of Behavioral and Cognitive Sciences.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.