Research Areas

Algorithms, Logic, and Complexity

The goal of pragmatic computer science is to develop systems that fully exploit the capabilities of current computer technology. The goal of theoretical computer science is to understand the underlying principles of information processing, principles that are invariant with respect to technological change. Some of the areas we are investigating are described below.

Analysis of Algorithms

An algorithm with exponential asymptotic running time is of limited practical value regardless of future advances in hardware technology. Members of the faculty are searching for efficient, practical algorithms to solve problems in coding, scheduling, logic, computational geometry, information retrieval, and programming-language optimization. We are also studying the approximation properties of NP optimization problems and developing methods for establishing both positive and negative approximation results for such problems.

Parallel Computation

Recent advances in VLSI have made it possible to use multiple processors to tackle a single problem. Efficient algorithms for a parallel system have characteristics far different from traditional sequential algorithms. Furthermore, some problems appear to be inherently sequential, in the sense that no parallel algorithm can significantly reduce the computation time needed to solve them. Our research has concentrated on distinguishing inherently sequential problems from those that can be solved quickly with parallel algorithms and on designing efficient parallel algorithms, particularly for scheduling and graph problems.

Distributed Computation

In distributed systems, the processors are loosely coupled and interact via messages sent through a communication network. The complexity of a problem on a distributed system is measured by the minimum number of messages that need to be sent to solve the problem. We investigate how the topology of the network and the knowledge available to individual processors affects the computational efficiency of a system of distributed processors and what functions can be computed in a network where the processors are anonymous.

Computational Learning Theory

Work in computational learning theory considers the problem of predicting the value of an unknown function on a given input, based on the values of the function on previously observed inputs. Learning algorithms have been developed for several useful types of functions, including functions defined by decision trees, finite automata, artificial neural networks, Boolean expressions, and formulas in first-order logic. We investigate the performance of learning algorithms and study trade-offs between learning accuracy and computational efficiency. We have identified classes of functions that have efficient learning algorithms with good predictive performance and in some cases have developed probably optimal learning algorithms. These results have applications in the areas of artificial intelligence and software engineering.

Logic in Computer Science

Logic-based languages provide a programming environment that is specification oriented, rather than procedure oriented. Theoretical study of such languages is an active and growing research area. We are studying semantic issues for logic programming, deductive database systems, and fixpoint logics. A central research direction in this area is the comparative study and classification of logic-based languages according to their expressive power, which is defined informally as the ability of one language to express concepts or answer queries that another language cannot capture. At the same time, we are interested in investigating the connections between computational complexity and expressibility in various logical formalisms, as well as analyzing the computational complexity of query answering under various semantics. Our research also addresses the important issues of parallelizability and optimization in logical query languages.

Computer Graphics, Animation, and Scientific Visualization

We are actively engaged in research on scientific visualization, computer animation, and computer-aided geometric design. Vision provides one of the richest methods of communication, both in ordinary life and in the solution of scientific problems. Although the human visual channel permits communication of great quantities of data, comprehension of information is highly dependent on its quality. Computer scientists and engineers can contribute to effective information comprehension by developing methods for increasing the quantity and quality of visual communication. Furthermore, computer graphics can provide images in which time and space are compressed or expanded, images that are mathematical models of real as well as unseen worlds. These images can be quickly and inexpensively manipulated and can replace objects and scenes that would be costly or impossible to construct. Members of the faculty are working in the following areas pertaining to visual communication.

Scientific Visualization

At UCSC, research on Scientific Visualization focus on novel visualization techniques, efficient data structures and algorithms for handling large datasets, multi-modal presentation of data incorporating sound and haptics to enrich and complement the visual presentation, shared virtual workspaces in a collaborative environment to accommodate remote participants, and incorporating uncertainty information for a more credible visualization. Some of these research are showcased in the Advanced Visualization and Interactive Systems (AVIS) .

Computer Animation

Research in computer animation centers around modeling and moving articulated characters such as humans and animals. The modeling paradigm is anatomically based: animals have underlying bone, muscles and tissue. Skin is an elastic membrane that can be modeled with radial basis functions. Motion is extracted from monocular video using a combination of techniques from computer vision and computer graphics. A long term goal is the development of a movement library that encodes motion for reuse is different environments and with different characters. Animal Modeling and Animation.

Computer Aided Geometric Design

Current work at Santa Cruz includes design of freeform surfaces using parametric and implicit surface patches, which meet with tangent or curvature continuity. Typical freeform surfaces include car bodies, ships' hulls, and mechanical objects, including prostheses for total hip replacement surgery. Design of algorithms for converting between parametric and implicit representation for surfaces, such as Bezier representation, multinomial representation, Lagrangian representation, and Newtonian representation, is also an active area of research. The techniques are then utilized to solve problems in scattered data interpolation, the construction of blending surfaces, and fluid flow visualization.

Computer Security and Privacy

Current research interests at Santa Cruz include the logic of authentication and its application to computer and network security, as well as secure file systems.

Computer Systems

The ever-increasing demand for faster, more powerful computer systems requires the coordinated development of many interdependent technologies. Modern computer systems, with their parallel and distributed components, cannot be designed or used effectively without full consideration of hardware, software, and their combination. Several research projects at UCSC are addressing issues of fundamental significance to the development of future computer systems.

Storage Systems

Research into improving the performance and usability of storage systems is a major research area in the computer science department. Our research in storage fits broadly into several categories: improving the performance of existing storage systems using caching, prediction, and other techniques; investigating the use of next-generation storage devices; and building high-performance scalable storage systems. This research is done under the umbrella of the Storage Systems Research Center, one of the leading academic storage research centers in the country.

We are improving the performance of existing storage systems using prediction and caching techniques, often in collaboration with the machine learning group. We have applied prediction to areas in storage ranging from disk drive spindown for mobile computers to file prefetching and caching. In addition to our work with prediction, we are currently exploring the use of adaptive algorithms to better select caching algorithms in both conventional storage systems and storage embedded in network nodes.

Distributed Systems

We developed a system for real-time scientific data acquisition and management called REINAS (Real-Time Environmental Information Network and Analysis System). It is a research and development program with the goal of designing, developing, and testing an operational prototype system for real-time sensor control, data acquisition, distributed data management, and visualization. The project is a multiyear effort of the Baskin Center, in cooperation with the Naval Postgraduate School, the Monterey Bay Aquarium Research Institute, and the Center for Ocean Analysis and Prediction.

We are investigating the problem of providing global-scale distributed services. Many wide-area distributed applications, including distributed databases, can be implemented using a group communication mechanism. We have developed a family of weak-consistency group communication mechanisms, based on the timestamped anti-entropy communication protocol, that provide the scalability and fault tolerance needed by wide-area systems. Weak consistency seems to be the only viable mechanism that can be used to construct global-scale distributed applications.

We are also investigating a distributed storage system for multimedia. Support for integrated access to continuous media such as digital audio and video is difficult for current computing systems, as they lack the necessary capacity to provide data at a sufficient rate and do not support the necessary end-to-end performance guarantees. We have developed a scalable architecture capable of exploiting current and future technologies by connecting many storage devices in parallel using high-performance communication networks. It provides the end-to-end performance guarantees necessary for continuous multimedia through negotiations with the scheduler of each component. Its distributed nature allows resource sharing according to the needs of its clients and, through the use of redundancy, provides a high degree of fault tolerance.

Related Research

Professors Garcia-Luna-Aceves, Obraczka, and Varma in the Computer Engineering Department have a strong focus on research in advanced computer networks.

Computer Vision, Multimedia, and Image Processing

Sensor Vision and Image Processing

We are utilizing a variety of sensors including GPS (Global Positioning System), orientation trackers, inertial sensors, cameras, camcorders, stereo cameras, and LiDARS to acquire real-time data. Image processing routines are being developed to create consistent robust 4D models and register these models geo-spatially. For more information, visit Geo-Spatial Visualization Lab.

Geo-Spatial Vision and Visualization

We are creating GIS (Geographic Information System) by bringing together several layers of information including terrain data, street maps, buildings, environment data, aerial images, and mobile objects data. Some of the information will be collected by mobile agents (both humans and robots) roaming in the environment. Images and data are segmented to identify and classify objects. Motion is segmented from videos to identify moving objects and their patterns of activity. View planning is being performed to decide which sensor to use to acquire new data. Intelligent on-line algorithms are being utilized to track mobile objects. An important step is to extract time-critical information and present it to the user in a hierarchical uncluttered way. Mobile agents will be able to interact with the database in a multi-modal manner using vision, text, graphics, annotations, speech, sound, gesture, and haptics. A 4-dimensional space-time visualization of geospatial data and intelligence associated with the environment is being created. Support for fusing data and information, quantifying and visualizing uncertainty will be provided for decision-making. For more information, visit Geo-Spatial Visualization Lab.

Delivering Mobile Augmented Reality Content

Smart phones are ubiquitous and pack a lot of computing power and come with a rich array of sensors. We are interested in projects that utilize such mobile platforms to deliver valuable content. Sample projects include real-time robust detection and visualization of rip currents from handheld video stream, human body pose estimation for presenting overlaid 3D rendering of anatomical parts, and a platform for quickly developing mobile apps that integrate AR capability.

Image Processing, Storage, Retrieval, and Transmission

Many images are captured by sensing devices and are represented in the form of a rectangular array of picture elements in which each picture element may be comprised of a large number of bits. The resulting image consumes a considerable amount of storage space and communications bandwidth. We are studying ways to represent such images in more compact forms, either by eliminating some of the information deemed less important (lossy compression) or by eliminating statistical redundancies (lossless compression). With the assistance of adaptive and effective coding techniques such as arithmetic coding, we are exploring cost-effective data models for compressing classes of images. We are also studying hardware-software implementation trade-offs and the place of special-purpose hardware within an image-processing system.

Database Systems

The database systems group is working on research on tracking data throughout its lifetime, including the areas of data provenance, annotations, and archiving. The group also does research in data integration, scientific databases, and database query languages. Combinatorial optimization of database problems is another area of interest.

Machine Learning and Artificial Intelligence

Machine learning (ML) and Artificial intelligence (AI) address the challenging task of developing systems whose behavior may be learned by machines and termed intelligent. AI techniques have been applied to problem domains including natural language processing, robotics, expert systems, automatic programming, combinatorial problem solving, perceptual problems, computer vision, image processing, and geo-spatial visualization. Despite the diverse nature of these domains, they all benefit from AI methodologies developed for knowledge representation, efficient search, deduction, and learning. The following areas in artificial intelligence are the current focus of faculty research.

Machine Learning

One of the most challenging problems of AI is to build systems that modify their own behavior in response to their environment, gradually adapting to meet the specifications. Systems have been built that automatically acquire and refine classification rules for problems in domains such as medicine, chemistry, agriculture, and circuit design, and that automatically generate complex input-to-output mappings required for domains such as speech synthesis, signal processing, and visual feature extraction. We are working on the classification, analysis, and further development of the learning algorithms that make such adaptive software possible.

Our current experimental work includes investigations of a variety of connectionist learning algorithms and statistical learning methods, as well as learning algorithms that produce decision trees, finite automata, hidden Markov models, and logical formulas. This work has concentrated on algorithms that automatically discover new features in the data that are relevant for classification. Our theoretical work focuses on probabilistic analysis of the number of training examples and the computation time needed by various machine-learning algorithms. We have developed a number of new learning algorithms, including on-line learning algorithms whose performance is provably close to the best off-line algorithm.

We are also actively working in the area of applying machine learning algorithms for geo-spatial tracking of mobile objects, and object and pattern activity identification in sensor vision, and visualization applications. For more information, please visit Geo-Spatial Visualization Lab.

Neural Networks

Work in artificial neural networks represents an important direction in AI. At UCSC we are interested in artificial neural network models for applications in pattern recognition (including speech recognition and vision), signal processing, forecasting, and control. Our neural network group includes both CS faculty interested in the learning aspects of neural networks and CE faculty interested in digital and analog VLSI implementations of neural networks. Current projects range from building a VLSI implementation of a feedforward neural network with on-chip learning to software simulations of a neural net driving an arm to reach for objects in space. In addition to simulations, we have done extensive analytical work to quantify the rates of learning and generalization in artificial neural networks and to put the theory of learning in neural networks on a solid statistical foundation. Finally, we are developing several new neural network architectures and learning algorithms.

Pattern Recognition and Retrieval

Another area in which a system can learn to improve its performance is in database retrieval. We are building a representation-independent self-organizing retrieval system. This system automatically develops its own taxonomy for the items in its database and takes advantage of this taxonomy to improve retrieval efficiency. It also uses sophisticated heuristic search methods that have been a focus of research at UCSC. Its database is designed for domains in which the objects to be stored and retrieved are complex patterns like graphs, molecules, or images. An important feature of the system is that it is not tied to any particular representation for the patterns. Its application domains include organic chemistry, radio astronomy, computer chess, language understanding, and text retrieval.

Natural Language Processing

Programming Languages

Research in this area is concerned with the design and analysis of programming languages. This research includes investigations of core topics, such as type systems, and also deals with applications in software engineering and security. It combines theory (often based on methods from logic) and experimental work (often overlapping with software engineering). See also the Software and Languages Research Group.

Software, Web, and Internet Engineering

Our research focuses on developing tools and techniques for improving the quality and evolution of large software systems. Research on model checking of software components and their composition promises advances in analysis of systems at an architectural level. Object-oriented design and design patterns research improves our ability to represent and reason about software during the design phase. Projects focused on pair programming in the classroom, literate programming technology, and software configuration management repositories aim for improvements in the activity and control of software coding. Research on object-oriented methodology using contemporary languages such as C++, Java, and C# yields improved understanding of how to represent complex problems in software. Static analysis and verification research leads to improved understanding of software instabilities within large evolving systems, as well as improved quality in new and existing software.