In this paper, we present an efficient and accurate decision tree building method which resolves some problems and reduces the overhead of database scanning in the CAM method. We also build a structure named class-rooted FP-tree. From our simulation, we show that the performance of the proposed class-rooted FP-tree mining method is better than the CAM methods in terms of storage usage, the times of database scanning and classification accuracy.

Space-filling curves, particularly, Hilbert curves, have been extensively used to maintain spatial locality of multi-dimensional data in a wide variety of applications. A window query is an important query operation in spatial (image) databases. Given a Hilbert curve, a window query reports its corresponding orders without the need to decode all the points inside this window into the corresponding Hilbert orders. Given a query window of size p×q on a Hilbert curve of size T×T, Chung et al. have proposed an algorithm for decomposing a window into the corresponding Hilbert orders, which needs O(n log T) time, where n=max(p,q). By employing the properties of Hilbert curves, the authors present an efficient algorithm, named as Quad-Splitting, for decomposing a window into the corresponding Hilbert orders on a Hilbert curve without individual sorting and merging steps. Although the proposed algorithm also takes O(n log T) time, it does not perform individual sorting and merging steps which are needed in Chung et al.'s algorithm. Therefore experimental results show that the Quad-Splitting algorithm outperforms Chung et al.'s algorithm.

Genomic sequence databases, like GenBank, EMBL, are widely used by molecular biologists for homology searching. Because of the increase of the size of genomic sequence databases, the importance of indexing the sequences for fast queries grows. In this paper, we propose a new index structure, ACGT-Words tree, for efficiently support query processing in genomic databases. We define the concept of words which is different from the word definition given in the word suffix tree, and separate the DNA sequences stored in the database and in the query sequence into distinct words. Our approach does not store all of the suffixes in the database sequences. Therefore, we need less space than the suffix tree approach. We also propose an efficient search algorithm to do the sequence match based on the ACGT-Words tree index structure. Therefore, we could take less time to finish the search than the suffix array approach. Moreover, our approach avoids the missing cases occurring in the word suffix tree. The simulation results show that our ACGT-Words tree outperforms the suffix tree and the suffix array in terms of storage and processing time, respectively

In video databases, each video contains temporal and spatial relationships between content objects. One of the well-known video indexing strategies is the 3D C-string strategy. However, it cannot deal with the condition that an object appears and then disappears for more than one time. To solve this problem, in this paper, we propose an indexing strategy, called temporal UID Matrix1. Based on the original 13 spatial relationships proposed by 2D C-string and our three new spatial relationships, we can derive the temporal relationships from the sequence of spatial relationships. Therefore, in our proposed strategy, although we build only index for spatial relationships, and we still can answer the video queries, i.e., spatial, temporal, and spatio-temporal queries. From our simulation study, we show that our proposed strategy is more efficient for video searching than the 3D C-string strategy.

To efficiently support continuous retrieval for continuous media, many approaches based on the striping strategy that is implemented on a multi-disk drive have been proposed. However, the striping strategy only considers the fixed bandwidth of an object. Moreover, the aggregate bandwidth of the multi-disk drive is determined when the object is striped. Furthermore, for some applications, such as self-learning systems, users may quickly browse some familiar objects while they will slowly scan some unfamiliar objects. Therefore, we propose an efficient approach to supporting continuous retrieval with dynamic required bandwidths without reorganizing the whole striped object. From the performance study, we observe that the number of subobjects that must be moved is proportional to the initial required bandwidth and the current required bandwidth.

The goal of dynamic hashing is to design a function and a file structure that allow the address space allocated to the file to be increased and reduced without reorganizing the whole file. We propose a new scheme for dynamic hashing in which the growth of a file occurs at a rate of n+k/n per full expansion, where n is the number of pages of the file and k is a given integer constant which is smaller than n, as compared to a rate of two in linear hashing. Like linear hashing, the proposed scheme (called linear spiral hashing) requires no index; however, the proposed scheme may or may not add one more physical page, instead of always adding one more page in linear hashing, when a split occurs. Therefore, linear spiral hashing can maintain a more stable performance through the file expansions and have much better storage utilization than linear hashing. From our performance analysis, linear spiral hashing can achieve nearly 97 percent storage utilization as compared to 78 percent storage utilization by using linear hashing, which is also verified by a simulation study.

One of the most important challenges in a video-on-demand system is to support interactive browsing functions such as fast forward and fast backward. There are several possible approaches to implementing these functions which require additional resources. Although the segment-sampling strategy proposed by Chen et al. (1995) can support browsing at any desired speed without any additional resource, this strategy only considers the display of a single continuous object at a time. In this paper, we propose a new strategy, called the multi-sampling strategy, which generalizes the approach of the segment-sampling strategy so that it can support continuous display of multiple objects at different display speed rates, simultaneously, without any additional resource.

In this paper, we propose an efficient conflict-resolution approach based on the multi-disk architecture for the insertion/deletion operations on continuous media that are split up into blocks and placed in various locations on the disk, without reorganizing the whole data. When a new subobject is inserted after subobject i, it will be assigned with an identification number (i + 1) and be inserted into a disk in which the retrieval of the new subobject does not conflict with the retrieval of any other subobject, where a conflict means a pair of two consecutive subobjects that are stored in the same disk have to be retrieved simultaneously. However, a new conflict on the same disk may occur since all the identification numbers of subobjects after subobject i are increased by one. Only when such a new conflict occurs, one movement operation is required, so does the case of a deletion operation. Moreover, to reduce those additional movement cost, a deferring approach is proposed at the cost of an additional buffer. In this approach, n data insertions are deferred and stored in a buffer. Then, the system starts to insert those data after an optimal insertion sequence is determined. Based on this approach, two strategies are proposed: the conflict-resolved-first-deferring strategy (the CRFD strategy) and the conflict-resolved-last-deferring strategy (the CRLD strategy). From our performance analysis, we will prove that the CRLD strategy with an insertion sequence according to the ascending order of identification numbers is an optimal strategy based on the proposed deferring approach.

In an active database system, rules are used to monitor and respond to events that happen inside the database. This paper presents the implementation of an active database system called RBE. The system loosely couples an OPS5 production system and an INGRES database management system to efficiently monitor databases on complex conditions. In this system, atable-based Rule-By-Example (RBE) language, is designed. The internal representations of the RBE rule language are production rules; therefore, rules can be stored, managed and tested efficiently by using the well-developed pattern matching algorithm in a production system. In other words, the system applies a production system and a special production system program to the task of query rewrite trigger processing. Moreover, a user-friendly interface is used to loosely couple the OPS5 rule system with the INGRES DBMS. The architecture used in this system shows the applicability of constructing an active database system by integrating any production system and any database system. Moreover, the proposed technique could be used as an implementation method for a query-rewrite rule system inside a DBMS server, not using a layered approach. © 1997 by John Wiley & Sons, Ltd.

Proposes a generalized approach for designing a class of dynamic hashing schemes which require no index and have the growth of a file at a rate of (n+1)/n per full expansion, where n is the number of pages of the file, as compared to a rate of 2 in linear hashing. Based on this generalized approach, we derive a new dynamic hashing scheme called alternating hashing, in which, when a split occurs in page k, the data records in page k are redistributed to page k and page (k+1), or to page k and page (k-1), according to whether the value of level d is even or odd, respectively (d is defined as the number of full expansions that have happened so far). From our performance analysis, given a fixed load control, the proposed scheme can achieve nearly 97% storage utilization, as compared to 78% by using linear hashing.

To verify the logical correctness of communication protocols, protocol verification should be invoked in the design phase. In this paper, we propose a new communicating finite state machine (CFSM)-based verification method, which is called reverse protocol verification. By analyzing the properties of deadlock error, unspecified reception error and channel overflow error, some candidate erroneous global states are generated. Then, each candidate global state is checked whether there is a path, i.e. a global state sequence, which can connect to the original initial global state. If there is a path, then the candidate global state is really an erroneous global state and the protocol under designing does have some logical errors; alternatively, if there is no candidate global state or none of the candidate global states has a path, then the protocol is error free. Based on the reverse method, an incremental protocol specification system (IPSS) has been developed on SUN SPARC workstations. Usage and applications of IPSS are also presented in this paper.

A multimedia document is composed of different media objects. ISO's Open Document Architecture (ODA) proposes a standard multimedia document model. However, the current ODA profile only includes static media, e.g. text, geometric graphics and images. Because the future multimedia documents not only include static media but also continuous media, e.g. video and audio, continuous media document parts should be added to have a complete multimedia document model. In this paper, we propose a multimedia document model, which is derived from ODA's concept. The proposed model is based on the object-oriented approach. Objects in the proposed document model are divided into two types: data objects and pseudo objects. Data objects are data structures of a document; pseudo objects are used to manage data objects. Based on the proposed model, a multimedia document authoring and presenting system (MMDS) is also developed on SUN SPARC workstations using the Solaris 2.X operating system

A hybrid approach to mutual exclusion is proposed to minimize both message traffic and time delay at the same time. A hybrid mutual exclusion algorithm using the release local sites first mode, the requesting group semantics, and the requesting sequence 1324 (i.e., local competition followed by global competition) is found to be an efficient way to control the interaction. This hybrid algorithm uses M. Singhal's (1989) algorithm as the local algorithm and M. Maekawa's (1985) algorithm as the global algorithm. Compared to Maekawa's algorithm, which needs 3 square root N. . .5 square root N messages but two time units delay between successive executions of the critical section (where N is the number of sites in the system), the proposed hybrid algorithm can reduce message traffic by 55% and time delay by 32% at the same time. Furthermore, when a distributed system exhibits locality of requests, the proposed hybrid algorithm can achieve even better performance.>

A fault-tolerant mutual exclusion algorithm for distributed systems is presented. The algorithm uses a distributed queue strategy and maintains alternative paths at each site to provide a high degree of fault tolerance. However, owing to these alternative paths, the algorithm must use reverse messages to avoid the occurrence of directed cycles, which may form when the direction of edges is reversed after the token passes through. If there is no alternative path, the total number of the messages exchanged is O (2*log N) in light traffic and two messages in heavy traffic; however, in this case the system cannot tolerate even a single communication link or site failure. If there are alternative paths between sites, the system can achieve a higher degree of fault tolerance at the expense of increased message traffic (owing to reverse messages). Thus, there is a tradeoff between efficiency and reliability, and a system can be designed to balance these two criteria properly. A recovery procedure for restoring a recovering site consistently into the system is also presented.>

A computer-aided protocol design system based on the OPS5 production system approach is proposed. Communication rules (state transitions) are specified as triples of object-attribute-value and the modeling of state transitions is specified by production rules. An incremental validation algorithm to facilitate protocol design is also presented. Based on a globally shared dataspace (working memory) in which different types and levels of information are all represented in a uniform structure, the OPS5 production system integrates both rule-based and procedure-based computations. Using this characteristic, the machine-dependent part can be abstractly specified through external procedure calls, the details of which can be coded in a procedure language until the implementation phase. Since computations in OPS5 are based on pattern matching, all of the attributes of elements that are in production rules or in external procedure calls can act as data templates for generic data types. This capability enhances the generic specification that allows different realizations for various implementation environments.>