Supporting efficient multimedia database exploration

Due to the fuzziness of query specification and media matching, multimedia retrieval is conducted by way of exploration. It is essential to provide feedback so that users can visualize query reformulation alternatives and database content distribution. Since media matching is an expensive task, another issue is how to efficiently support exploration so that the system is not overloaded by perpetual query reformulation. In this paper, we present a uniform framework to represent statistical information of both semantics and visual metadata for images in the databases. We propose the concept of query verification, which evaluates queries using statistics, and provides users with feedback, including the strictness and reformulation alternatives of each query condition as well as estimated numbers of matches. With query verification, the system increases the efficiency of the multimedia database exploration for both users and the system. Such statistical information is also utilized to support progressive query processing and query relaxation. Received: 9 June 1998/ Accepted: 21 July 2000 Published online: 4 May 2001     

The GMAP: a versatile tool for physical data independence

Physical data independence is touted as a central feature of modern database systems. It allows users to frame queries in terms of the logical structure of the data, letting a query processor automatically translate them into optimal plans that access physical storage structures. Both relational and object-oriented systems, however, force users to frame their queries in terms of a logical schema that is directly tied to physical structures. We present an approach that eliminates this dependence. All storage structures are defined in a declarative language based on relational algebra as functions of a logical schema. We present an algorithm, integrated with a conventional query optimizer, that translates queries over this logical schema into plans that access the storage structures. We also show how to compile update requests into plans that update all relevant storage structures consistently and optimally. Finally, we report on experiments with a prototype implementation of our approach that demonstrate how it allows storage structures to be tuned to the expected or observed workload to achieve significantly better performance than is possible with conventional techniques. Edited by Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received September 15, 1994 / Accepted September 1, 1995     

MING-I: a distributed interactive multimedia document development mechanism

The next generation of interactive multimedia documents can contain both static media, e.g., text, graph, image, and continuous media, e.g., audio and video, and can provide user interactions in distributed environments. However, the temporal information of multimedia documents cannot be described using traditional document structures, e.g., Open Document Architecture (ODA) and Standard Generalized Mark-up Language (SGML); the continuous transmission of media units also raises some new synchronization problems, which have not been met before, for processing user interactions. Thus, developing a distributed interactive multimedia document system should resolve the issues of document model, presentation control architecture, and control scheme. In this paper, we (i) propose a new multimedia document model that contains the logical structure, the layout structure, and the temporal structure to formally describe multimedia documents, and (ii) point out main interaction-based synchronization problems, and propose a control architecture and a token-based control scheme to solve these interaction-based synchronization problems. Based on the proposed document model, control architecture, and control scheme, a distributed interactive multimedia document development mechanism, which is called MING-I, is developed on SUN workstations.     

Content-based navigation of music using melodic pitch contours

We describe a system which supports dynamic user interaction with multimedia information using content-based hypermedia navigation techniques, specialising in a technique for navigation of musical content. The model combines the principles of open hypermedia, whereby hypermedia link information is maintained by a link service, with content-based retrieval techniques in which a database is queried based on a feature of the multimedia content; our approach could be described as ‘content-based retrieval of hypermedia links’. The experimental system focuses on temporal media and consists of a set of component-based navigational hypermedia tools. We propose the use of melodic pitch contours in this context and we present techniques for storing and querying contours, together with experimental results. Techniques for integrating the contour database with open hypermedia systems are also discussed.     

Integrating symbolic images into a multimedia database system using classification and abstraction approaches

Symbolic images are composed of a finite set of symbols that have a semantic meaning. Examples of symbolic images include maps (where the semantic meaning of the symbols is given in the legend), engineering drawings, and floor plans. Two approaches for supporting queries on symbolic-image databases that are based on image content are studied. The classification approach preprocesses all symbolic images and attaches a semantic classification and an associated certainty factor to each object that it finds in the image. The abstraction approach describes each object in the symbolic image by using a vector consisting of the values of some of its features (e.g., shape, genus, etc.). The approaches differ in the way in which responses to queries are computed. In the classification approach, images are retrieved on the basis of whether or not they contain objects that have the same classification as the objects in the query. On the other hand, in the abstraction approach, retrieval is on the basis of similarity of feature vector values of these objects. Methods of integrating these two approaches into a relational multimedia database management system so that symbolic images can be stored and retrieved based on their content are described. Schema definitions and indices that support query specifications involving spatial as well as contextual constraints are presented. Spatial constraints may be based on both locational information (e.g., distance) and relational information (e.g., north of). Different strategies for image retrieval for a number of typical queries using these approaches are described. Estimated costs are derived for these strategies. Results are reported of a comparative study of the two approaches in terms of image insertion time, storage space, retrieval accuracy, and retrieval time. Received June 12, 1998 / Accepted October 13, 1998     

Dynamic playout scheduling algorithms for continuous multimedia streams

In this paper, we investigate a playout scheduling framework for supporting the continuous and synchronized presentations of multimedia streams in a distributed multimedia presentation system. We assume a situation in which the server and network transmissions provide sufficient support for the delivery of media objects. In this context, major issues regarding the enforcement of the smooth presentation of multimedia streams at client sites must be addressed to deal with rate variance of stream presentations and delay variance of networks. We develop various playout-scheduling algorithms that are adaptable to quality-of-service parameters. The proposed algorithms permit the local adjustment of unsynchronized presentations by gradually accelerating or retarding presentation components, rather than abruptly skipping or pausing the presentation materials. A comprehensive experimental analysis of the proposed algorithms demonstrates that our algorithms can effectively avoid playout gaps (or hiccups) in the presentations. This scheduling framework can be readily used to support customized multimedia presentations.     

Grammar-based articulation for multimedia document design

This paper describes an approach to the problem of articulating multimedia information based on parsing and syntax-directed translation that uses Relational Grammars. This translation is followed by a constraint-solving mechanism to create the final layout. Grammatical rules provide the mechanism for mapping from a representation of the content and context of a presentation to forms that specify the media objects to be realized. These realization forms include sets of spatial and temporal constraints between elements of the presentation. Individual grammars encapsulate the “look and feel” of a presentation and can be used as generators of such a style. By making the grammars sensitive to the requirements of the output medium, parsing can introduce flexibility into the information realization process.     

A hybrid system approach for supporting digital libraries

A digital library (DL) consists of a database which contains library information and a user interface which provides a visual window for users to search relevant information stored in the database. Thus, an abstract structure of a digital library can be defined as a combination of a special purpose database and a user-friendly interface. This paper addresses one of the fundamental aspects of such a combination. This is the formal data structure for linking an object oriented database with hypermedia to support digital libraries. It is important to establish a formal structure for a digital library in order to efficiently maintain different types of library information. This article discusses how to build an object oriented hybrid system to support digital libraries. In particular, we focus on the discussion of a general purpose data model for digital libraries and the design of the corresponding hypermedia interface. The significant features of this research are, first, a formalized data model to define a digital library system structure; second, a practical approach to manage the global schema of a library system; and finally, a design strategy to integrate hypermedia with databases to support a wide range of application areas. Received: 15 December 1997 / Revised: June 1999     

An algebra for creating and querying multimedia presentations

Over the last few years, there has been a tremendous increase in the number of interactive multimedia presentations prepared by different individuals and organizations. In this paper, we present an algebra for creating and querying interactive multimedia presentation databases. This algebra operates on trees whose branches reflect different possible playouts of a set of presentations. The algebra not only extends all the classical relational operators to such databases, but also introduces a variety of novel operators for combining multiple presentations. As our algebra supports merging parts or all of existing presentations, this algebra can also be used as an authoring tool for creating multimedia presentations. We prove a host of equivalence results for queries in this algebra, which may be used to build query optimizers for interactive presentation databases.     

A logical view of structured files

Structured data stored in files can benefit from standard database technology. In particular, we show here how such data can be queried and updated using declarative database languages. We introduce the notion of structuring schema, which consists of a grammar annotated with database programs. Based on a structuring schema, a file can be viewed as a database structure, queried and updated as such. For queries, we show that almost standard database optimization techniques can be used to answer queries without having to construct the entire database. For updates, we study in depth the propagation to the file of an update specified on the database view of this file. The problem is not feasible in general and we present a number of negative results. The positive results consist of techniques that allow to propagate updates efficiently under some reasonable locality conditions on the structuring schemas. Received November 1, 1995 / Accepted June 20, 1997     

Multimedia databases

The rapidly growing interest in building multimedia tools and applications has created a need for the development of multimedia database management systems (MMDBMSs) as a tool for efficient organization, storage and retrieval of multimedia objects. We begin with a word about traditional database management systems (DBMSs). Then we present an overview of the MMDBMS research issues, challenges, methods, models, and architectures. We review the state of the art and research contributions from related disciplines. Finally, we consider possibilities and probabilities for MMDBMS research in the future.     

Dejittering in the transport of MPEG-2 and MPEG-4 video

When multimedia information is transported over a packet-switched network, the quality of presentation can be degraded due to network delay variation or jitter. This paper presents a dejittering scheme that can be used in the transport of MPEG-4 and MPEG-2 video to absorb any introduced network jitter, thus preserving the presentation quality of transported media streams. The dejittering scheme is based on the statistical approximation of delay variation in the arrival times of video packets carrying encoded clock reference values and a filtering and re-stamping mechanism. In addition, a brief overview of the MPEG-4 system is presented.     

A Methodological Approach for Object-Relational Database Design using UML

The most common way of designing databases is by means of a conceptual model, such as E/R, without taking into account other views of the system. New object-oriented design languages, such as UML (Unified Modelling Language), allow the whole system, including the database schema, to be modelled in a uniform way. Moreover, as UML is an extendable language, it allows for any necessary introduction of new stereotypes for specific applications. Proposals exist to extend UML with stereotypes for database design but, unfortunately, they are focused on relational databases. However, new applications require complex objects to be represented in complex relationships, object-relational databases being more appropriate for these requirements. The framework of this paper is an Object-Relational Database Design Methodology, which defines new UML stereotypes for Object-Relational Database Design and proposes some guidelines to translate a UML conceptual schema into an object-relational schema. The guidelines are based on the SQL:1999 object-relational model and on Oracle8i as a product example. Initial submission: 22 January 2002 / Revised submission: 10 June 2002 Published online: 7 January 2003 This paper is a revised and extended version of Extending UML for Object-Relational Database Design, presented in the UML’2001 conference [17].     

Drag-and-drop multimedia: ¶an interface framework for digital libraries

In this paper, we describe a new interface for querying multimedia digital libraries and an interface building framework. The interface employs a drag-and-drop style of interaction and combines a structured natural-language style query specification with reusable multimedia objects. We call this interface DanDMM, short for “drag-and-drop multimedia”. DanDMM interfaces capture the syntax of the underlying query language, and dynamically reconfigure to reflect the contents of the data repository. A distinguishing feature of DanDMM is its ability to synthesize integrated interfaces that incorporate both example-based specification using multimedia objects, and traditional techniques including keyword, attribute, and free text-based search. We describe the DanDMM-builder, a framework for synthesizing DanDMM interfaces, and give several examples of interfaces that have been constructed using DanDMM-builder, including a remote-sensing library application and a video digital library. Received: 15 December 1997 / Revised: June 1999     

Answering queries using views: A survey

The problem of answering queries using views is to find efficient methods of answering a query using a set of previously defined materialized views over the database, rather than accessing the database relations. The problem has recently received significant attention because of its relevance to a wide variety of data management problems. In query optimization, finding a rewriting of a query using a set of materialized views can yield a more efficient query execution plan. To support the separation of the logical and physical views of data, a storage schema can be described using views over the logical schema. As a result, finding a query execution plan that accesses the storage amounts to solving the problem of answering queries using views. Finally, the problem arises in data integration systems, where data sources can be described as precomputed views over a mediated schema. This article surveys the state of the art on the problem of answering queries using views, and synthesizes the disparate works into a coherent framework. We describe the different applications of the problem, the algorithms proposed to solve it and the relevant theoretical results. Received: 1 August 1999 / Accepted: 23 March 2001 Published online: 6 September 2001     

A survey of approaches to automatic schema matching

Schema matching is a basic problem in many database application domains, such as data integration, E-business, data warehousing, and semantic query processing. In current implementations, schema matching is typically performed manually, which has significant limitations. On the other hand, previous research papers have proposed many techniques to achieve a partial automation of the match operation for specific application domains. We present a taxonomy that covers many of these existing approaches, and we describe the approaches in some detail. In particular, we distinguish between schema-level and instance-level, element-level and structure-level, and language-based and constraint-based matchers. Based on our classification we review some previous match implementations thereby indicating which part of the solution space they cover. We intend our taxonomy and review of past work to be useful when comparing different approaches to schema matching, when developing a new match algorithm, and when implementing a schema matching component. Received: 5 February 2001 / Accepted: 6 September 2001 Published online: 21 November 2001     

Adaptive multimedia synchronization in a teleconference system

In this paper, we present an adaptive buffering scheme for implementing intra-stream and inter-stream synchronization in real-time multimedia applications. The essence of the proposed scheme is to dynamically enforce equalized delays to incoming media streams, in order to piece-wise smooth the network delay variations and to synchronize the streams at the sink. An adaptive control mechanism based on an event-counting algorithm is employed to calibrate the PlayOut Clocks (POCs), which manages the presentations of multimedia data. The algorithm does not rely on globally synchronized clock and makes minimal assumption on underlying network delay distribution. Also, the user defined quality of service (QoS) specifications can be directly incorporated into the design parameters of the synchronization algorithm. The proposed synchronization scheme has been experimentally implemented in a teleconference system which consists of separately controllable audio, video, and data channels. The modular structure of the synchronization control provides the flexibility to maintain an arbitrary synchronization group in conjunction with a distributed conference management scheme. This paper also shows the experimental results of the test implementation and the suitability of the proposed scheme with respect to the multimedia traffic across an FDDI/Ethernet network.     

Design and evaluation of a multimedia storage server for mixed traffic

The relative simplicity of access to digital communications nowadays and the simultaneous increase in the available bandwidth are leading to the definition of new telematic services, mainly oriented towards multimedia applications and interactivity with the user. In the near future, a decisive role will be played in this scenario by the providers of interactive multimedia services of the on-demand type, which will guarantee the end user a high degree of flexibility, speed and efficiency. In this paper, some of the technical aspects regarding these service providers are dealt with, paying particular attention to the problems of storing information and managing service requests. More specifically, the paper presents and evaluates a new storage technique based on the use of disk array technology, which can manage both typical multimedia connections and traditional requests. The proposed architecture is based on the joint use of the partial dynamic declustering and the information dispersal algorithm, which are employed for the allocation and retrieval of the data stored on the disk array. We also define efficient strategies for request management in such a way as to meet the time constraints imposed by multimedia sessions and guarantee good response times for the rest of the traffic. The system proposed is then analyzed using a simulation approach.