In this paper we consider the k-clustering problem for a set S of n points p_i=(x_i) in the d-dimensional space with variance-based errors as clustering criteria, motivated from the color quantization problem of computing a color lookup table for frame buffer display. As the inter-cluster criterion to minimize, the sum of intra-cluster errors over every cluster is used, and as the intra-cluster criterion of a cluster S_j, |S_j|^α-1 Σ_{pi Sj} ||x_i - ^- x (S_j)||² is considered, where |||| is the L₂ norm and ^- x (S_j) is the centroid of points in S_j, i. e. , (1/|S_j|)Σ_{pi Sj} x_i. The cases of α=1,2 correspond to the sum of squared errors and the all-pairs sum of squared errors, respectively. The k-clustering problem under the criterion with α = 1,2 are treated in a unified manner by characterizing the optimum solution to the k-clustering problem by the ordinary Euclidean Voronoi diagram and the weighted Voronoi diagram with both multiplicative and additive weights. With this framework, the problem is related to the generalized primary shatter function for the Voronoi diagrams. The primary shatter function is shown to be O(n^O(kd)), which implies that, for fixed k, this clustering problem can be solved in a polynomial time. For the problem with the most typical intra-cluster criterion of the sum of squared errors, we also present an efficient randomized algorithm which, roughly speaking, finds an ε-approximate 2-clustering in O(n(1/ε)^d) time, which is quite practical and may be used to real large-scale problems such as the color quantization problem.

In static multiprocessor scheduling, heuristic algorithms have been widely used. Instead of gaining execution speed, most of them show non promising solutions since they search only a part of solution spaces. In this paper, we propose a scheduling algorithm using the genetic algorithm (GA) which is a well-known stochastic search algorithm. The proposed algorithm, named ordered-deme GA (OGA), is based on the multiple subpopulation GA, where a global population is divided into several subpopulations (demes) and each demes evolves independently. To find better schedules, the OGA orders demes from the highest to the lowest deme and migrates both the best and the worst individuals at the same time. In addition, the OGA adaptively assigns different mutation probabilities to each deme to improve search capability. We compare the OGA with well-known heuristic algorithms and other GAs for random task graphs and the task graphs from real numerical problems. The results indicate that the OGA finds mostly better schedules than others although being slower in terms of execution time.

In this paper, a new network structure called generalized Hierarchical Completely-Connected networks (HCCs) is proposed, and its properties and features are evaluated. Simple routing strategies for HCCs are also developed for shortest-paths routing algorithms. A set of HCCs constructed by the proposed method includes some conventional hierarchical networks, then it is called generalized one. The construction of an HCC starts from a basic block (a level-1 block) which consists of n nodes of constant degree. Then a level-h block for h 2 is constructed recursively by interconnecting any pair of macro nodes (n level-(h-1) blocks) completely. An HCC has a constant node-degree regardless of an increase in its size (the number of nodes). Furthermore, since an HCC has a hierarchically structured topology and the feature of uniformity, a wide variety of inter-cluster connections is possible. Evaluation results show that an HCC is suitable for very large computer systems.

File system buffers provide memory space for data being transferred to and from disk and act as caches for the recently used blocks, and the buffer manager usually reads ahead data blocks to minimize the number of disk accesses. However, if several multimedia files with different consumption rates are accessed simultaneously from the file system in which LRU buffer replacement strategy is used, the read-ahead blocks of the low rate file are unloaded from memory to be used for loading a data block of a high data rate file, therefore they should be reloaded again into memory from disk when these blocks are actually referenced. This paper proposes and implements a new buffer cache management scheme for a multimedia file system and analyzes the performance of the proposed scheme by modifying the file system kernel of FreeBSD. In this proposed scheme, initially, some buffers are allocated to each opened multimedia file, privately, then these buffers are reused for other data blocks of that file when they are loaded from the disk. Moreover, the number of private buffers allocated for the file is dynamically adjusted according to its data rate. An admission control scheme is also proposed to prevent opening of a new file which may cause overloads in the file system. Experimental results comparing proposed scheme with the original FreeBSD and a simple CTL-based model show that the proposed buffer management scheme could support the realtime play back of several multimedia files with various data rates concurrently without helps of a realtime CPU and disk scheduling.

Design patterns which Erich Gamma advocates is expected as an effective approach for the reuse of designs. So, design patterns are predicted to be used frequently in object-oriented software development. In such circumstance, tools to support applying design patterns to the design diagrams of the system under development are thought to be useful. This research develops Object-Oriented Pattern Applying Support tool OOPAS. It consists of a library of Gamma design patterns with very familiar examples and adrem explanation, and of a function to generate the correctly modified design diagrams of the application system when a design pattern was applied to evolve that system. Actually, these functions are installed in the structured object modeling environment SOME, which is an object-oriented design diagram editor made previously in our laboratory. This design diagram evolving function is formalized as a Join operation of the recursive graph. As a result of the evaluation experiment, the join operation can be applied to the almost of the twenty three Gamma design patterns excluding the six patterns such as Iterator and Command, which are stated at too abstract level to be represented by the design diagrams.

In a client-server system, when LRU or its variant buffer replacement strategy is used on both the client and the server, the cache performance on the server side is very poor mainly because of pages duplicated in both systems. This paper introduces a server buffer replacement strategy which uses a replaced page-id than a request page-id, for the primary information for its operations. The importance of the corresponding pages in the server cache is decided according to the replaced page-ids that are delivered from clients to the server, so that locations of the pages are altered. Consequently, if a client uses LRU as its buffer replacement strategy, then the server cache is seen by the client as a long virtual client LRU cache extended to the server. Since the replaced page-id is only sent to the server by piggybacking whenever a new page fetch request is sent, the operation to deliver the replaced page-id is simple and induces a minimal overhead. We show that the proposed strategy reveals good performance characteristics in diverse situations, such as single and multiple clients, as well as with various access patterns.

It has been proposed that the collaborative working environments have been created by the computing assistance for human behaviors with the instructions of related information and items. The purpose of this study is to propose the collaboration mechanism and the environments constrained by the roles. The basic principle at issue in this studies is that all members should behave autonomously, and behave collaboratively with understanding the surrounding environments. We have already presented the Distributed Collaborative Computing architecture called Noah that has the concept of field with tupple space. On this mechanism, we designed the role-based cooperative work environments on the collaboration and coordination mechanism. We applied this mechanism to the typical models in the industrial system's domain.

We propose a new method for generating visual stereo images from the common two dimensional images without 3D reconstruction. The major novel contributions of this report are in two aspects. First, we address the detection of dominant motion presented in the given scenes, for doing so we borrow phase shift theorem and calculate the inverse Fourier transform of cross-power spectrum to find the maximum peak value whose position can be used to decide motion parameters. Secondly, unlike most of researchers study the stereo vision to recover 3D information for modeling and rendering, we address the visual stereo image generation without 3D reconstruction by applying the computed motion parameters to make decision of selecting two given images to form a stereo pair for left eye and right eye respectively. The proposed approaches can be employed for applications such as navigation in a virtual environment.

An optimum representative-frames (r-frames) selection method using step-wise function approximation has been developed to provide automatic indexing for a video-query-agent (VQA) system. It uses dynamic programming to simultaneously select the r-frames and corresponding segment boundaries. Experiments showed that the approximation error of the selected r-frames was less than that of two conventional methods. Retrieval experiments using a feature-based image-search engine showed that the proposed method is more robust and effective than the two conventional methods. The proposed method was implemented in a VQA system and processing time was evaluated. The results showed that the processing time for indexing was shorter than that of the conventional method.

We propose a rough classification system using Hierarchical Learning Vector Quantization (HLVQ) for large scale classification problems which involve many categories. HLVQ of proposed system divides categories hierarchically in the feature space, makes a tree and multiplies the nodes down the hierarchy. The feature space is divided by a few codebook vectors in each layer. The adjacent feature spaces overlap at the borders. HLVQ classification is both speedy and accurate due to the hierarchical architecture and the overlapping technique. In a classification experiment using ETL9B, the largest database of handwritten characters in Japan, (it contains a total of 607,200 samples from 3036 categories) the speed and accuracy of classification by HLVQ was found to be higher than that by Self-Organizing feature Map (SOM) and Learning Vector Quantization methods. We demonstrate that the classification rate of the proposed system which uses multi-codebook vectors for each category under HLVQ can achieve higher speed and accuracy than that of systems which use average vectors.

In many of machine learning problems, it is essential to use not only the training data, but also a priori knowledge about how the world is constrained. In many cases, such knowledge is given in the forms of constraints on differential data or more specifically partial differential equations (PDEs). Neural networks with capabilities to learn differential data can take advantage of such knowledge and easily incorporate such constraints into the learning of training value data. In this paper, we report a structure, an algorithm, and results of experiments on neural networks learing differential data.

In this paper, we have proposed a new method for diffuse liver disease classification with sonogram, including the normal liver, hepatitis and cirrhosis, from a new point of view "scale. " The new system utilizes a multiscale analysis tool, called wavelet transforms, to analyze the ultrasonic liver images. A new set of features consisting of second order statistics derived from the wavelet transformed images is employed. From these features, we have found that the third scale is the representative scale for the classification of the considered liver diseases, and the horizontal wavelet transform can improve the representation of the corresponding features. Experimental results show that our method can achieve about 88% correct classification rate which is superior to other measures such as the co-occurrence matrices, the Fourier power spectrum, and the texture spectrum. This implies that our feature set can access the granularity from sonogram more effectively. It should be pointed out that our features are powerful for discriminating the normal livers from the cirrhosis because there is no misclassification samples between the normal liver and the cirrhosis sets. In addition, the experimental results also verify the usefulness of "scale" because our multiscale feature set can gain eighteen percent advantage over the direct use of the statistical features. This means that the wavelet transform at proper scales can effectively increase the distances among the statistical feature clusters of different liver diseases.

A generalized class of consecutive-k-out-of-n:G systems, referred to as Con/k^*/n:G systems, is studied. A Con/k^*/n:G system has n ordered components and is good if and only if k_i good consecutive components that originate at component i are all good, where k_i is a function of i. Theorem 1 gives an O(n) time equation to compute the reliability of a linear system and Theorem 2 gives an O(n²) time equation for a circular system. A distributed computing system with a linear (ring) topology is an example of such system. This application is very important, since for other classes of topologies, such as general graphs, planar graphs, series-parallel graphs, tree graphs, and star graphs, this problem has been proven to be NP-hard.

This article shows a Boolean Multivalued logical model of varying confirmation by observation of events in human inference and, as an introductory example, applies the model to solve Hempel's paradox of the ravens.