The recent proliferation of multimedia contents led to the need to more effective and efficient content representation techniques to speed up their retrieval. MPEG-7 is a new standard that aims at describing the low-level (syntactic) and high-level (semantic) multimedia content. In MPEG-7, the relationships between moving regions (i.e. objects) in videos are represented by the directional, spatial and temporal relationships. In this paper, we propose to extend the description scheme (DS) of moving objects to include rich sets of visual-spatio-temporal (VST) relationships that support semantical descriptions of the relationships between objects. Also, we propose an XML based DSs of the VST relationships and then present the bit format representations for the VST relationships. The VST relationships are more intuitive to users, thus simplifying the formulation of user queries.

In the past few years, modeling and querying video databases have been a subject of extensive research to develop tools for effective search of videos. In this paper, we present a hierarchal approach to model videos at three levels, object level (OL), frame level (FL), and shot level (SL). The model captures the visual features of individual objects at OL, visual-spatio-temporal (VST) relationships between objects at FL, and time-varying visual features and time-varying VST relationships at SL. We call the combination of the time-varying visual features and the time-varying VST relationships a Content trajectory which is used to represent and index a shot. A novel query interface that allows users to describe the time-varying contents of complex video shots such as those of skiers, soccer players, etc., by sketch and feature specification is presented. Our experimental results prove the effectiveness of modeling and querying shots using the content trajectory approach.

Abstract Earthquakes have been recognized as resulting from a stick–slip frictional instability along the faults between deformable rocks. An arbitrarily‐shaped contact element strategy, named the node‐to‐point contact element strategy, is proposed, applied with the static‐explicit characters to handle the friction contact between deformable bodies with stick and finite frictional slip and extended here to simulate the active faults in the crust with a more general nonlinear friction law. An efficient contact search algorithm for contact problems among multiple small and finite deformation bodies is also introduced. Moreover, the efficiency of the parallel sparse solver for the nonlinear friction contact problem is investigated. Finally, a model for the plate movement in the north‐east zone of Japan under gravitation is taken as an example to be analyzed with different friction behaviors. Copyright © 2002 John Wiley & Sons, Ltd.

In this paper, we present a novel technique for real-time cloth simulation. The method combines dynamic simulation and geometric techniques. Only a small number of particles (a few hundred at maximum) are controlled using dynamic simulation to simulate global cloth behaviors such as waving and bending. The cloth surface is then smoothed based on the elastic forces applied to each particle and the distance between each pair of adjacent particles. Using this geometric smoothing, local cloth behaviors such as twists and wrinkles are efficiently simulated. The proposed method is very simple, and is easy to implement and integrate with existing particle-based systems. We also describe a particle-based simulation system for efficient simulation with sparse particles. The proposed method has animated a skirt with rich details in real-time.

Feature-based similarity retrieval has become an important research issue in multimedia database systems. The features of multimedia data are useful for discriminating between multimedia objects (e.g., documents, images, video, music score, etc.). For example, images are represented by their color histograms, texture vectors, and shape descriptors. A feature vector is a vector that represents a set of features, and are usually high-dimensional data. The performance of conventional multidimensional data structures (e.g., R-tree family K-D-B tree, grid file, TV-tree) tends to deteriorate as the number of dimensions of feature vectors increases. The R*-tree is the most successful variant of the R-tree. We propose a SOM-based R*-tree as a new indexing method for high-dimensional feature vectors. The SOM-based R*-tree combines SOM and R*-tree to achieve search performance more scalable to high dimensionalities. Self-organizing maps (SOMs) provide mapping from high-dimensional feature vectors onto a two-dimensional space. The mapping preserves the topology of the feature vectors. The map is called a topological feature map, and preserves the mutual relationships (similarity) in the feature spaces of input data, clustering mutually similar feature vectors in neighboring nodes. We experimentally compare the retrieval time cost of a SOM-based R*-tree with that of an SOM and an R*-tree using color feature vectors extracted from 40,000 images.

Proposes a new parallel algorithm for computing path expressions, named the "parallel cascade semi-join" (PCSJ) algorithm. Moreover, a new scheduling strategy called the "right-deep zigzag tree" is designed to further improve the performance of the PCSJ algorithm. The experiments have been implemented in a distributed and parallel NOW (network of workstations) environment. The results show that the PCSJ algorithm outperforms two other parallel algorithms [the parallel forward pointer chasing (PFPC) algorithm and the index-splitting parallel algorithm (IndexSplit)] when computing path expressions with restrictive predicates, and that the right-deep zigzag tree scheduling strategy has a better performance than the right-deep tree scheduling strategy.

In order to support processing of highly concurrent transactions at low price on distributed database server systems, a network of workstations (NOW) is used as the hardware environment. In order to share resources that are distributed among different sites of NOW and support the database functionalities, persistent distributed shared virtual memory (PDSVM) is implemented on ShusseUo, an object database system developed by Kyushu University, Japan. In ShusseUo, all workstations cooperate to perform jobs submitted by database applications. Each job consists of several transactions. These transactions are executed on PDSVM and the cost of each transaction varies according to the workstation on which the transaction runs. We present the cost-based transaction coordinator (CTC) algorithm. In CTC, the load information of a transaction is collected automatically while the transaction is running, and it is fed back when the transaction is committed. In CTC, each transaction is coordinated to a certain workstation based on its cost as calculated using the fed back information and the distribution information of the database. The algorithm is evaluated in terms of the TPC-C benchmark. The benchmark result is presented and analyzed.

Earth science (ES) applications handle very large geo-spatial data sets and interactive response time is required by its query processing. Spatial selection is one of the very important basic operations for geo-spatial databases. It retrieves all the objects that intersect with a given point or rectangle. We present a novel approach for the parallel processing of spatial selection of very large geo-spatial databases using partitioned parallelism. To evaluate this approach, we use the Extended Sequoia 2000 benchmark, which has real world data and real queries. In addition, we use an actual object database management system, ShusseUo, which we developed previously. The experimental results of parallel processing of spatial selection show good speed-up.

This paper presents a dynamic motion control technique for human-like articulated figures in a physically based character animation system. This method controls a figure such that the figure tracks input motion specified by a user. When environmental physical input such as an external force or a collision impulse are applied to the figure, this method generates dynamically changing motion in response to the physical input. We have introduced comfort and balance control to compute the angular acceleration of the figure's joints. Our algorithm controls the several parts of a human-like articulated figure separetely through the minimum number of degrees-of-freedom. Using this approach, our algorithm simulates realistic human motions at efficient computational cost. Unlike existing dynamic simulation systems, our method assumes that input motion is already realistic, and is aimed at dynamically changing the input motion in real-time only when unexpected physical input is applied to the figure. As such, our method works efficiently in the framework of current computer games.

Discusses dynamic performance optimization mechanisms for parallel object-oriented database programming languages. When a large number of objects are distributed on a distributed-memory parallel processor, referencing a remote object requires inter-processor communication. If those objects are not allocated properly, it may cause total performance degradation. When those objects are allocated with a biased distribution among the processing elements, it may cause a load imbalance. However, the information necessary for relocating objects must be obtained at run time, since the number of objects on a processor and the topology of the objects in a database are unknown at compilation time. This paper proposes a new approach to dynamic performance optimization method, and evaluates the results through simulation tests.

An entity in the real world may obtain and lose its roles, or aspects, again and again with time. For modeling such dynamic changes of aspects, objects having multiple types, or multiple-type objects, are essential to persistent programming languages. In this paper, we introduce multiple-type objects, and show a method of implementing them in an enhanced C++ persistent programming language called INADA. Any persistent objects in INADA may obtain any type at any time the type is needed, and may lose any unnecessary types dynamically. We also present a performance study in which the performance penalty caused by the introduction of multiple-type objects was examined. Copyright © 2000 John Wiley & Sons, Ltd.

Applying design patterns to the design of an application makes it robust against issues related to extensibility and maintainability. However, currently, a designer must apply structures and constraints of design patterns to an application by hand, therefore mistakes often occur. We have proposed a notation using SGML for describing design patterns and a support system for design patterns. We aim at providing a source code generation support system based on the notation and system. There has been much research into semi-automatic application generators using existing knowledge such as libraries based on algorithms and data structure, and classes packaged based on the object-oriented technology. When using design patterns for source code generation support, the same requirements for such semi-automatic application generators must be considered. The requirements are lessening codes to be written by users, and satisfying constraints without directing users' attention to them. In this paper we consider the requirements and describe a design and implementation of the source code generation support system and results.

Though parallel database systems have been extensively studied, as far as we know, the parallel algorithms of R-tree proposed so far are limited to one workstation with multiprocessors or multi disks, where a parallel sorting algorithm or concurrent I/O is used to improve the performance. For the searching of R-trees, multiple search paths from the root to leaves are traversed sequentially. This sequential traverse can be transformed into multiple parallel traverses based on multiple search paths, where the query is divided into subqueries which can be executed concurrently. Aiming at parallel I/O and CPU operations, we introduce a parallel R-tree search algorithm running on distributed shared virtual memory (DSVM), especially on Shusseuo which is an ODBMS providing global persistent object management on persistent DSVM. The related problems are discussed and the evaluations are made based on Shusseuo. Experimental results show that optimal performance can be reached in dealing with large volumes of data.

Hash joins are expensive and important operations in relational database systems. Developing parallel hash join algorithms is known as an efficient method to improve their performance. Since a parallel processing environment of a networked cluster of nodes is widely available for its advantages of low-cost, high speed and ease of use, we developed a parallel hash-based join algorithm in a networked cluster of multiprocessor nodes. The parallel hash-based join algorithm has two features. One is that it takes advantage of parallel and distributed environments in which shared-memory multiprocessor computers are nodes of a networked cluster. The other is that a distributed shared virtual space is integrated into the design of the parallel hash-based join algorithm so as to facilitate the algorithm and its implementation. In this paper, we present the ideas of design, describe the parallel hash-based join algorithm, show the performance evaluation of it, as well as give a dynamic changing message model for the presence of skew.

Design patterns are abstract software components for system structures and functions used in OOA/OOD. They are described currently as texts (with figures), and difficult to catalog, maintain and handle. The paper presents a framework to describe patterns as structured documents based on SGML (Structured Generalized Markup Language). A design pattern, in general, has three elements: texts, configuration charts and pseudo-codes, therefore SGML schemes are proposed for them respectively so that they are integrated into a single structured document. The document also includes link to related pattern documents and corresponding class source codes. This SGML-based pattern document is visualized by automatic HTML conversion and automatic chart generation. And the document is used for interactive code generation.

Four object reference mechanisms for a parallel object-oriented database system (OODBS) and used by a massively parallel programming language (MAPPLE) are tested by the parallel 001 Benchmark. Out of these mechanisms, the object allocation table (OAT) was the most successful when many objects existed and were moved across processors. The OAT stores object identifiers (OIDs) that are independent of the object location and are paired with an indicator of the object location. In addition, the evaluation results show that when the number of object references among processors is large, an OAT entry should be inserted when an object is created. If the number is small, an OAT entry should be inserted when an object is referenced for the first time.

Integrating parallel functions into the manipulation of persistent objects on a network-based shared memory architecture is a proposal under consideration. The cost associated with manipulating a large amount of distributed persistent objects is expected to improve from sequential to parallel processing. However, it is a complex task to combine persistence with the capability of parallel and distributed processing. We put forward the design and implementation methods concerning this. Based on a C++ based language called INADA, in which functions for handling persistent objects are introduced, we present a language construct for accessing distributed persistent objects in parallel, and a new approach for supporting transparent parallel and distributed processing. The transparency assures that distributed persistent objects are manipulated in parallel on multiple threads of remote computers as if they were manipulated in a local multiprocessor machine. A key point of this proposal is that we have made a combination of persistence, multithread primitives, network-based shared-memory, and the agent-oriented paradigm.

This paper presents the transaction management in a high performance distributed object storage system WAKASHI. Unlike other systems that use centralized client/server architecture and other conventional buffer management for distributed persistent object management, WAKASHI is based on symmetric peer-peer architecture and employs memory-mapping and distributed shared virtual memory techniques. Several novel techniques of transaction management for WAKASHI are developed. First, a multi-threaded transaction manager offers "multi-threaded connection" so that data control and transaction operations can be performed in parallel manner. Secondly, a concurrency control mechanism supports transparent page-level locks to reduce the complexity of user programs and locking overhead. Thirdly, a "compact commit" method is proposed to minimize the communication cost by reducing the amount of data and the number of connections. Fourthly, a redo-only recovery method is implemented by "shadowed cache" method to minimize the logging cost, and to allow fast recovery and system restart. Moreover, the system offers "hierarchical" control to support nested transactions. A performance evaluation by the OO7 benchmark is presented.

An analytical model is presented for estimating parallel efficiency of the domain decomposition method which is used for the parallelization of implicit finite element code. Serial and parallel finite element codes with domain decomposition and direct LDU solution of equation systems are developed. Dependencies of parallel efficiency on problem size are obtained for IBM SP2 with 4,6 and 8 processor nodes. It is shown that interprocessor load balancing during assembly-decomposition phase which can be achieved by partitioning into unequal subdomains increase parallel efficiency considerably. Predicted and measured values of parallel efficiency are in reasonable agreement.

In general it takes a lot of time to decide the forms of classes, or types, in database design. This is because the forms of objects stored in a database can hardly be changed. If the objects can get and lose types dynamically, this may be solved. We describe design of multiple type objects in INADA, an object oriented persistent programming language. Any persistent objects in INADA may get any types at any time the types are needed, and may lose any unnecessary types dynamically. INADA is an enhanced C++ language; it borrows the object model of C++ and extends it to provide facilities needed for processing on a large amount of persistent objects. We also show implementation of multiple type objects borrowing the type system of C++ just as it is.

New applications such as CAD, AI, and hypermedia require direct representation and flexible use of complex objects, behavioral knowledge, and multimedia data. To this end, we have devised a knowledge base management system called Jasmine. An object-oriented approach in a programming language also seems promising for use in Jasmine. Jasmine extends the current object-oriented approach and provides the following features. Our object model is based on functional data models and well-established set theory. Attributes or functions composing objects can represent both structural and behavioral knowledge. The object model can represent incomplete and generic knowledge. The model can support the basic storage and operations of multimedia data. The facets of attributes can flexibly represent constraints and triggers. The object manipulation language can support associative access of objects. The structural and behavioral knowledge can be uniformly treated to allow the user to specify complex object operations in a compact manner. The user-defined and system-defined attributes can be uniformly specified to ease user customization of the language. The classes and instances can be uniformly accessed. Incomplete knowledge can be flexibly accessed. The system has a layered architecture. Objects are stored in nested relations provided by extensive DBMS as a sublayer. User query of objects is compiled into relational operations such as select and join, which can be efficiently processed using hashing. The behavioral knowledge is compiled into predicate and manipulation function interfaces that can directly access tuples in a buffer.— Authors' Abstract

The authors propose an object-oriented programming language called WARASA for writing concurrent object-oriented program on Mach-based shared memory multiprocessor computers. WARASA is an extension to C/sup ++/ to allow a programmer to develop concurrent programming. In designing WARASA, the parallel mechanisms on the Mach operating system are combined with the object-oriented paradigm. It enables users to develop concurrent programs easily and efficiently, because some implementation details such as locking and unlocking which programmers would have to know to write parallel programs are hidden. An overview of WARASA is given. The features of WARASA class models are discussed. Some applications are shown to demonstrate WARASA's expressive power.>

This paper presents a knowledge-based approach to design a portable natural language interface to database systems, called KID (Knowledge-based Interface to Database systems). To free the user from the need to know about query languages and databases, and to allow the user to access databases in natural language, KID incorporates a knowledge base called the world model (WM), which contains a domain model, linguistic knowledge, and database mapping knowledge. To transport KID to a new domain, the user has only to build a new WM for the domain; the WM is easy for the user to define and understand. KID's processing of the user's query using the WM is transparent enough to the user to enable easy debugging of the WM. Encapsulating all the domain-specific knowledge into the WM makes KID portable. This paper discusses the WM design and KID's knowledge-based processing of a query using the WM.

KIPS is an automatic programming system which generates standardized business application programs through interactive natural language dialogue.KIPS models the program under discussion and the content of the user's statements as organizations of dynamic objects in the object*oriented programming sense.This paper describes the statement*model and the program-model, their use in understanding Japanese program specifications, and bow they are shaped by the linguistic singularities of Japanese input sentences.