With the ever-expanding size of multimedia databases it is important to seek new technologies that improve the performance of systems that manage these databases. One such technology is holographic memory which has some very interesting attributes such as massive parallelism, high speed, and content searching. A volume holographic database system (VHDS) serves as a building block for a postulated terabyte electro-optical computer architecture (EOCA). Data mining and image management applications are considered for the EOCA. Using the associative processing capabilities of the holographic memory a number of queries can be completed in a matter of seconds for the entire terabyte database. These queries could take hours on sequential computers. However, the state of the art in holographic memory lags far behind electronic computing and thus considerably more research and development must be performed before these systems can realize their vast potential.

In this paper, we present the current state of the art in semantic data modeling of multimedia data. Semantic conceptualization can be performed at several levels of information granularity, leading to multilevel indexing and searching mechanisms. Various models at different levels of granularity are compared. At the finest level of granularity, multimedia data can be indexed based on image contents, such as identification of objects and faces. At a coarser level of granularity, indexing of multimedia data can be focused on events and episodes, which are higher level abstractions. In light of the above, we also examine modeling and indexing techniques of multimedia documents.

High-performance servers and high-speed networks will form the backbone of the infrastructure required for distributed multimedia information systems. A server for an interactive distributed multimedia system may require thousands of gigabytes of storage space and a high I/O bandwidth. In order to maximize the system utilization, and thus minimize the cost, it is essential that the load be balanced among each of the server's components, viz. the disks, the interconnection network and the scheduler. Many algorithms for maximizing retrieval capacity from the storage system have been proposed in the literature. This paper presents techniques for improving the server capacity by assigning media requests to the nodes of a server so as to balance the load on the interconnection network and the scheduling nodes. Five policies for request assignment-round-robin (RR), minimum link allocation (MLA), minimum contention allocation (MCA), weighted minimum link allocation (WMLA) and weighted minimum contention allocation (WMCA)-are developed. The performance of these policies on a server model developed by the authors (1995) is presented. We also consider the issue of file replication, and develop two schemes for storing the replicas: the parent group-based round-robin placement (PGBRRP) scheme, and the group-wide round-robin placement (GWRRP) scheme. The performance of the request assignment policies in the presence of file replication is presented.

The UPIO (user-controllable parallel I/O) proposed by the authors in 1996 allows users to determine a file's structure by considering the access patterns of particular applications and the distribution of data for parallel access, and them do I/O collectively. This enables users to produce high-performance external computation codes by planning I/O, computations, communication, and the reuse of data effectively in the codes. They show how well UPIO produces high performance external computation codes by designing I/O and memory-efficient external matrix multiplication algorithms and exploring the effects of UPIO with the codes.

One of the key components of a multiuser multimedia-on-demand system is the data server. Digitalization of traditionally analog data such as video and audio, and the feasibility of obtaining network bandwidths above the gigabit-per-second range, are two important advances that have made possible the realization, in the near future, of interactive distributed multimedia systems. Secondary-to-main memory I/O technology has not kept pace with advances in networking, main memory, and CPU processing power. Consequently, the performance of the server has a direct bearing on the overall performance of such a system. In this paper, we present a highperformance solution to the I/O retrieval problem in a distributed multimedia system. We develop a model for the architecture of a server for such a system. Parallelism of data retrieval is achieved by striping the data across multiple disks. We present the algorithms for server operation when servicing a constant number of streams, as well as the admission control policy for accepting requests for new streams. The performance of any server ultimately depends on the data access patterns. Two modifications of the basic retrieval algorithm are presented to exploit data access patterns in order to improve system throughput and response time. Finally, we present preliminary performance results of these algorithms on the IBM SP1 and Intel Paragon parallel computers.

The improvements in disk speeds have not kept up with improvements in processor and memory speeds. Conventional storage techniques, in the face of multimedia data, are inefficient and/or inadequate. Here, an efficient multimedia object allocation strategy is presented. We describe a multimedia object model, the object and storage device characteristics, and the fragmentation strategy. A bipartite graph approach is used for mapping fragments to storage devices and a cost function is used to determine an efficient allocation of an object and to balance the loads on the devices.>

The authors provide an overall assessment of the current state-of-the art in multimedia information technology, the future directions and the engineering challenges faced by the designers and researchers working in this area. They describe how the newly emerging networking and high performance storage technologies can provide unique opportunities for building interesting multimedia applications, which were unconceivable previously.>

A class of order-preserving dynamic hashing structures is introduced and analyzed. The access method is referred to as the dynamic random-sequential access method (DRSAM) and is derived from linear hashing. A new logical to physical mapping that is based on sequential bucket allocations in hash order is proposed. With respect to previous methods, this allocation technique has the following characteristics: (1) the structure captures the hashed order in consecutive storage areas so that order preserving (OPH) schemes should result in performance improvements for range queries and sequential processing; and (2) it adapts elastic buckets for the control of file growth. Under specific conditions, this approach outperforms the partial expansion method previously proposed by P.-A. Larson (1982).>

A novel class of order-preserving dynamic hashing structures is introduced and analyzed. The access method is referred to as dynamic random-sequential access method (DRSAM) and is derived from linear hashing. With respect to previous methods DRSAM presents the following characteristics: (1) the structure captures the hashed order in consecutive storage areas so that order-preserving schemes result in performance improvements for range queries and sequential processing; and (2) it adapts elastic buckets for the control of file growth. This approach outperforms the partial expansion method. The file structure is also extended with proper control mechanisms to cope with nonuniform distributions. The outcome is a multilevel trie stored as a two-level sequentially allocated file.>

In this paper we propose a full text search system based on optics. The storage and processing of the textual data are performed by an optical back-end system to an electronic computer. In this way we can take advantage of the speed and parallelism of digital optical processing. Using the proposed configuration we show how one might implement a set of text processing operations using lasers, spatial light modulators and photodetectors.

To maintain consistency in a distributed database environment, the transactions must be executed atomically. The standard algorithm for ensuring an atomic execution is called the distributed commit protocol. The two-phase commit protocol and its variations, the well-known protocols used for this purpose, are characterized by successive rounds of message exchange, among all the sites of the database, at the time a transaction enters into a completion phase. The performance of these protocols is given by a complexity measure that depends on the communication structure of the protocol. Given N sites, the worst-case complexity of a commit protocol is O(N/sup 2/). A communication structure called maximal binomial structure (MBS) is presented, for which the complexity of the protocol is O(N*log/sup 3/ N). A lower bound for this complexity is also given, which is O(N*log/sup 2/ N). Protocols using the MBS remain symmetric. A scheme for an arbitrary expansion of the MBS to allow communication among a large number of sites is proposed. For the expanded system, the protocol complexity is also shown to be O(N*log/sup 3/ N). These structures are shown to be superior to other known structures.>

Storage, interconnection, and processing are discussed. Various types of optical disks and page-oriented holographic memories are considered. It is shown that optical storage is advancing rapidly and holds the potential of hundreds of megabytes per second data rates from a single storage unit, which can provide many new opportunities for supercomputing. Module-to-module, board-to-board, and chip-to-chip interconnection and gate-to-gate communication are discussed. It is concluded that optical interconnection is, in many cases, superior to electronic interconnection and holds the key to the development of future electrooptic systems. Optical computing devices are discussed and various application areas where optical processing as well as storage and interconnection are expected to play a role in the future are considered. The authors believe that optical processing, while holding considerable promise, lags behind its electronic counterpart primarily due to the fact that digital optical device development is in its infancy. They predict near-term systems will be electrooptic, with each technology providing its strength to the problem at hand.>

The authors assess the possible impact of optics on database and knowledge base systems, focusing on storage, interconnection, and processing. Various types of optical disks and page-oriented holographic memories are discussed. In the interconnection section, data communication is discussed at a variety of levels. Under processing, applications involving optical content addressable memories, optical data/knowledge base machines, and optics applied to full text processing will be optoelectronic, with easy technology providing its strength to the problem under consideration. It is noted that optical interconnection is superior to electronic interconnection in many cases and that the rapid advance of optical storage holds the potential of hundreds of megabytes per second data rates from a single storage unit. It is noted that optical processing holds considerable promise but lags behind primarily because digital optical device development is in its infancy.>

Increased emphasis has been given to the solution of data base management and information retrieval problems through the use of new hardware architectures. These architectures have included front end/back end organizations, logic in memory, associative memory/array processors, special function architectures and computers developed solely for the handling of data. In this paper a brief overview of some of these architectures is given. The paper is concluded with the author's opinion as to progress in the field during the next ten years.

Recent announcements in the computer field concerning semiconductor technology have motivated interest in the area of data base management and computer architecture to develop data base machines (DBM). The variety of architectural options available for defining a DBM has initiated a research effort to develop a methodology to help design and evaluate these options. Selected subsets of a DBM can be designed and implemented in specialized architectures called special purpose function architectures(SPFA's). These SPFA's can perform data base management functions, in hardware, that are currently being done by software modules. As part of this research, a highly specialized environment is currently being studied in a joint research effort between Syracuse University and USAF/ RADC to integrate the tools necessary for designing and evaluating DBM architectures. This environment is called a Data Base Machine Design and Evaluation Facility. Tasks to perform a study of the DBMDEF are described in this paper.

Secondary indexes are often used in database management systems for secondary key retrieval. Although their use can improve retrieval time significantly, the cost of index maintenance and storage increases the overhead of the file processing application. The optimal set of indexed secondary keys for a particular application depends on a number of application dependent factors. In this paper a cost function is developed for the evaluation of candidate indexing choices and applied to the optimization of index selection. Factors accounted for include file size, the relative rates of retrieval and maintenance and the distribution of retrieval and maintenance over the candidate keys, index structure, and system charging rates. Among the results demonstrated are the increased effectiveness of secondary indexes for large files, the effect of the relative rates of retrieval and maintenance, the greater cost of allowing for arbitrarily formulated queries, and the impact on cost of the use of different index structures.

An associative approach to data management is developed, and a methodology for measuring the performance and effectiveness of this approach is provided. Mathematical models which quantitatively describe retrieval, storage requirements, updating, and flexibility are developed for both a class of current sequential systems and an associative system. Utilizing these models, a comparison is made between the two systems under certain assumptions so that for given classes of data management problems, one can determine which system is more favorable.