Semistructured data has no a-priori schema information, which causes some problems such as inefficient storage and query execution. To cope with such problems, extracting schema information from semistructured data has been an important issue. However, in most cases optimal schema information cannot be extracted efficiently, and few efficient approximation algorithms have been proposed. In this paper, we consider an approximation algorithm for extracting "typical" classes from semistructured data. Intuitively, a class C is said to be typical if the structure of C is "similar" to those of "many" objects. We present the following results. First, we prove that the problem of deciding if a typical class can be extracted from given semistructured data is NP-complete. Second, we present an approximation algorithm for extracting typical classes from given semistructured data, and show a sufficient condition for the approximation algorithm to run in polynomial time. Finally, by using extracted classes obtained by the approximation algorithm, we propose a polynomial-time algorithm for constructing a set R of classes such that R covers all the objects to form a database schema.

In this paper, we investigate the blocking characteristics of all-optical WDM (Wavelength-Division Multiplexing) networks under distributed wavelength assignment policies. For assigning wavelengths in a distributed manner, we consider two algorithms: random and locally-most-used algorithm. For a random wavelength assignment policy, we develop new blocking models of unidirectional/bidirectional ring networks based on the M/M/c/c queueing models under uniform/nonuniform traffic conditions. These models are shown to be more accurate than the previous blocking models since our approach considers the large traffic correlation among links in ring networks. We also analyze the blocking performance of the locally-most-used algorithm by comparing with that of the globally-most-used algorithm in fixed routing networks. We show that our analysis models match well with the simulation results in ring and mesh networks. Through the comparison with the previous centralized/distributed algorithms, it is demonstrated that the distributed locally-most-used algorithm is computationally efficient with good blocking performance.

For physically disabled persons, the conventional computer keyboard is insufficient as a useable communication device. In this paper, Morse code is selected as a communication adaptive device for persons with impaired hand coordination and dexterity. Morse code is composed of a series of dots, dashes, and space intervals. Each element is transmitted by sending a signal for a defined length of time. Maintaining a stable typing rate by the disabled is difficult. To solve this problem, a suitable adaptive automatic recognition method, which combines a variable degree variable step size LMS algorithm with a learning vector quantization method, was applied to this problem in the present study. The method presented here is divided into five stages: space recognition, tone recognition, learning process, adaptive processing, and character recognition. Statistical analyses demonstrated that the proposed method elicited a better recognition rate in comparison to alternative methods in the literature.

New good convolutional codes with optimal free distance are tabulated for the number of memories M 22 and rate R=1/2, which were selected based on the criterion of minimizing the decoding error rate and bit error rate. Furthermore, for R=1/3, 1/4 and M 13, we give the new good codes and make clear the existance of the codes with minimum free distance which achieve to Heller's upper bound for M 16.

Many new multimedia applications involve multiple dynamically changing participants, have stringent source-to-end delay requirements, and consume large amounts of network resources. A conventional algorithm that allows "two coming paths," where nodes in a multicast tree transmit several identical data flows, is therefore not practical. We have developed an algorithm for delay-constrained dynamic routing. This algorithm uses a QoS label to prevent the occurrence of "two coming paths," and can construct an efficient multicast tree for any traffic volume. The proposed algorithm was superior to conventional routing algorithms in terms of cost when nodes were added to or removed from the multicast group during a steady-state simulation.

We study the performance of oblivious routing algorithms that follow minimal (shortest) paths, referred to as minimal oblivious routing algorithms in this paper, using competitive analysis on a d-dimensional, N = 2d-node hypercube. We assume that packets are injected into the hypercube arbitrarily and continuously, without any (e.g., probabilistic) assumption on the arrival pattern of the packets. Minimal algorithms reduce the total load in the network in the first place and they preserve locality. First we show that the well known deterministic oblivious routing algorithm, namely, the greedy routing algorithm, has competitive ratio Ω(N1/2). Then we show a problem lower bound of Ω(Nlog 2 (5/4)/log5 N). We also give a natural randomized minimal oblivious routing algorithm whose competitive ratio is close to the problem lower bound we provide.

This paper evaluates the security of the block cipher E2 against truncated differential cryptanalysis. We show an algorithm to search for effective truncated differentials. The result of the search confirmed that there exist no truncated differentials that lead to possible attacks for E2 with more than 8 rounds. The best attack breaks an 8-round variant of E2 with either IT-Function (the initial transformation) or FT-Function (the final transformation) using 294 chosen plaintexts. We also found the attack which distinguishes a 7-round variant of E2 with IT- and FT-Functions from a random permutation using 291 chosen plaintexts.

This paper is, in half part, written in review nature, and presents recent theoretical results on linear-filtering and -prediction problems of nonstationary Gaussian processes. First, the basic concepts, signal and noise, are mathematically characterized, and information sources are defined by linear stochastic differential equations. Then, it is shown that the solution to a conventional problem of filtering or prediction of a nonstationary time series is, in principle, reducible to a problem, of which solution is given by Kalman-Bucy's theory, if one can solve a problem of finding the canonical representation of a Gaussian process such that it has the same covariance functions as those of the time series under consideration. However, the problem mentioned above is left open. Further, the problem of time-frequency analysis is discussed, and physical realizability of the evolutionary, i.e., the online, spectral analyzer is shown. Methods for dealing with differential operators are presented and their basic properties are clarified. Finally, some of related open problems are proposed.

The goal of this paper is to describe a practical and efficient algorithm for computing in the Jacobian of a large class of algebraic curves over a finite field. For elliptic and hyperelliptic curves, there exists an algorithm for performing Jacobian group arithmetic in O(g2) operations in the base field, where g is the genus of a curve. The main problem in this paper is whether there exists a method to perform the arithmetic in more general curves. Galbraith, Paulus, and Smart proposed an algorithm to complete the arithmetic in O(g2) operations in the base field for the so-called superelliptic curves. We generalize the algorithm to the class of Cab curves, which includes superelliptic curves as a special case. Furthermore, in the case of Cab curves, we show that the proposed algorithm is not just general but more efficient than the previous algorithm as a parameter a in Cab curves grows large.

In this paper we propose a mobile positioning method based on a recursive least squares (RLS) algorithm for suppressing the non-line of sight (NLOS) effects in cellular systems. The proposed method finds the position of a mobile station from TOAs measured by three BSs. Simulation results show that the proposed method has a fast convergence time and greatly reduces the positioning error especially in NLOS situations. Thus it is expected that the proposed method can be effectively used in a dense urban environment.

Watermarking techniques proposed up to now have some measure of robustness against non-geometrical alteration, however, most of them are not so robust against geometrical alteration. As also for video watermarking, small translation, scaling, rotation, affine transformation can be effective attacks on the watermark. In this paper, we propose an image correction scheme for video watermarking extraction. This scheme embeds 'patchwork' into digital video data for detection of positions, and corrects the images attacked by geometrical alteration on the basis of the detected positions. We also show the simulation results of applying proposed scheme to the conventional watermarking technique.

In this paper, first, we propose two of the high rate methods based on Morii-Kasahara cryptosystem. Method A-I is based on Schalkwijk algorithm. Method A-II is based on the extended Schalkwijk algorithm, which is proposed in this paper. We then show that these proposed methods can yield a higher rate compared with ElGamal cryptosystem. Next, we also propose two methods for a fast encryption by dividing the message vector into several pieces. Regarding each of the divided vectors as an index, we can realize a fast transformation of the index into a limited weight vector. In Method B-I, Schalkwijk algorithm is used for the fast transformation. In Method B-II, the fast transformation is realized with the method of table-lookup. These methods can realize a faster encryption than Method A-I, Method A-II and Morii-Kasahara cryptosystem. The security of these proposed methods are based on the security of Morii-Kasahara cryptosystem.

Recently, Boneh et al. proposed an interesting algorithm for factoring integers, the so-called LFM (Lattice Factoring Method). It is based on the techniques of Coppersmith and Howgrave-Graham, namely, it cleverly employs the LLL-algorithm. The LFM is for integers of the form N = pr q, and is very effective for large r. That is, it runs in polynomial time in log N when r is on the order of log p. We note that for small r, e.g. N =pq, p2q, it is an exponential time algorithm in log N. In this paper, we propose a method for speeding up the LFM from a practical viewpoint. Also, theoretical considerations and experimental results are provided that show that the proposed algorithm offers shorter runing time than the original LFM.

This paper introduces a generalized cyclic convolution which can be implemented via the conventional cyclic convolution system by the discrete Fourier transform (DFT) with pre-multiplication for the input and post-multiplication for the output. The generalized cyclic convolution is applied for computing a negacyclic convolution. Comparison shows that the proposed implementation is more efficient and simpler in structure than other methods. The modified Fermat number transform (MFNT) is known to be useful for computing a linear convolution of integer-valued sequences. The generalized cyclic convolution is also applied for generalizing the linear convolution system by MFNT, and easing the signal length restriction imposed by the system.

An automated method for cryptanalysis of DFT-based analog speech scramblers is presented through statistical estimation treatments. In the proposed system, the ciphertext only attack is formulated as a combinatorial optimization problem leading to a search for the most likely key estimate. For greater efficiency, we also explore the benefits of genetic algorithm to develop an estimation method which takes into account the doubly stochastic characteristics of the underlying keyspace. Simulation results indicate that the global explorative properties of genetic algorithms make them very effective at estimating the most likely permutation and by using this estimate significant amount of the intelligibility can be recovered from the ciphertext following the attack on DFT-based speech scramblers.

A minimum classification error formulation based on genetic algorithm is proposed for discriminative training of the bigram language model. Results of Chinese dialect identification were reported which demonstrate performance improvement with use of the genetic algorithm over the generalized probabilistic descent algorithm.

The maximum likelihood estimate of a mixture model is usually found by using the EM algorithm. However, the EM algorithm suffers from a local optima problem and therefore we cannot obtain the potential performance of mixture models in practice. In the case of mixture models, local maxima often have too many components of a mixture model in one part of the space and too few in another, widely separated part of the space. To escape from such configurations we proposed a new variant of the EM algorithm in which simultaneous split and merge operations are repeatedly performed by using a new criterion for efficiently selecting the split and merge candidates. We apply the proposed algorithm to the training of Gaussian mixtures and the dimensionality reduction based on a mixture of factor analyzers using synthetic and real data and show that the proposed algorithm can markedly improve the ML estimates.

This paper presents an O(n2)-time algorithm for constructing two edge-disjoint paths connecting two given pairs of vertices in a given tournament graph. It improves the time complexity of a previously known O(n4)-time algorithm.

We call a network an anonymous network, if each vertex of the network is given no ID's. For distributed algorithms for anonymous networks, solvable problems depend strongly on the given initial conditions. In the past, initial conditions have been investigated, for example, by computation given the number of vertices as the initial condition, and in terms of what initial condition is needed to elect a leader. In this paper, we study the relations among initial conditions. To achieve this task, we define the relation between initial conditions A and B (denoted by A B) as the relation that some distributed algorithm can compute B on any network satisfying A. Then we show the following property of this relation among initial conditions. The relation is a partial order with respect to equivalence classes. Moreover, over initial conditions, it induces a lattice which has maxima and minima, and contains an infinite number of elements. On the other hand, we give new initial conditions k-LEADER and k-COLOR. k-LEADER denotes the initial condition that gives special condition only to k vertices. k-COLOR denotes the initial condition that divides the vertices into k groups. Then we investigate the property of the relation among these initial conditions.

The signed regressor algorithm, a variation of the least mean square (LMS) algorithm, is characterized by the estimation way of using the clipped reference signals, namely, its sign (). This clipping, equivalent to quantizing the reference signal to 1, only increases the estimation error by about 2 dB. This paper proposes to increase the number of the quantization steps to three, namely, 1 and 0, and shows that the 'tri-quantized-x' normalized least mean square (NLMS) algorithm with three quantization steps improves the convergence property.