RESEARCH PROJECTS






Math Search
(Status: Ongoing)

Project Web Page
Publications of this Project

This project focuses on the research and development of a novel, math-aware search systems. This involves the development and study of various related topics such as: indexing and retrieval of mathematical contents, relevance ranking of query hits, development and optimization of math-query processing, math-query relaxations for more effective math search, the generation and use of metadata in math search, equivalence detection in math search, special interfaces for math search systems, and a number of other related research issues. Math contents differ from general text because they involve mostly mathematical symbols (as opposed to textual words) that are inter-related in rich mathematical structures. Therefore, standard text indexing and retrieval techniques are not effective for math contents. In this project, a search system for mathematical contents has been developed for the National Institute of Standards and Technology. This system will be deployed as a major part of a multi-million dollar NIST Web digital library, called the Digital Library of Mathematical Functions (DLMF). DLMF is the Web counterpart of the all-time math bestseller "Handbook of Mathematical Functions" since the 1960s. A related direction of research that we started recently is the automated recognition of hand-written mathematical symbols and mathematical expressions for math search purposes.

Back to the Menu of Research Projects

Audio and image Search
(Status: Ongoing)

Publications of this Project

Content-based indexing of audio-visual data in multimedia databases is very critical for sophisticated search and retrieval. Example searches include "sound-like" and "look-like" search queries. Other more complex search types involve specifying semantically certain audio-visual features to be matched. This project is using some of the same techniques used in compression and data-fitting modeling to index audio-visual data for supporting sound-like and look-like searches. For feature-matching searches, the project will address a variety of feature extraction and selection techniques for domain-dependent indexing.

Back to the Menu of Research Projects

Image and Video Processing
(Status: Ongoing)

Publications of this Project

This research focuses on applying image/video processing techniques, such as pattern recognition and signal processing techniques, to solve specific problems in real-world applications.

One application is the computerized age-assessment of skeletal development of babies, children and young adults, using X-rays of the human hand. A mismatch of the skelettal age with the biological age indicates growth abnormalties, and thus serves as good diagnostic tool for a number of diseases. New pattern matching methods were developed to create algorithms for the assessment of the skeletal age of the patient.

Almost all the image processing problems carry over to video processing, but magnified by the larger data sizes and the new dimension of time and motion. In this project we have developed video segmentation techniques that will open the door to some sort of divide-&-conquer approach to many of the video processing problems. Some of the applications we are exploring are (2) video indexing for effective video retrieval, (2) video editing, and (3) video hyperlinking. Another area of focus is video pattern recognition.

Back to the Menu of Research Projects

Data Compression
(Status: Ongoing)

Publications of this Project

Current imaging and video applications, such as medical imaging, teleradiology, space imaging, multimedia, and video on demand, involve massive amounts of data which have pushed the storage and transmission technologies to their limits and beyond. One approach to deal with the massive amounts of data is data compression. This project is involved with all aspects of data compression, both lossless and lossy. In lossless compression, novel compression techniques are being developed and investigated; some techniques are domain dependent, while others are generic. In lossy compression, the project is focusing on wavelet compression of images/videos, novel quantization schemes, and motion detection/compensation. One important aspect of this project is the study of the interactions between compression, on the one hand, and watermarking, progressive transmission, error resilency, audio/visual data indexing, and a variety of image analysis/computer vision applications, on the other hand. Those interactions are themselves research projects of considerable scope; they are discussed seperately below.

Back to the Menu of Research Projects

Error Resiliency in Image/Video Storage and Transmission
(Status: Ongoing)

Publications of this Project

Error resiliency is the ability to tolerate data loss and uncorrectable errors with graceful quality degradation and without data retransmission. Several approaches can be applied to achieve error resiliency, such as (1) predicting the lost/uncorrectable data from the surrounding available data, and (2) transforming the data before storage/transmission and then applying differentiated error protection. The first approach works well in video transmission. The second approach is applicable to all natural signals: images, videos, and sound. Error resiliency affords us graceful quality degradation in that if certain data is unrecovered, a good- (albeit degraded-) quality reconstruction of the data is still possible. In this project we focus on developing and studying novel techniques of error resiliency for images, videos, and audio data.

Back to the Menu of Research Projects

Watermarking (Steganography)
(Status: Ongoing)

Publications of this Project

Watermarking refers to hiding some sort of signature within an image/video/sound datafile to establish traceable ownership of the data. This project addresses the development and analysis of watermarking techniques for audio, images, and video data. The techniques must meet certain criteria such as (1) nondestructability by various processes, (2) nondetectability, (3) minimum distortion, and/or (4) minimum overhead. We have already developed new music watermaking techniques with excellent robustness qualities. Other techniques are being explored for image and video watermarking.

Back to the Menu of Research Projects

Parallel Algorithms
(Status: Ongoing)

Publications of this Project

This is an ongoing project involved in designing parallel algorithms for problems in various application areas such as numerical computations, image processing, data compression, and so on. The parallel algorithms that have been developed in this project include



Back to the Menu of Research Projects

Interconnection Networks
(Status: Complete)

Publications of this Project

The PI did considerable research for several years in the area of interconnection networks, but now is pursuing other research interests. This section describes the highlights and accomplishments of that research.

The Banyan-Hypercube Networks

Network design is concerned with defining network structures that meet certain performance criteria under the constraints of a limited number of IO channels per processor (due to limited pin counts of IC chips) and a limited number of inter-processor communication links (due to cost considerations). The network performance criteria commonly held are routing speed, bandwidth, and richness of structure, i.e., ability to embed certain common communication patterns. Much of the research in this area has focused on finding high-performance network designs. The well-known hypercube has been shown to deliver high performance and has been implemented in several commercial parallel computers. However, the hypercube has two disadvantages: poor upward scalability and inability to embed certain important communication patterns. In addition, the communication speed of hypercubes could be improved upon. In this project we designed a new network, called the banyan-hypercube , and showed that it shares with the hypercube all the advantages of the latter, and that it is superior to the hypercube in communication speed, bandwidth, and ability to efficiently embed all the important communication patterns.

Cartesian Product Networks

In this project we have developed a general unified theory of networks, namely the theory of Cartesian product networks, which include many of the well-known networks such as multidimensional meshes/tori, hypercubes and banyan-hypercubes. In this theory, a general methodology of (1) network design, (2) network performance evaluation, (3) routing, (4) embedding, (5) partitioning, and (6) network fault tolerance is developed. This theory unifies many network concepts/techniques into one framework.

Routing

Routing, the most important function of networks, is concerned with scheduling and establishing routes between processors to communicate data during the execution of computational tasks. In this project many routing algorithms were designed and studied:

Fault tolerance

We have addressed fault tolerance in randomized routing on Clos and Benes networks. The fault model assumes multiple switch faults, where a faulty switch is considered to be stuck at some setting. We have shown that by a slight modification the randomized routing algorithms can tolerate switch faults. We have conducted a quantitative performance evaluation of the faulty network, using probabilistic analysis and simulation, and shown that the network performance is hardly affected by the presence of switch faults, mainly because of the resilience of randomized routing. In addition, we have shown that randomized routing on Clos/Benes networks can tolerate faults without fault diagnosis , that is, without knowing which switches are faulty and what their fault state is.

We have also developed a general fault-tolerant routing algorithm for Cartesian product networks as part of the general theory of product networks mentioned earlier. This algorithm applies particularly to meshes, tori, hypercubes, and banyan-hypercubes, where the fault model assumes multiple faulty processors and faulty links.

Embedding

Embedding is concerned with appropriately assigning the processes of a parallel task to the processors of a parallel system so that the communication overhead between the processors is minimized. We have constructed embeddings for linear arrays, meshes, trees, pyramids, and multiple pyramids on the banyan-hypercube network. These embeddings are better than the corresponding embeddings on any other existing network (e.g., meshes, tori, and hypercubes). This greatly enhances the significance of the banyan-hypercube networks. In addition, we have developed in our theory of Cartesian product networks a general methodology for constructing optimal embeddings for the aforementioned patterns on any Cartesian product network.

Network Partitioning

For parallel processors to be general-purpose systems, they must support multitasking and multi-users. Thus, parallel systems should be partitionable into independent subsystems where every subsystem has the same structure (scaled down) as the parent system. Accordingly, the interconnection network of the system should be partitionable into independent (i.e., nonoverlapping) subnetworks of the same structure as the parent network. In addition to network partitionability, multitasking requires a software system for network management (i.e., network resource allocation) akin to memory management in multiprogramming uniprocessors. The main components of this network management system are: (1) a strategy for subdividing the network into subnetworks and allocating unoccupied subnetworks of appropriate sizes to incoming tasks; (2) a strategy for merging freed subnetworks to form larger subnetworks; and (3) a system data structure that keeps track of which subnetworks are free and which are busy. We have developed a network management system for partitioning the banyan-hypercube and have shown that the banyan-hypercube experiences less fragmentation and delivers better multitasking performance than the widely used hypercubes and meshes. In addition, we developed a generic partitioning system for the Cartesian product networks. This generic partitioning system gives multitasking capabilities to any parallel system interconnected with a product network.

Properties of Multistage Networks

This project was largely my Ph.D dissertation. It focused primarily on the relationships between topology, functionality and routing control of multistage networks. I defined three important routing control schemes, classified networks according to these schemes, and characterized the topological structure of each network class. This characterization guides the network designer as to which network structure to use, given a desired routing control mechanism. The other important relationship studied was that between functionality and topology of networks. It was known that if two networks are topologically equivalent, then they must be functionally equivalent. My second contribution was to establish the challenging reverse relation: if two networks are functionally equivalent, they must be topologically equivalent. The insight gained from understanding the topology-control relationship and the topology-functionality relationship enabled me to address the relationships between all the various multistage networks that had been defined according to some widespread design paradigm. I showed that all these networks have the same routing control scheme, and concluded that they are topologically and functionally equivalent to one another. The implication was that no new network designed according to the aforementioned paradigm would bring any new functionality.

Back to the Menu of Research Projects

Parallel Processing and Computer Architecture
(Status: Complete)

Publications of this Project

The project involved the development of a novel approach to parallel processing based on parallel primitives and their stored processing requirements. A parallel primitive is a frequently used parallel computation that has clear processing requirements (e.g., number of processors, communication pattern, processing time, etc.). A parallel primitive is abstractly treated as an atomic instruction similar to instructions in uniprocessor systems. The advantage of parallel primitives is twofold. First, they allow users to write programs in terms of parallel primitives without requiring users to have parallel programming skills or to know the inner structure of the parallel computer. In other terms, the primitives provide a good abstraction of parallel machines. The second advantage is the extraction of high performance from parallel systems. This is accomplished by using a primitives table where the processing requirements of each primitive are stored. The operating system consults that table regularly to configure and manage the system according to the processing requirements of the primitives used in the running program and thus achieve efficient utilization of the system.

To take full advantage of the concept of parallel primitives and primitives table, we developed 3-layer system architecture. The top layer is a standard user interface and a compiler that recognizes the pre-defined parallel primitives. The middle layer is an intelligent operating system that relies heavily on the primitives table. The bottom layer is a standard operating system. The middle layer uses the primitives table to identify the best system configuration needed by a program. The bottom layer operating system, which has immediate access to the underlying parallel hardware, configures the system according to the instructions of the middle layer. This 3-layer architecture provides a portable, multitasking, general-purpose parallel system that offers the speed of parallel computers without requiring from the users the skills of parallel programming.

Another focus of the project was the scheduling of large applications on a heterogeneous suite of computers connected with a local area network, where the various tasks of the application require different computer resources, and the suite consists of uniprocessors, vector machines, SIMD machines, MIMD machines, and so on. The applications considered are abstracted by a variety of dependency graphs such as series-parallel graphs and trees, and the scheduling approaches cover several techniques such as divide-&-conquer, dynamic programming, and genetic algorithms.

Back to the Menu of Research Projects

Return to the Home Page