Department of 
Computer Science

Search our Site



Research Project Index

Faculty Research Areas Index

  Research Area Descriptions

The Department of Computer Science is actively engaged in research on a broad range of topics. Follwing are descriptions of the principal areas of computer science in which our graduate faculty members conduct research.

Algorithms and Complexity Theory
Computation can be studied both experimentally, by building prototype systems, and mathematically, by investigating the capabilities and limits of the mathematical abstractions of algorithms and the problems that they are asked to solve. Research in algorithms and complexity theory tends to take the mathematical approach, even when problems are motivated by practical applications or when implementations and experimentation are used to test the capabilities and limits of mathematical abstractions. Projects in this area range from algorithms for geometric computation to scheduling in real-time systems.

See also: Computer Graphics, Image Analysis and Computer Vision; Real-Time Systems

Assistive Technology

Bioinformatics and Computational Biology
Bioinformatics is concerned with the interpretation and analysis of the large quantities of data being generated by biological experiments. These data include the genetic sequence (genome) of various species, the expression of proteins under the direction of the genome in response to a variety of experimental conditions, and the observed incidence of\ disease in a group of individuals, to name just a few examples. From a computer science point of view, this analysis requires the development of new algorithms for data mining, statistics, and modeling, all of which must operate in the presence of noisy or incomplete data.

Computational Biology is concerned with elucidation of a protein's 3-dimensional structure and its relation to the protein's function. It combines insights from biochemistry with techniques in geometric modelling and computation, as well as computational methods for the simulation of a protein's dynamic behavior based on molecular and quantum mechanical models.

See also: Databases and Data Mining; Geometric Modeling and Computation; Parallel Computing

Computer Architectures
The study of computer architectures is concerned with the selection of the internal components of a computer and the design of their arrangement and connectivity. The key to understanding any computer architecture lies in the way trade-offs are made to optimize certain characteristics at the expense of others, subject to budgetary and physical constraints. Computer architectures are often optimized to solve particular kinds of problems, such as rendering computer graphics images, signal analysis, or string comparison. Much current work in this area involves the design of parallel computer systems optimized for particular kinds of problems.

See also: Computer Graphics, Image Analysis and Computer Vision; Hardware Systems and Design; Parallel Computing

Computer Graphics, Image Analysis and Computer Vision
Computer graphics systems produce the images that are the visual interface between people and computers. Our research concerns interactive graphics where the main challenges are the rapid generation of high-quality images in response to user inputs and the development of mechanisms for human interaction with the graphics system. We provide users with convincing, interactive, often immersive experiences with 3D data sets. We work in all the technologies required for these synthetic environments: image-generation hardware, display devices, tracking, model acquisition and management, image-generation algorithms, and interaction techniques, including haptic devices.

Image-analysis systems measure properties of image objects or prepare image data for presentation by a graphics system. Our research focuses on the rapid and accurate identification and measurement of objects in 2D and 3D medical images (organs, blood vessels, tumors), combining and presenting information obtained from different imaging modalities, and matching images to models or atlases of the structures we expect to find in the images.

See also: Computer Architectures; Geometric Modeling and Computation

Computer-Supported Cooperative Work
The design of computer applications and systems has traditionally assumed that a single user interacts with a computer program at any one time. The field of computer-supported cooperative work (CSCW) addresses the design, implementation, and use of programs that allow distributed users--people working together from separate locations--to collaborate with each other on a common task such as creating and editing a document or developing a program. To enable multiple, distributed users to communicate simultaneously with a program requires the rethinking of basic concepts in operating and distributed systems, programming environments, user-interface frameworks, software engineering, and transaction models. Thus, research in CSCW tends to extend and to integrate concepts from diverse subfields of computer science and from other disciplines such as social science and psychology. Research in CSCW at UNC-Chapel Hill includes augmenting existing software systems such as World Wide Web servers and browsers for supporting collaborative work; supporting real-time communications for interpersonal, multimedia communications; composing shared virtual environments for collaboration in immersive virtual worlds; and designing a common software framework for collaborative applications.

See also: Distributed Systems; Multimedia Systems; Networking; Real-Time Systems

Databases and Data Mining

Distributed Systems
Distributed systems research concerns the design and implementation of computer system services on groups of computers that communicate by exchanging messages across an internetwork. Examples of such services include file services, remote computation services, information retrieval services, and communication services such as electronic mail. Research in this area considers the trade-offs between the features of a service and its performance and cost on issues such as: (1) consistency of performance regardless of where the computation supporting a service is located, (2) the viability of the service as the number of computers or the physical span of the distributed system grows, and (3) the system's ability to maintain reliable service in spite of the failure of some of its components. At UNC-Chapel Hill, research ranges from theoretical investigations of distributed algorithms for process coordination and synchronization to system building efforts involving the construction of a next-generation Web server, hypermedia file systems, and network communication protocols for real-time, multimedia-based communications.

See also: Computer-Supported Cooperative Work; Hypertext; Networking; Parallel Computing; Real-Time Systems

Geometric Modeling and Computation
Geometric modeling is concerned with representing and manipulating objects in preparation for graphical rendering, manufacturing, computer-aided design, or physical simulation. Objects can be represented by their boundaries or by construction from simpler shapes. Finite-element analysis can be used to represent physical properties of objects (mass, density, rigidity, flexibility). Geometric models are sometimes created at multiple resolutions to support interactive graphics, efficient network transmission, or rapid object manipulation.

Computational geometry provides algorithmic foundations and analytic tools for solving geometric problems encountered in many fields of science and engineering. Problems include computing convex hulls, locating intersections of 3D objects, efficiently fitting a surface with triangular patches, locating exactly the point on an object having a particular property (e.g., highest, frontmost, closest to a given point or object in space), proximity problems, detecting collisions between objects, and approximating smooth surfaces. We study both the theoretical computational complexity of these problems and the techniques for efficiently and robustly computing their solutions, exactly or approximately.

See also: Computer Graphics, Image Analysis and Computer Vision

Hardware Systems and Design
Electronic digital computers are the main but not the only technology for information processing. Information occurs in many forms, most of which are not digital and often not even electrical. Correspondingly, many applications require systems that include rather disparate technologies in addition to computers and software. Therefore, we adopt an unusually broad doctrine of information-processing systems in which the needs of an application define the technologies needed for system design. This doctrine is embodied for example in the HiBall Tracker which comprises infrared optics, LEDs, photo detectors, analog circuits, A-to-D conversion, digital circuits, communications protocols, a synchronizing control processor, I/O driver, host PC, the SCAAT algorithm, and system and application software. Another example is the 3D Force Microscope which comprises a similarly rich mix of technologies and disciplines. Moreover, when the computational performance needs of a system cannot be met by software on general-purpose machines, it may become necessary to reconsider the computing hardware itself. Customized hardware systems can offer dramatic performance improvements. Examples of such hardware built here are the Pixel-Planes, PixelFlow, and BioSCAN systems. This research doctrine is also incorporated in parts of our hardware systems curriculum.

See also: Computer Architectures; Computer Graphics, Image Analysis and Computer Vision

Human-Machine Interaction
Humans have marvelous capabilities for pattern recognition and strategic judgment that computers cannot equal. Computers have marvelous capabilities for data transmission and manipulation and huge, exact data storage that humans cannot equal. Powerful systems for solving difficult problems can arise from combining the capabilities of human operators and computer systems. Research in human-machine interaction aims to devise hardware input and output devices, including new kinds of sensors and displays, communication protocols, interaction idioms, data manipulation algorithms, display and visualization formats, and monitoring and evaluation methods. These developments aim to make the combined human-computer system a more effective problem-solver by providing: (1) information most effectively to the sensory apparatus of the human operator, (2) natural, and thus easily remembered and reliably performed, interaction sequences for the human operator, and (3) fast, effective guidance for the computations performed by the computer system. This research area permeates the work of the two largest laboratories in our department; the Graphics and Image Lab and the Collaboratory.

See also: Computer Graphics, Image Analysis and Computer Vision; Computer-Supported Cooperative Work; Distributed Systems

Hypertext refers to a network of linked, computer-based documents that allows a user to select a highlighted region called an anchor to obtain another document. This second document may consist of text, audio, or video and may contain further links. When the user selects a link, the referenced document is retrieved (often via the Internet from a remote computer system) and is displayed on the user's screen by a program called a browser. The World Wide Web is a well-known example of a hypertext. Netscape Navigator and Microsoft Internet Explorer are examples of browser programs. Research in hypertext includes studies of how to organize information, how to handle requests for hypertext documents rapidly and reliably, how to maintain hypertexts, how to monitor usage of a hypertext, and how to enhance the current hypertext protocols to support more kinds of documents, such as documents containing mathematical notations.

See also: Computer-Supported Cooperative Work; Distributed Systems

Mobile Computing

The Monte Carlo Method
Many problems are so large or complex that solving them completely by any of the standard methods would require much more computing time than is available. If we relax the demand to solve the problem exactly, however, it is sometimes possible to obtain a solution that is within a few percent of the optimal or correct solution after a reasonably small amount of computation. Stochastic algorithms often obtain such rapid but approximate solutions using a directed random search. One particularly useful stochastic algorithm is the Monte Carlo method. Instead of trying to solve for the answer directly, this method sets up a random process whose mean is the correct answer to the problem. By running such (possibly sequentially improving) processes many times, better and better estimates of the correct answer to the original problem are obtained. Research in this area is concerned with how to formulate efficient stochastic variants of the original problem, how to generate instances of the random process quickly, and how to measure how well the Monte Carlo process has approximated the correct answer. An associated field is the study of the fast, algorithmic generation of "random" (pseudo-random, quasi-random) samples for such Monte Carlo computations.

Multimedia Systems
Computers and networks can manipulate data representing text, graphics, images, audio, video, and even more exotic media. Each form of data demands different capabilities of the computer systems and networks through which it passes, including high throughput, reliable transmission rate, easy manipulation, high reliability, and fast update. Satisfying these diverse requirements is a difficult challenge both for the computer systems at the transmission ends as well as for the software controlling the Internet. Our Multimedia Systems research is concerned with how to use processing power at the sending and receiving ends to decrease, or at least to even out, the demands on the network so that the real-time data stream can be presented faithfully to the receiver. Other aspects of this research include how data in different media can be abstractly organized and seamlessly integrated to present unified multimedia documents and visualizations; how static concepts such as hyperlinks can be done in dynamic media like video; and how media can be manipulated to disambiguate the actions of different users in a collaborative environment. In addition, this research helps to define the capacity and features that will be needed in the next generation of the Internet.

See also: Computer-Supported Cooperative Work; Networking; Real-Time Systems

The current implementation of the Internet was not designed to handle the kinds of multimedia traffic that people want to send across it. Audio and video transmission make different demands on the network than more traditional e-mail or Web pages. What is needed are mechanisms in the software systems controlling the Internet to allocate the network's capacity for different uses and to guarantee a suitable level of service to data streams that have real-time requirements. Without such service level guarantees, real-time audio or video transmissions are subject to unpredictable interruptions and dropouts due to network congestion. Research in networking technology aims to modify the hardware and software systems that operate the Internet to increase capacity and to allow for quality-of-service guarantees that support multimedia communications.

See also: Computer-Supported Cooperative Work; Multimedia Systems; Real-Time Systems

Parallel Computing
Parallel computing is concerned with the development and programming of computer systems containing multiple processors. The objective is to create systems that can achieve performance far greater than any single-processor computer system. Maximum performance requires the use of new algorithmic, analytical, and system implementation techniques in ways that are specific to each parallel computer architecture.

See also: Computer Architectures; Distributed Systems; Programming Language Design and Implementation

Programming Language Design and Implementation
In the study of programming languages we are concerned with features that allow us to express complex programs reliably. For example:

  • Data-parallel constructs can be used to describe repeated computations in a succinct fashion and also provide opportunities for high-performance implementation.
  • Object-oriented features of programming languages, such as Java and C++, can be used to describe, extend, and reuse recurring design patterns.
  • Declarative programming languages, such as Prolog, can be used to describe complex symbolic computations, such as theorem provers.
A clear understanding of programming languages is also required to create programs that process other programs. In the construction of collaborative systems, for example, it is important to identify domain-specific design patterns involving components of these systems, and to automatically generate or modify some of these components.

At UNC-Chapel Hill, research in programming language implementation centers on high-performance execution, which is required for many scientific and real-time problems. Achieving high-performance execution is complicated by the increasing divergence between the high-level features of programming languages and the low-level performance-oriented features of modern computer architectures, such as multiple functional units and multi-level caches. Our research targets efficient parallel execution and effective use of the memory hierarchy, using techniques applied at compile time and in execution.

See also: Computer Architectures; Computer-Supported Cooperative Work; Distributed Systems; Parallel Computing; Software Engineering and Environments; Theorem Proving and Term Rewriting

Real-Time Systems
Real-time systems are a class of computer systems that interact with the real world in a time frame that is defined by processes in the external environment. A typical real-time system is one that must obtain an input from an external device such as a sensor and generate an output in a bounded amount of time. This output must be provided on time, regardless of other activities contending for the processing resources of the system. Real-time systems research studies the mathematical problem of allocating computer system resources such as processing capacity, memory space, and network bandwidth so that the competing demands of multiple, simultaneously-executing applications can be met. Based on this theory, UNC-Chapel Hill researchers are building real-time operating systems, databases, and communication protocols, and are demonstrating how these systems can be used to solve problems in collaborative computing, multimedia communications, and distributed virtual environments.

See also: Computer-Supported Cooperative Work; Multimedia Systems

Software Engineering and Environments
Software engineering is concerned with the creation of programming system products that meet client specifications as well as physical, regulatory, budgetary, and other constraints. Software engineering environments are software systems that help software engineers to document and communicate their system's architecture and current status; develop their products, including code and documentation, test suites, and demonstration versions; manage the whole endeavor with schedules, plans, progress reports, critical path charts, deadlines, milestones, and version control features; and to evaluate the products via testing and coverage tools, notations for proving correctness of components, and programming language features that support construction of new components from existing components.

See also: Programming Language Design and Implementation

Theorem Proving and Term Rewriting
In many artificial intelligence systems, the facts that the system knows about the world are represented as assertions, declarative statements about objects or relationships among objects, and rules of inference--procedures that describe how to derive correct new statements from known statements. When the system needs to determine the validity of some assertion that is not explicitly stored in its knowledge base, the system treats the assertion as a theorem to be proved from the known facts using the rules of inference. Theorem proving, then, is the mechanism by which such a system reasons. Term rewriting systems are a particular implementation of such a system in which all of the knowledge relevant to a problem is stored as a set of equations. Theorems are proved by replacement of equal expressions and by unification to attempt to reduce the assertion to a trivial true statement. If this reduction can be completed, the assertion is accepted as true; otherwise it may be false, or it may require a more complete description of the world to determine its validity. Research in this area involves the development of efficient theorem-proving strategies, methods for analyzing the complexity of theorem provers, methods for incorporating semantics in theorem provers, methods for implementing theorem proving efficiently, and applications of theorem provers.

See also: Programming Language Design and Implementation

Horizontal Line
Department of Computer Science
Campus Box 3175, Sitterson Hall
College of Arts & Sciences
The University of North Carolina at Chapel Hill
Chapel Hill, NC 27599-3175 USA
Phone: (919) 962-1700
Fax: (919) 962-1799
Content Manager:
Server Manager:
Last Content Review: 11 April 2003