A rectangle-of-influence drawing of a plane graph G is a straight-line planar drawing of G such that there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of any edge. In this paper, we show that any given 5-connected plane graph G with five or more vertices on the outer face has a rectangle-of-influence drawing in an integer grid such that W + H ≤ n - 2, where n is the number of vertices in G, W is the width and H is the height of the grid.
Yi XIONG Senanayake THILAK Yu YONEZAWA Jun IMAOKA Masayoshi YAMAMOTO
This paper proposes an analytical model of maximum operating frequency of class-D zero-voltage-switching (ZVS) inverter. The model includes linearized drain-source parasitic capacitance and any duty ratio. The nonlinear drain-source parasitic capacitance is equally linearized through a charge-related equation. The model expresses the relationship among frequency, shunt capacitance, duty ratio, load impedance, output current phase, and DC input voltage under the ZVS condition. The analytical result shows that the maximum operating frequency under the ZVS condition can be obtained when the duty ratio, the output current phase, and the DC input voltage are set to optimal values. A 650 V/30 A SiC-MOSFET is utilized for both simulated and experimental verification, resulting in good consistency.
Satoshi ITO Tomoaki KANAYA Akihiro NAKAO Masato OGUCHI Saneyasu YAMAGUCHI
The concepts of programmable switches and software-defined networking (SDN) give developers flexible and deep control over the behavior of switches. We expect these concepts to dramatically improve the functionality of switches. In this paper, we focus on the concept of Deeply Programmable Networks (DPN), where data planes are programmable, and application switches based on DPN. We then propose a method to improve the performance of a key-value store (KVS) through an application switch. First, we explain the DPN and application switches. The DPN is a network that makes not only control planes but also data planes programmable. An application switch is a switch that implements some functions of network applications, such as database management system (DBMS). Second, we propose a method to improve the performance of Cassandra, one of the most popular key-value based DBMS, by implementing a caching function in a switch in a dedicated network such as a data center. The proposed method is expected to be effective even though it is a simple and traditional way because it is in the data path and the center of the network application. Third, we implement a switch with the caching function, which monitors the accessed data described in packets (Ethernet frames) and dynamically replaces the cached data in the switch, and then show that the proposed caching switch can significantly improve the KVS transaction performance with this implementation. In the case of our evaluation, our method improved the KVS transaction throughput by up to 47%.
Sohei SHIMOMAI Kei UEDA Shinji KIMURA
Recently, Quantum Annealing (QA) has attracted attention as an efficient algorithm for combinatorial optimization problems. In QA, the input data size becomes large and its reduction is important for accelerating by the hardware emulation since the usable memory size and its bandwidth are limited. The paper proposes the compression method of input sparse matrices for QA emulator. The proposed method uses the sparseness of the coefficient matrix and the reappearance of the same values. An independent table is introduced and data are compressed by the search and registration method of two consecutive data in the value table. The proposed method is applied to Traveling Salesman Problem (TSP) with 32, 64 and 96 cities and Nurse Scheduling Problem (NSP). The proposed method could reduce the amount of data by 1/40 for 96 city TSP and could manage 96 city TSP on the hardware emulator. When applied to NSP, we confirmed the effectiveness of the proposed method by the compression ratio ranging from 1/4 to 1/11.8. The data reduction is also useful for the simulation/emulation performance when using the compressed data directly and 1.9 times faster speed can be found on 96 city TSP than the CSR-based method.
The aim of a computer-aided drawing therapy system in this work is to associate drawings which a client makes with the client's mental state in quantitative terms. A case study is conducted on experimental data which contain both pastel drawings and mental state scores obtained from the same client in a psychotherapy program. To perform such association through colors, we translate a drawing to a color feature by measuring its representative colors as primary color rates. A primary color rate of a color is defined from a psychological primary color in a way such that it shows a rate of emotional properties of the psychological primary color which is supposed to affect the color. To obtain several informative colors as representative ones of a drawing, we define two kinds of color: approximate colors extracted by color reduction, and area-averaged colors calculated from the approximate colors. A color analysis method for extracting representative colors from each drawing in a drawing sequence under the same conditions is presented. To estimate how closely a color feature is associated with a concurrent mental state, we propose a method of utilizing machine-learning classification. A practical way of building a classification model through training and validation on a very small dataset is presented. The classification accuracy reached by the model is considered as the degree of association of the color feature with the mental state scores given in the dataset. Experiments were carried out on given clinical data. Several kinds of color feature were compared in terms of the association with the same mental state. As a result, we found out a good color feature with the highest degree of association. Also, primary color rates proved more effective in representing colors in psychological terms than RGB components. The experimentals provide evidence that colors can be associated quantitatively with states of human mind.
In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1) × (n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n × 2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 20n × 16n grid if T(G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 10n × 5n grid if T(G) has exactly five leaves. We also present a linear-time algorithm to find such a drawing.
We have developed and evaluated a prototype micro-pump for a new form of medication that is driven by a chemical reaction. The chemical reaction between citric acid and sodium bicarbonate produces carbon dioxide, the pressure of which pushes the medication out. This micropump is smaller in size than conventional diaphragm-type micropumps and is suitable for swallowing.
This paper concentrates on a class of pseudorandom sequences generated by combining q-ary m-sequences and quadratic characters over a finite field of odd order, called binary generalized NTU sequences. It is shown that the relationship among the sub-sequences of binary generalized NTU sequences can be formulated as combinatorial structures called Hadamard designs. As a consequence, the combinatorial structures generalize the group structure discovered by Kodera et al. (IEICE Trans. Fundamentals, vol.E102-A, no.12, pp.1659-1667, 2019) and lead to a finite-geometric explanation for the investigated group structure.
Mamoru UGAJIN Yuya KAKEI Nobuyuki ITOH
Quadrature voltage-controlled oscillators (VCOs) with current-weight-average and voltage-weight-average phase-adjusting architectures are studied. The phase adjusting equalizes the oscillation frequency to the LC-resonant frequency. The merits of the equalization are explained by using Leeson's phase noise equation and the impulse sensitivity function (ISF). Quadrature VCOs with the phase-adjusting architectures are fabricated using 180-nm TSMC CMOS and show low-phase-noise performances compared to a conventional differential VCO. The ISF analysis and small-signal analysis also show that the drawbacks of the current-weight-average phase-adjusting and voltage-weight-average phase-adjusting architectures are current-source noise effect and large additional capacitance, respectively. A voltage-average-adjusting circuit with a source follower at its input alleviates the capacitance increase.
Purevtseren BAYARSAIKHAN Ryuji KUSE Takeshi FUKUSAKO Kazuma TOMIMOTO Masayuki MIYASHITA Ryo YAMAGUCHI
An aperture-shared multi-port waveguide antenna with multiple feeds is presented in this paper. The antenna consists of sequentially rotated four traditional WR-28 waveguides at 28GHz so as to create a multi-polarized function with decoupling between the ports. In addition, a rectangular DR (Dielectric resonator) is mounted at the center of the four apertures to obtain lower mutual coupling over a wide band and to suppress the cross-polarization in the antenna boresight direction. The proposed antenna achieves high gain of 14.4dBi, low mutual coupling of ≤-20dB on average, sufficient cross-polarization discrimination level at ≃20dB in the 27-29GHz frequency band.
Constructing accurate similarity graph is an important process in graph-based clustering. However, traditional methods have three drawbacks, such as the inaccuracy of the similarity graph, the vulnerability to noise and outliers, and the need for additional discretization process. In order to eliminate these limitations, an entropy regularized unsupervised clustering based on maximum correntropy criterion and adaptive neighbors (ERMCC) is proposed. 1) Combining information entropy and adaptive neighbors to solve the trivial similarity distributions. And we introduce l0-norm and spectral embedding to construct similarity graph with sparsity and strong segmentation ability. 2) Reducing the negative impact of non-Gaussian noise by reconstructing the error using correntropy. 3) The prediction label vector is directly obtained by calculating the sparse strongly connected components of the similarity graph Z, which avoids additional discretization process. Experiments are conducted on six typical datasets and the results showed the effectiveness of the method.
Tongwei LU Hao ZHANG Feng MIN Shihai JIA
Convolutional neural network (CNN) based vehicle re-identificatioin (ReID) inevitably has many disadvantages, such as information loss caused by downsampling operation. Therefore we propose a vision transformer (Vit) based vehicle ReID method to solve this problem. To improve the feature representation of vision transformer and make full use of additional vehicle information, the following methods are presented. (I) We propose a Quadratic Split Architecture (QSA) to learn both global and local features. More precisely, we split an image into many patches as “global part” and further split them into smaller sub-patches as “local part”. Features of both global and local part will be aggregated to enhance the representation ability. (II) The Auxiliary Information Embedding (AIE) is proposed to improve the robustness of the model by plugging a learnable camera/viewpoint embedding into Vit. Experimental results on several benchmarks indicate that our method is superior to many advanced vehicle ReID methods.
Satoru JIMBO Daiki OKONOGI Kota ANDO Thiem Van CHU Jaehoon YU Masato MOTOMURA Kazushi KAWAMURA
For formulating Quadratic Knapsack Problems (QKPs) into the form of Quadratic Unconstrained Binary Optimization (QUBO), it is necessary to introduce an integer variable, which converts and incorporates the knapsack capacity constraint into the overall energy function. In QUBO, this integer variable is encoded with auxiliary binary variables, and the encoding method used for it affects the behavior of Simulated Annealing (SA) significantly. For improving the efficiency of SA for QKP instances, this paper first visualized and analyzed their annealing processes encoded by conventional binary and unary encoding methods. Based on this analysis, we proposed a novel hybrid encoding (HE), getting the best of both worlds. The proposed HE obtained feasible solutions in the evaluation, outperforming the others in small- and medium-scale models.
Kai YAN Tiejun ZHAO Muyun YANG
Graph layout is a critical component in graph visualization. This paper proposes GRAPHULY, a graph u-nets-based neural network, for end-to-end graph layout generation. GRAPHULY learns the multi-level graph layout process and can generate graph layouts without iterative calculation. We also propose to use Laplacian positional encoding and a multi-level loss fusion strategy to improve the layout learning. We evaluate the model with a random dataset and a graph drawing dataset and showcase the effectiveness and efficiency of GRAPHULY in graph visualization.
A grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without any edge-intersection. In this paper we give a linear-time algorithm to find a grid drawing of any given 5-connected plane graph G with five or more vertices on the outer face. The size of the drawing satisfies W + H≤n - 2, where n is the number of vertices in G, W is the width and H is the height of the grid drawing.
Hiro TAMURA Kiyoshi YANAGISAWA Atsushi SHIRANE Kenichi OKADA
This paper presents a physical layer wireless device identification method that uses a convolutional neural network (CNN) operating on a quadrant IQ transition image. This work introduces classification and detection tasks in one process. The proposed method can identify IoT wireless devices by exploiting their RF fingerprints, a technology to identify wireless devices by using unique variations in analog signals. We propose a quadrant IQ image technique to reduce the size of CNN while maintaining accuracy. The CNN utilizes the IQ transition image, which image processing cut out into four-part. An over-the-air experiment is performed on six Zigbee wireless devices to confirm the proposed identification method's validity. The measurement results demonstrate that the proposed method can achieve 99% accuracy with the light-weight CNN model with 36,500 weight parameters in serial use and 146,000 in parallel use. Furthermore, the proposed threshold algorithm can verify the authenticity using one classifier and achieved 80% accuracy for further secured wireless communication. This work also introduces the identification of expanded signals with SNR between 10 to 30dB. As a result, at SNR values above 20dB, the proposals achieve classification and detection accuracies of 87% and 80%, respectively.
Yosuke MUKASA Tomoya WAKAIZUMI Shu TANAKA Nozomu TOGAWA
In an amusement park, an attraction-visiting route considering the waiting time and traveling time improves visitors' satisfaction and experience. We focus on Ising machines to solve the problem, which are recently expected to solve combinatorial optimization problems at high speed by mapping the problems to Ising models or quadratic unconstrained binary optimization (QUBO) models. We propose a mapping of the visiting-route recommendation problem in amusement parks to a QUBO model for solving it using Ising machines. By using an actual Ising machine, we could obtain feasible solutions one order of magnitude faster with almost the same accuracy as the simulated annealing method for the visiting-route recommendation problem.
Masahiro ONDA Masaki MORIGUCHI Keiko IMAI
The Tokyo subway is one of the most complex subway networks in the world and it is difficult to compute a visually readable metro map using existing layout methods. In this paper, we present a new method that can generate complex metro maps such as the Tokyo subway network. Our method consists of two phases. The first phase generates rough metro maps. It decomposes the metro networks into smaller subgraphs and partially generates rough metro maps. In the second phase, we use a local search technique to improve the aesthetic quality of the rough metro maps. The experimental results including the Tokyo metro map are shown.
In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1)×(n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n×2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 grid if T(G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 20n×16n grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of O(n2) size.
In this paper, we address the problem of detector design in severely frequency-selective channels for spatial multiplexing systems that adopt filter bank multicarrier based on offset quadrature amplitude modulation (FBMC/OQAM) as the communication waveforms. We consider decision feedback equalizers (DFEs) that use multiple feedback filters to jointly cancel the post-cursor components of inter-symbol interference, inter-antenna interference, and, in some configuration, inter-subchannel interference. By exploiting the special structures of the correlation matrix and the staggered property of the FBMC/OQAM signals, we obtain an efficient method of computing the DFE coefficients that requires a smaller number of multiplications than the linear equalizer (LE) and conventional DFE do. The simulation results show that the proposed detectors considerably outperform the LE and conventional DFE at moderate-to-high signal-to-noise ratios.