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.     

Interactive authoring of multimedia documents in a constraint-based authoring system

As multimedia applications spread widely, it is crucial for programming and design support systems to handle “time” in multimedia documents effectively and flexibly. This paper presents a set of interactive system support tools for designing and maintaining the temporal behavior of multimedia documents. The tool set provides mechanisms for anomaly detection, temporal query processing, and interactive scheduling. It is based on a fast incremental constraint solver we have developed, which can be adapted by any constraint-based system. The incremental constraint solver provides immediate feedback to the user, supporting a highly interactive design process. Combined with existing optimal layout generation mechanisms proposed in the literature, our tools effectively utilize the flexibility provided by constraint-based systems.     

Towards video-based immersive environments

Video provides a comprehensive visual record of environment activity over time. Thus, video data is an attractive source of information for the creation of virtual worlds which require some real-world fidelity. This paper describes the use of multiple streams of video data for the creation of immersive virtual environments. We outline our multiple perspective interactive video (MPI-Video) architecture which provides the infrastructure for the processing and analysis of multiple streams of video data. Our MPI-Video system performs automated analysis of the raw video and constructs a model of the environment and object activity within this environment. This model provides a comprehensive representation of the world monitored by the cameras which, in turn, can be used in the construction of a virtual world. In addition, using the information produced and maintained by the MPI-Video system, our immersive video system generates virtual video sequences. These are sequences of the dynamic environment from an arbitrary view point generated using the real camera data. Such sequences allow a user to navigate through the environment and provide a sense of immersion in the scene. We discuss results from our MPI-Video prototype, outline algorithms for the construction of virtual views and provide examples of a variety of such immersive video sequences.     

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.     

The Personal Presence System: a wide-area network resource for the real-time composition of multipoint multimedia communications

The Personal Presence System (PPS) is an experimental research prototype platform to support advanced broadband applications, including multimedia conferencing and distance learning. It supports the user's presentation control of advanced network elements (multimedia bridges). The multimedia bridge provides for a single contact point per user, who receives only one combined video stream, which minimizes access bandwidth. This architecture solves the -squared transmission problem of multipoint video conferencing and makes customer terminal equipment simpler and cheaper than high-end desktop workstations. The PPS provides each user with flexible presentation control of a feature-rich video bridge. The PPS also supports advanced features such as object extraction and multimedia object associations.     

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.     

Context-based prefetch – an optimization for implementing objects on relations

When implementing persistent objects on a relational database, a major performance issue is prefetching data to minimize the number of round-trips to the database. This is especially hard with navigational applications, since future accesses are unpredictable. We propose the use of the context in which an object is loaded as a predictor of future accesses, where a context can be a stored collection of relationships, a query result, or a complex object. When an object O's state is loaded, similar state for other objects in O's context is prefetched. We present a design for maintaining context and for using it to guide prefetch. We give performance measurements of its implementation in Microsoft Repository, showing up to a 70% reduction in running time. We describe several variations of the optimization: selectively applying the technique based on application and database characteristics, using application-supplied performance hints, using concurrent database queries to support asynchronous prefetch, prefetching across relationship paths, and delayed prefetch to save database round-trips. Received May 3, 2000 / Accepted October 26, 2000     

Synchronization of distributed multimedia systems with user interactions

Without user interactions, multimedia presentations are just fancy slide shows with sound and video supports. User interactions by themselves do not change the temporal relationships among multimedia objects, such as texts, graphics, images, audio, and video, but affect the playback schedules. In this paper, we propose a synchronization mechanism to guarantee the quality of multimedia presentation with user interactions. In our protocol, each presentation site requests media transmission from the required media servers at certain time intervals prior to the playback deadlines, where these time intervals are the response times to cover possible experienced end-to-end delays and packet losses, and waits for an initial setup time to ensure intermedia synchronization before starting the presentation. Users may interact with the presentation. This synchronization mechanism solves the problems incurred by user interactions by determining the new presentation scenario produced by the interactive operation, calculating the corresponding setup time, and then rendering the new playback and retrieval schedules.     

Effectiveness of keyword-based display and selection of retrieval results for interactive searches

We present an approach to increasing the effectiveness of ranked-output retrieval systems that relies on graphical display and user manipulation of “views” of retrieval results, where a view is the subset of retrieved documents that contain a specified subset of query terms. This approach has been implemented in a system named VIEWER (VIEwing WEb Results), acting as an interface to available search engines. An experimental evaluation of the performance of VIEWER in contrast to AltaVista is the major focus of the paper. We first report the results of an experiment on single, short query searches where VIEWER, used as an interactive ranking system, markedly outperformed AltaVista. We then concentrate on a more realistic searching scenario, involving free query formulation, unconstrained selection of retrieval results, and possibility of query reformulation. We report the results of an experiment where the use of VIEWER, compared to AltaVista, seemed to shift the user effort from inspection to evaluation of results, increasing retrieval effectiveness, and user satisfaction. In particular, we found that the VIEWER users retrieved half as many nonrelevant documents as the AltaVista users while retrieving a comparable number of relevant documents. Published online: 22 September 2000     

Semantic caching of Web queries

Abstract. In meta-searchers accessing distributed Web-based information repositories, performance is a major issue. Efficient query processing requires an appropriate caching mechanism. Unfortunately, standard page-based as well as tuple-based caching mechanisms designed for conventional databases are not efficient on the Web, where keyword-based querying is often the only way to retrieve data. In this work, we study the problem of semantic caching of Web queries and develop a caching mechanism for conjunctive Web queries based on signature files. Our algorithms cope with both relations of semantic containment and intersection between a query and the corresponding cache items. We also develop the cache replacement strategy to treat situations when cached items differ in size and contribution when providing partial query answers. We report results of experiments and show how the caching mechanism is realized in the Knowledge Broker system. Received June 15, 1999 / Accepted December 24, 1999     

Intelligent multimedia data: data + indices + inference

In this paper, we present a novel approach for multimedia data indexing and retrieval that is machine independent and highly flexible for sharing multimedia data across applications. Traditional multimedia data indexing and retrieval problems have been attacked using the central data server as the main focus, and most of the indexing and query-processing for retrieval are highly application dependent. This precludes the use of created indices and query processing mechanisms for multimedia data which, in general, have a wide variety of uses across applications. The approach proposed in this paper addresses three issues: 1. multimedia data indexing; 2. inference or query processing; and 3. combining indices and inference or query mechanism with the data to facilitate machine independence in retrieval and query processing. We emphasize the third issue, as typically multimedia data are huge in size and requires intra-data indexing. We describe how the proposed approach addresses various problems faced by the application developers in indexing and retrieval of multimedia data. Finally, we present two applications developed based on the proposed approach: video indexing; and video content authorization for presentation.     

One-dimensional and multi-dimensional substring selectivity estimation

With the increasing importance of XML, LDAP directories, and text-based information sources on the Internet, there is an ever-greater need to evaluate queries involving (sub)string matching. In many cases, matches need to be on multiple attributes/dimensions, with correlations between the multiple dimensions. Effective query optimization in this context requires good selectivity estimates. In this paper, we use pruned count-suffix trees (PSTs) as the basic data structure for substring selectivity estimation. For the 1-D problem, we present a novel technique called MO (Maximal Overlap). We then develop and analyze two 1-D estimation algorithms, MOC and MOLC, based on MO and a constraint-based characterization of all possible completions of a given PST. For the k-D problem, we first generalize PSTs to multiple dimensions and develop a space- and time-efficient probabilistic algorithm to construct k-D PSTs directly. We then show how to extend MO to multiple dimensions. Finally, we demonstrate, both analytically and experimentally, that MO is both practical and substantially superior to competing algorithms. Received April 28, 2000 / Accepted July 11, 2000     

The end of zero-hit queries: query previews for NASA’s Global Change Master Directory

The Human-Computer Interaction Laboratory (HCIL) of the University of Maryland and NASA have collaborated over three years to refine and apply user interface research concepts developed at HCIL in order to improve the usability of NASA data services. The research focused on dynamic query user interfaces, visualization, and overview + preview designs. An operational prototype, using query previews, was implemented with NASA’s Global Change Master Directory (GCMD), a directory service for earth science datasets. Users can see the histogram of the data distribution over several attributes and choose among attribute values. A result bar shows the cardinality of the result set, thereby preventing users from submitting queries that would have zero hits. Our experience confirmed the importance of metadata accuracy and completeness. The query preview interfaces make visible the problems or gaps in the metadata that are undetectable with classic form fill-in interfaces. This could be seen as a problem, but we think that it will have a long-term beneficial effect on the quality of the metadata as data providers will be compelled to produce more complete and accurate metadata. The adaptation of the research prototype to the NASA data required revised data structures and algorithms. Received: 12 December 1997 / Revised: June 1999     

Query processing over object views of relational data

This paper presents an approach to object view management for relational databases. Such a view mechanism makes it possible for users to transparently work with data in a relational database as if it was stored in an object-oriented (OO) database. A query against the object view is translated to one or several queries against the relational database. The results of these queries are then processed to form an answer to the initial query. The approach is not restricted to a ‘pure’ object view mechanism for the relational data, since the object view can also store its own data and methods. Therefore it must be possible to process queries that combine local data residing in the object view with data retrieved from the relational database. We discuss the key issues when object views of relational databases are developed, namely: how to map relational structures to sub-type/supertype hierarchies in the view, how to represent relational database access in OO query plans, how to provide the concept of object identity in the view, how to handle the fact that the extension of types in the view depends on the state of the relational database, and how to process and optimize queries against the object view. The results are based on experiences from a running prototype implementation. Edited by: M.T. ?zsu. Received April 12, 1995 / Accepted April 22, 1996     

Increasing multimedia system throughput with consumption-based buffer management

In a multimedia server, multiple media streams are generally serviced in a cyclic fashion. Due to non-uniform playback rates and asynchronous arrivals of queries, there tends to be spare disk bandwidth in each service cycle. In this paper, we study the issue of dynamically using spare disk bandwidth and buffer to maximize the system throughput of a multimedia server. We introduce the concept of minimizing buffer consumption as the criterion to select an appropriate media stream to utilize the spare system resources. Buffer consumption measures not only the amount of buffer but also the amount of time such buffer space is occupied (i.e., the space-time product). Different alternatives to utilizing spare disk bandwidth are examined, including different rate-adjustable retrievals of an already activated stream and prefetching the next waiting stream. For rate-adjustable retrievals, we study buffer consumption-based and remaining-time-based criteria for selecting an active stream to increase retrievals. Simulations are conducted to evaluate and compare different cases. The results show that (1) minimizing buffer consumption is the right criterion for maximizing the system throughput with spare disk bandwidth; (2) in general, prefetching a waiting stream incurs more buffer consumption, and thus is less effective than rate-adjustable retrieval of active streams in maximizing the system throughput; and (3) the advantage of rate-adjustable retrieval over prefetching is especially significant when service cycle time is small.     

A data model and a query languagefor multimedia documents databases

A multimedia application involves information that may be in a form of video, images, audio, text and graphics, need to be stored, retrieved and manipulated in large databases. In this paper, we propose an object-oriented database schema that supports multimedia documents and their temporal, spatial and logical structures. We present a document example and show how the schema can adress all the structures described. We also present a multimedia query specification language that can be used to describe a multimedia content portion to be retrieved from the database. The language provides means by which the user can specify the information on the media as well as the temoral and spatial relationships among these media.     

Presentations for databases in multimedia environments

The problem of presenting database query results has not been investigated sufficiently. This work proposes an approach to identify effective presentations for the results of database queries. This will be done by considering different kinds of information, such as user goals, the characteristics of the data to be presented, and the relationships among them. Our approach is based on the definition of composition operations which, on the basis of elementary presentation types, allow us to obtain designs of complex final presentations. Some effectiveness criteria are considered in order to identify those presentations which best match the user's goals and cognitive abilities. We consider multimedia environments at both the data and presentation level.     

The OODB path-method generator (PMG) using access weights and precomputed access relevance

A path-method is used as a mechanism in object-oriented databases (OODBs) to retrieve or to update information relevant to one class that is not stored with that class but with some other class. A path-method is a method which traverses from one class through a chain of connections between classes and accesses information at another class. However, it is a difficult task for a casual user or even an application programmer to write path-methods to facilitate queries. This is because it might require comprehensive knowledge of many classes of the conceptual schema that are not directly involved in the query, and therefore may not even be included in a user's (incomplete) view about the contents of the database. We have developed a system, called path-method generator (PMG), which generates path-methods automatically according to a user's database-manipulating requests. The PMG offers the user one of the possible path-methods and the user verifies from his knowledge of the intended purpose of the request whether that path-method is the desired one. If the path method is rejected, then the user can utilize his now increased knowledge about the database to request (with additional parameters given) another offer from the PMG. The PMG is based on access weights attached to the connections between classes and precomputed access relevance between every pair of classes of the OODB. Specific rules for access weight assignment and algorithms for computing access relevance appeared in our previous papers [MGPF92, MGPF93, MGPF96]. In this paper, we present a variety of traversal algorithms based on access weights and precomputed access relevance. Experiments identify some of these algorithms as very successful in generating most desired path-methods. The PMG system utilizes these successful algorithms and is thus an efficient tool for aiding the user with the difficult task of querying and updating a large OODB. Received July 19, 1993 / Accepted May 16, 1997     

Yoda,an adaptive soft classification model: content-based similarity queries and beyond

Abstract. Providing a customized result set based upon a user preference is the ultimate objective of many content-based image retrieval systems. There are two main challenges in meeting this objective: First, there is a gap between the physical characteristics of digital images and the semantic meaning of the images. Secondly, different people may have different perceptions on the same set of images. To address both these challenges, we propose a model, named Yoda, that conceptualizes content-based querying as the task of soft classifying images into classes. These classes can overlap, and their members are different for different users. The “soft” classification is hence performed for each and every image feature, including both physical and semantic features. Subsequently, each image will be ranked based on the weighted aggregation of its classification memberships. The weights are user-dependent, and hence different users would obtain different result sets for the same query. Yoda employs a fuzzy-logic based aggregation function for ranking images. We show that, in addition to some performance benefits, fuzzy aggregation is less sensitive to noise and can support disjunctive queries as compared to weighted-average aggregation used by other content-based image retrieval systems. Finally, since Yoda heavily relies on user-dependent weights (i.e., user profiles) for the aggregation task, we utilize the users' relevance feedback to improve the profiles using genetic algorithms (GA). Our learning mechanism requires fewer user interactions, and results in a faster convergence to the user's preferences as compared to other learning techniques. Correspondence to: Y.-S. Chen (E-mail: yishinc@usc.edu) This research has been funded in part by NSF grants EEC-9529152 (IMSC ERC) and IIS-0082826, NIH-NLM R01-LM07061, DARPA and USAF under agreement nr. F30602-99-1-0524, and unrestricted cash gifts from NCR, Microsoft, and Okawa Foundation.