A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.
Kenji SATO Mikio HANAFUSA Akira NODA Atsutoshi ARAKAWA Toshiaki ASAHI Masayuki UCHIDA Osamu ODA
Pure green ZnTe light-emitting diodes (LEDs) were first realized reproducibly based on high quality ZnTe substrates and a simple thermal diffusion process. This success which overcomes the compensation effect in II-VI materials is due to the use of high quality p-type ZnTe single crystals with low dislocation densities of the level of 2000 cm-2 grown by the vertical gradient freezing (VGF) method and the suppression of as compensating point defects by low temperature annealing with covering the surface of the substrates by the deposition of n-type dopant, Al. The thermal diffusion coefficient and the activation energy of Al were determined from the pn interface observed by scanning electron spectroscopy (SEM). The formation of the intrinsic pn junctions was confirmed from the electron-beam induced current (EBIC) observation and I-V measurement. The bright 550 nm electroluminescence (EL) from these pn-junctions was reproducibly observed under room light at room temperature, with the lifetime exceeding 1000 hrs.
Hiroyasu ISHIKAWA Naoyuki NAKADA Masaharu NAKAJI Guang-Yuan ZHAO Takashi EGAWA Takashi JIMBO Masayoshi UMENO
Investigations were carried out on metalorganic-chemical-vapor-deposition (MOCVD)-grown strained AlGaN/ GaN/sapphire structures using X-ray diffratometry. While AlGaN with lower AlN molar fraction (< 0.1) is under the in-plane compressive stress, it is under the in-plane tensile stress with high AlN molar fraction (> 0.1). Though tensile stress caused the cracks in AlGaN layer with high AlN molar fraction, we found that the cracks dramatically reduced when the GaN layer quality was not good. Using this technique, we fabricated a GaInN multi-quantum-well (MQW) surface emitting diodes were fabricated on 15 pairs of AlGaN/GaN distributed Bragg reflector (DBR) structures. The reflectivity of 15 pairs of AlGaN/GaN DBR structure has been shown as 75% at 435 nm. Considerably higher output power (1.5 times) has been observed for DBR based GaInN MQW LED when compared with non-DBR based MQW structures.
Masakazu FURUICHI Atsuo OZAKI Kazuhiro ABE Katsuto NAKAJIMA Hidetoshi TANAKA
This paper proposes a Space-Time Object Model, an object oriented model that possesses space and time management mechanisms. The goal of this object model is to provide a common software infrastructure for implementing large-scale moving object simulations efficiently, such as car traffic simulations and disaster evacuation simulations, using a direct mapping scheme on a parallel and distributed computing environment. In this object model, the software infrastructure provides two principal functions, "Space Management" and "Time Management," which allows programmers to focus on application programming instead of parallel programming. Although there are several known infrastructure software, which provide the environment needed to develop and execute parallel and distributed simulations, they only provide a "Time Management" mechanism. In this paper, we present a Space-Time Object Model and an overview of a program called OSim, which is an implementation of the Space-Time Object Model. Then, we demonstrate the applicability and efficiency of this model by introducing the overview and evaluation results of a parallel car traffic simulation system using OSim.
Ji-Hoon KANG Ki-Hyung HONG Kyu-Young WHANG Jung-Wan CHO
In this paper, we consider linearization of nonlinear datalog programs with multiple bilinear rules and multiple linear rules. If a nonlinear program can be linearized, it is possible to process queries on the program efficiently by using well-known cost-effective techniques for linear programs. We define a transformation, called Right-Linear-First (RLF) transformation, for linearizing such nonlinear programs. A nonlinear program is RLF-linearizable if it is logically equivalent to its RLF-transformed program. We present three sufficient conditions, called LCR-consistency, LCRN1-consistency, and LCRN2-consistency, for identifying such RLF-linearizable programs. These conditions can be tested in polynomial time. Our work presented in this paper extends the work on ZYT-linearizability in a sense that RLF-linearizability considers multiple bilinear rules with multiple linear rules.
Vincent van de LAAR Kiyoharu AIZAWA
This paper describes a scheme to capture a wide-view image using a camera setup with uncalibrated cameras. The setup is such that the optical axes are pointed in divergent directions. The direction of view of the resulting image can be chosen freely in any direction between these two optical axes. The scheme uses eight-parameter perspective transformations to warp the images, the parameters of which are obtained by using a relative orientation algorithm. The focal length and scale factor of the two images are estimated by using Powell's multi-dimensional optimization technique. Experiments on real images show the accuracy of the scheme.
Vakhtang LASHKIA Shun'ichi KANEKO Stanislav ALESHIN
In this paper, we present a class of combinatorial-logical classifiers called test feature classifiers. These are polynomial functions that can be used as pattern classifiers of binary-valued feature vectors. The method is based on so-called tests, sets of features, which are sufficient to distinguish patterns from different classes of training samples. Based on the concept of test we propose a new distance-based test feature classifiers. To test the performance of the classifiers, we apply them to a well-known phoneme database and to a textual region location problem where we propose a new effective textual region searching system that can locate textual regions in a complex background. Experimental results show that the proposed classifiers yield a high recognition rate than conventional ones, have a high ability of generalization, and suggest that they can be used in a variety of pattern recognition applications.
Hiroyuki NARA Shuichi INO Tohru IFUKUBE
The sense of equilibrium is influenced by various factors of visual stimulation, especially far peripheral vision and a motion parallax. An investigation of these two factors was made in order to apply the findings to construct a rehabilitation method for equilibrium disorders. From the experimental results, it was found that the center of gravity for the subjects was greatly affected by both far peripheral vision and the motion parallax. This finding suggests how visual stimulation should be displayed to control the sense of balance in the case of equilibrium disorders.
In this paper, we propose a method for detecting conserved domains from a set of amino acid sequences that belong to a protein family. This method detects the domains as follows: first, generate fixed-length subsequences from the sequences; second, construct a weighted graph that connects any two of the subsequences (vertices) having higher similarity than a pre-defined threshold; third, search for the maximum-density subgraph for each connected component of the graph; finally, explore conserved domains in the sequences by combining the results of the previous step. From the performance results obtained by applying the method to several protein families that have complex conserved domains, we found that our method was able to detect those domains even though some domains were weakly conserved.
Noritaka OSAWA Toshitsugu YUBA
This paper proposes and evaluates a character or symbol code system called EPICS for multilingual information processing. EPICS integrates a variable-length coding system using 16-bit units and a smart virtual machine. EPICS enhances the interchangeability of data. The variable-length coding system provides a huge code space. This huge space can include not only standardized code sets but also non-standardized codes of ancient symbols and user-specific symbols. The smart virtual machine executes inputs as instructions and is dynamically customizable. It allows us to define and modify instructions during runtime and provides us with customization facilities. Customization facilities can be used to specify a sorting order and normalization. Customization also makes it possible for an information producer (sender) to express his intentions or annotations in data and for an information consumer (receiver) to process the data depending on his needs. Moreover, customization enables one to send compressed data and decompression program fragments incrementally and efficiently without predefined decompression algorithms.
Yoshiyuki SHINKAWA Masao J. MATSUMOTO
Software Composition is one of the major concerns in component based software development (CBSD). In this paper, we present a formal approach to construct software systems from requirements models using available components. We focus on the knowledge resides in the requirements and the components in order to deal with those heterogeneous concepts. This approach consists of three steps. The first step is selecting adaptable components to the requirements model. The requirements and the components are transformed into the form of Σ algebra, and the component adaptability is evaluated by Σ homomorphism. Rough Set Theory (RST) is used to make carriers of two Σ algebras common, which are derived from the requirements and the components. The second step is identifying the control structure of the requirements. Decision tables are used for representing the knowledge on the requirements, and RST is used to optimize the control structure. The third step is to implement the control structure as glue codes which would perform the components appropriately. This approach mainly focuses on enterprise back-office applications in this paper, however, it can be easily applied to other domains, since it assumes the requirements to be expressed in Colored Petri Nets (CPN), and CPN can express various problem domains other than enterprise back-office applications.
Hideki TODE Hiroki YAMAUCHI Hiromasa IKEDA
An efficient scheme for establishing the multicast-path on ATM network is to configure the tree-shaped path via several intermediate copy nodes. This scheme needs the multicast routing control. Thus, restricting the number of copy nodes was proposed since it make this control fast and simple. However, if restricted number of copy nodes is fixed in the network design, multicast traffic will concentrate around copy nodes, and as a result, the possibility of occurring congestion will be higher. In our research, we permit restricted number of nodes as intermediate nodes which branch the tree-shaped path at routing, and name this permission "copy-token. " Namely, the node which has "copy-token" is defined as the copy node. Our research purpose is to distribute the multicast traffic by adaptively allocating "copy-token" to nodes which satisfy the conditions of both the priority for multicasting such as lower offered load and the geographical distribution at the same time. Finally, we evaluate the performance of our proposed routing scheme on the blocking probability through computer simulations.
Younggeun HAN Chang-Seok KIM Un-Chul PAEK Youngjoo CHUNG
We will discuss performance optimization of strain and temperature sensors based on long period fiber gratings (LPFGs) through control of the temperature sensitivity of the resonant peak shifts. Distinction between the effects of strain and temperature is a major concern for applications to communication and sensing. This was achieved in this work by suppressing or enhancing the temperature sensitivity by adjusting the doping concentrations of GeO2 and B2O3 in the core or cladding. The LPFGs were fabricated with a CO2 laser by the mechanical stress relaxation and microbending methods. The optimized temperature sensitivities were 0.002 nm/ for the suppressed case and 0.28 nm/ for the enhanced case, respectively. These LPFGs were used for simultaneous measurement of strain and temperature. The result indicates the rms errors of 23 µstrain for the strain and 1.3 for the temperature.
The two dimensional mesh is widely considered to be a promising parallel architecture in its scalability. In this architecture, processors are naturally placed at intersections of horizontal and vertical grids, while there can be three different types of communication links: (i) The first type is the most popular model, called a mesh-connected computer: Each processor is connected to its four neighbours by local connections. (ii) Each processor of the second type is connected to a couple of (row and column) buses. The system is then called a mesh of buses. (iii) The third model is equipped with both buses and local connections, which is called a mesh-connected computer with buses. Mesh routing has received considerable attention for the last two decades, and a variety of algorithms have been proposed. This paper provides an overview of lower and upper bounds for algorithms, with pointers to the literature, and suggests further research directions for mesh routing.
Takao ASANO Kenichiro IWAMA Hideyuki TAKADA Yoshiko YAMASHITA
For NP-hard combinatorial optimization problems, approximation algorithms with high performances have been proposed. In many of these algorithms, mathematical programming techniques have been used and proved to be very useful. In this survey, we present recent mathematical programming techniques as well as classic fundamental techniques, by showing how these techniques are used in designing high-quality approximation algorithms for NP-hard combinatorial optimization problems.
Koichi IIYAMA Takahiro MAEDA Saburo TAKAMIYA
We describe FMCW reflectometry for characterization of long optical fibers by using an external-cavity laser diode as a light source. Since the optical path difference between the reference beam and the reflected beam from the optical fiber under test is much longer than the coherence length of the light source, the reference and the reflected beams are phase-decorrelated. As a result, the beat spectrum between the reference and the reflected beams is measured. In the phase-decorrelated FMCW reflectomety, the spatial resolution is enhanced by narrowing the spectral linewidth of the light source and increasing the repetition frequency of the optical frequency sweep as well as increasing the chirping range of the optical frequency sweep. In the experiments, an external-cavity DFB laser is used as a narrow linewidth light source, and the optical frequency is swept by minute modulation of the external cavity length. Long single mode optical fibers are characterized, and the maximum measurement range of 80 km is achieved, and the spatial resolutions of 46 m, 100 m and 2 km are achieved at 5 km, 11 km and 80 km distant, respectively. The Rayleigh backscattering is clearly measured and the propagation loss of optical fiber is also measured. The optical gain of an erbium-doped optical fiber amplifier (EDFA) is also estimated from the change in the Rayleigh backscattering level in the optical fiber followed after the EDFA.
Tetsu SOH Kouji WADA Osamu HASHIMOTO
An epoxy-modified urethane rubber mixed with carbon particles is now chosen as the millimeter-wave absorber material in our study. The absorption characteristics of the absorber is measured under temperature changes. The weatherability of our absorber is also clarified based on absorption characteristics, thickness and hardness of the sample. As a result of the temperature characteristics of the absorber, the difference of the maximum absorption frequency under temperature changes is about 1 GHz, however the absorption of 20 dB or more is obtained between 54 and 58 GHz. The result of accelerated artificial exposure test is that 2.8% of the thickness of our sample is shrunk after 1000 hour exposure, and the hardness of rubber is hardened with increasing test time. It is also confirmed that the deterioration of the absorption ranges from 1 to 3 dB, although the absorption of about 20 dB is kept at the frequency range. As a consequence, it is confirmed that the wave absorber using the epoxy-modified urethane rubber mixed with carbon particles has good weatherability including our desired temperature characteristics, and it is suitable for outdoor use.
Mutsumi KIMURA Tokuro OZAWA Satoshi INOUE
The pseudo-lattice method has been developed for dynamic 3-D liquid-crystal director simulation in thin-film-transistor liquid-crystal displays. Its feature is that the equation of motion of the director is not formularized from the real-lattices, but from the pseudo-lattices organized between the real-lattices. The director on the pseudo-lattice is calculated from the real-lattices by insertion. The objective is to simulate the continuous nematic symmetry correctly and to reduce time and memory needed for the calculation. Especially in this paper, the pseudo-lattice method is explained in detail. Moreover, experiments have been done, and the simulated behavior and location of the bright line, which is caused by the distortion of the director profile, were confirmed to be the same as the actual ones. In particular, the movement and elimination process of the bright line were simulated for the first time.
A directly modulated LED or SLD (super luminescent diode) is attractive for low-cost lightwave systems such as access networks. This letter experimentally studies a directly modulated SLD followed by a gain-saturated semiconductor optical amplifier (SOA), and shows that the modulation rate is expanded in effect by the use of the gain-saturated SOA. This results from the shortened response time of the SLD due to the ASE light from the SOA and a level-equalizing effect in the gain-saturated SOA.
This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.