Human faces convey various information, including that is specific to each individual person and that is part of mutual communication among persons. Information exhibited by a "face" is what is called "non-verbal information" and usually verbal media cannot easily describe such information appropriately. Recently, detailed studies on the processing of face images by a computer have been carried out in the engineering field for applications to communication media and human computer interaction as well as automatic identification of human faces. Two main technical topics are the recognition of human faces and the synthesis of face images. The objective of the former is to enable a computer to detect and identify users and further to recognize their facial expressions, while that of the latter is to provide a natural and impressive user interface on a computer in the form of a "face. " These studies have also been found to be useful in various non-engineering fields related to a face, such as psychology, anthropology, cosmetology and dentistry. Most of the studies in these different fields have been carried out independently up to now, although all of them deal with a "face. " Now in virtue of the progress in the above engineering technologies a common study tools and databases for facial information have become available. On the basis of these backgrounds, this paper surveys recent research trends in the processing of face images by a computer and its typical applications. Firstly, the various characteristics of faces are considered. Secondly, recent research activities in the recognition and synthesis of face images are outlined. Thirdly, the applications of digital processing methods of facial information are discussed from several standpoints: intelligent image coding, media handling, human computer interaction, caricature, facial impression, psychological and medical applications. The common tools and databases used in the studies of processing of facial information and some related topics are also described.

Recently, mobile computing has received much attention from database community. Sharing information among mobile users is one of the most challenging issues in mobile computing due to user mobility. Replication is a promising technique to this issue. However, adopting replication into mobile computing is a non-trivial task, since we are still facing other problems such as the lack in disk capacity and wireless network bandwidth used by mobile users. We have proposed a dynamic replica allocation strategy called User Majority Replica Allocation (UMRA) that is well suited to the modern architecture of mobile computing environment while avoiding such problems mentioned above. In this paper, we propose two relocation decision policies for UMRA and we provide a cost analysis for them. We also provide a cost analysis for another replica allocation strategy called Static Replica Allocation (SRA) for a comparison purpose.

This paper presents a new scheme of a low-power area-efficient pipelined A/D converter using a single-ended amplifier. The proposed multiply-by-two single-ended amplifier using switched capacitor circuits has smaller DC bias current compared to the conventional fully-differential scheme, and has a small capacitor mismatch sensitivity, allowing us to use a smaller capacitance. The simple high-gain dynamic-biased regulated cascode amplifier also has an excellent switching response. These properties lead to the low-power area-efficient design of high-speed A/D converters. The estimated power dissipation of the 10-b pipelined A/D converter is less than 12 mW at 20 MSample/s.

In geographical databases for navigation, users raise various types of queries concerning route guidance. The most fundamental query is a shortest-route query, but, as dynamical traffic information newly becomes available and the static geographical database of roads itself has grown up further, more flexible queries are required to realize a user-friendly interface meeting the current settings. One important query among them is a detour query which provides information about detours, say listing several candidates for useful detours. This paper first reviews algorithms for the shortest and k shortest paths, and discusses their extensions to detour queries. Algorithms for finding a realistic detour are given. The efficiency and property of the algorithms are examined through experiments on an actual road network.

Object-Oriented database systems (OODBMS) are well known for modeling complex and dynamic application domains. Typically OODBMS have to handle large and complex structured objects whose values and structures can change frequently. Consequently there is a high demand for systems which support temporal and versioning features in both objects (or database population) and schema. This paper presents a mechanism for accessing the temporal versioned objects stored in the database which supports schema versioning. The results shown here can be considered as a value-added extension of our model called TVOO described in detail in [1] and [2]. In contrast to conventional database models, in TVOO objects and classes are not physically discarded from the database after they are modified or deleted. They are time dependent and the history of the changes which occur on them are kept as Version hierarchies. Therefore our model enriches the database environment with temporal and versioning features. Also, an access mechanism which makes it possible to access any object under any schema version is defined in such a way that not only objects created under old versions of schema classes can be accessed from new versions, but also objects created by new schema class versions can be accessed from old versions of the respective class.

This paper describes a way of implementing a conceptual model for temporal data on a commercial object database system. The implemented version is provided as a class library. The library enables applications to handle temporal data. Any application can employ the library because it does not depend on specific applications. Furthermore, we propose an enhanced version of Time Index. The index efficiently processes event queries in particular. These queries search time intervals in which given events are all valid. We also investigate the effectiveness of the enhanced Time Index.

This paper gives an overview of research activities on high performance databases in Japan. It focuses on parallel algorithms for relational databases and data mining, parallel approaches for object-oriented databases, and parallel disk systems. Studies surveyed in this paper are carried out mainly by database researchers in Japanese universities under the Grant-in-Aid for Scientific Research (1996-1998).

This paper proposes a new framework of managing virtual spaces based on spatial databases as an extension of VRML-based systems. The framework is suitable for treating continuous virtual spaces and for managing the quality of service (QoS) of the virtual spaces depending on user's operations and situations of computer resources. Levels of detail (LoD) of 3D objects is the most important rule for rendering scenes dynamically while managing the QoS. This paper describes a method of managing the QoS depending on the LoD in the form of spatial queries. An advantage of the framework is that spatial databases can incrementally construct virtual spaces in clients using differential descriptions based on VRML, that is, DVRML, proposed in this paper. Dynamic spatial data such as avatar's movement and real-time multimedia data such as videos should be shared by all participants in a virtual space in real time. Our framework can also handle dynamic spatial data by means of real-time updating of some spatial objects in spatial databases as well as static spatial data. We developed some experimental applications based on the framework in order to prove that it is feasible for networked virtual spaces with video components.

In this paper, we will discuss a map synthesis system which handles static information (geographic objects) as well as dynamic information (traffic conditions, weather, etc. ). In addition to geographic thesauruses used in the previous systems, we will use co-existence relationships to improve the quality of maps generation. The system is considered to be general purpose (not restricted to car navigation nor travel maps) and can generate arbitrary maps according to the user's specification. It is very difficult for a user to specify a query which corresponds to the required map, because map description is not easy. The system should automatically generate missing information or find errors in the user specification. For the purpose we use geographic domain thesauruses which contain aggregation and other geographic relationships as well as conventional thesaurus hierarchy. In this paper, we will discuss to use co-existence relationships to enhance ability to select geographic objects automatically. Co-existence specifies relationships among geographic objects which should appear in a map together although they may not have geographic relationship by thesauruses. By utilizing co-existence relationships, a user can acquire much more understandable maps.

The Web is a collection of multimedia documents in the form of HTML pages connected through hyperlinks. Unlike most search engines, which focus on information retrieval based on keywords, WebDB aims at supporting database-like comprehensive query functionalities as well navigation, and document generation functionalities with customizability. To support hypermedia database functionalities, we augment the traditional concepts of tables in relational databases and classes in object-oriented databases with notions of document formats and navigation. We design WQL (Web Query Language) as an HTML document manipulation language. WQL language statements contain two parts: SELECT. . . FROM. . . WHERE clauses for specifying retrieval of data contents from hypermedia databases and CREATE. . . AS. . . clauses for specifying the output HTML format and navigation of the query results. This paper presents the architecture of WebDB and its functionalities. The extension to SQL for hypermedia document manipulation, query, and navigation and implementation on NEC PERCIO OODBMS are described in detail.

Structured documents often contain character strings of which semantics can be naturally stored as database values or has direct correspondence with database values. By building bilateral logical links between character strings in documents and corresponding database values, semantically rich queries are made expressible. We have introduced a new ADT, named "paratext," to model text which has links with database values. Paratexts are logically viewed as consisting of two parallel layers; on the "appearance" layer, ordinary text (i. e. a linear sequence of character strings) is placed, while the "reference" layer holds an array of OIDs and literals. Each OID or literal on the reference layer is associated with a contiguous substring of the appearance layer text, and represents the semantics of the associated substring. We have also designed domain-specific functions for this document model. Using the functions, we can express queries which go back and forth between the two layers. In structured documents, such character strings can appear in the whole content of logical elements, or as phrases inside logical elements. We also present frameworks for the implementation of the paratext ADT, and discuss how traditional full-text indexing techniques can be extended to support paratext.

This paper introduces a material management system for newspapers that was developed for The Yomiuri Shimbun. Material transferred to the system is stored in a material database and sent to terminals located in the related sections. The material can be processed effectively just by checking information on the terminals. Special requirements for this system will be discussed first in the paper, then problem-solving will be explored.

Internet users have become well acquainted with the World Wide Web (WWW) system, and WWW has become the most significant service on the Internet. In the near future, the importance of large scale hypermedia database systems based on WWW technologies is expected to continue to increace. The present study focuses on the issue of managing hyperlink integrity constraints on WWW like hypermedia database systems. After formally defining path existence constraint definitions(PEDs) using intuitive examples, we apply the notion of PEDs to represent hyperlink integrity constraints. Intuitively, a PED can be used to represent the following integrity constraint. If a reference path exists in a given database, then another corresponding reference path must also exist. An outline of a prototype hypermedia database system, AYATORI, which is based on the proposed model and under development, is also mentioned.

The advent of high-speed networks with quality of service guarantees, will enable the deployment of data-server distributed systems over wide-area networks. Most implementations of data-server systems have been over local area networks. Thus it is important, in this context, to study the performance of existing distributed data management protocols in the new networking environment, identify the performance bottlenecks and develop protocols that are capable of taking advantage of the high speed networking technology. In this paper, we examine and compare the scalability of the server-based two-phase locking protocol (s-2PL), and the group two-phase locking protocol (g-2PL). The s-2PL protocol is the most widely used concurrency control protocol, while the g-2PL protocol is an optimized version of the s-2PL protocol, tailored for high-speed wide-area network environments. The g-2PL protocol reduces the effect of the network latency by message grouping, client-end caching and data migration. Detailed simulation results indicate that g-2PL indeed scales better than s-2PL. For example, upto 28% improvement in response time is reported.

This paper presents a high-level test synthesis algorithm for operation scheduling and data path allocation. Data path allocation is achieved by a controllability and observability balance allocation technique which is based on testability analysis at register-transfer level. Scheduling, on other hand, is carried out by rescheduling transformations which change the default scheduling to improve testability. Contrary to other works in which the scheduling and allocation tasks are performed independently, our approach integrates scheduling and allocation by performing them simultaneously so that the effects of scheduling and allocation on testability are exploited more effectively. Additionally, since sequential loops are widely recognized to make a design hard-to-test, a complete (functional and topological) loop analysis is performed at register-transfer level in order to avoid loop creation during the integrated test synthesis process. With a variety of synthesis benchmarks, experimental results show clearly the advantages of the proposed algorithm.

Detecting security flaws is important in order to keep the database secure. A security flaw in object-oriented databases means that a user can infer the result of an unpermitted method only from permitted methods. Although a database management system enforces access control by an authorization, security flaws can occur under the authorization. The main aim of this paper is to show an efficient decision algorithm for detecting a security flaw under a given authorization. This problem is solvable in polynomial time in practical cases by reducing it to the congruence closure problem. This paper also mentions the problem of finding a maximal subset of a given authorization under which no security flaw exists.

The goal of this paper is to present algorithms for creating an optimized query plan for retrieving maximum information from multiple relations, using outerjoins. Especially we focus on conjunctive queries in the presence of predicates and foreign functions. We show first with examples that retrieving maximum information by integrating multiple relations requires outerjoin operators. The outerjoin is essential to prevent information loss that would be caused by the inner join. We also show that predicates and foreign functions are useful to mediate the discrepancy among the relations and to create arbitrary views. Outerjoins and foreign functions, together with predicates, make it difficult to create query processing plans since they impose restrictions on the order of query processing. The rest of this paper describes algorithms for creating such query processing plans for conjunctive queries expressed in extended Datalog. First, we show simple algorithms for creating query plans with outerjoins, but without predicates and foreign functions. We use the hypergraph representation of the relations to explain an optimized algorithm. Then, we show a more complex algorithm that works for query plans with predicates and foreign functions. In our algorithm, we create an initial expression graph whose nodes represent query processing units, including outerjoin, predicate and foreign function operators. Then, we convert the initial expression graph into an executable, optimized expression tree. This algorithm is implemented and deployed in a mediation system that integrates heterogeneous information sources.

We developed a PC cluster system which consists of 100 PCs as a test bed for massively parallel query processing. Each PC employs the 200 MHz Pentium Pro CPU and is connected with others through an ATM switch. Because the query processing applications are insensitive to the communication latency and mainly perform integer operations, the ATM connected PC cluster approach can be considered a reasonable solution for high performance database servers with low costs. However, there has been no challenge to construct large scale PC clusters for database applications, as far as the authors know. Though we employed commodity components as much as possible, we developed the DBMS itself, because that was a key component for obtaining high performance in parallel query processing, and there seemed no system which could meet our demand. On each PC node, a server program which acts as a database kernel is running to process the queries in cooperation with other nodes. The kernel was designed to execute pipelined operators and handle voluminous data efficiently, to achieve high performance on complex decision support type queries. We used the standard benchmark, TPC-D, on a 100 GB database to verify the feasibility of our approach, through comparison of our system with commercial parallel systems. As a whole, our system exhibited sufficiently high performance which was competitive with the current TPC-D top records, in spite of not using indices. For some heavy queries in the benchmark, which have high selectivity and joinability, our system performed much better. In addition, we applied transposed file organization to the database for further performance improvement. The transposed file organization vertically partitions the tuples, enabling attribute-by-attribute access to the relations. This resulted in significant performance improvement by reducing the amount of disk I/O and shifting the bottleneck to computation.

Support of collaborative work and management of spatio-temporal data has become one of the most interesting and important database applications, which is due to the tremendous progress of database and its surrounding technologies in the last decade. In this paper, we investigate the new generation database technologies that are needed to support such advanced applications. Because of the recent progress of virtual reality technology, virtual work spaces are now available. We examine a typical CSCW (Computer Supported Cooperative Work) fsystem to identify database problems that arise from it. We introduce typical approaches to database improvement based on the high-level view and the virtual reality technique. Also, in this paper, the following are introduced and discussed: the design and implementation of three- and four-dimensional spatio-temporal database systems, VRML (Virtual Reality Modeling Language) database systems, fast access methods to spatio-temporal data, and the interval-based approach to temporal multimedia databases.

This paper focuses on the problems how to organize and retrieve video data in an effective manner. First we identify several issues to be solved for the problems. Next, we overview our current research results together with a brief survey in the research area of video databases. We especially describe the following research results obtained by the the Japanese Ministry of Education under Grant-in-Aid for Scientific Research on Priority Area: "Advanced Databases" concerned with organization and retrieval of video data: Instance-Based Video Annotation Models, Self-Organization of Video Data, and A Query Model for Fragmentally Indexed Video.