A. K. M. Tauhidul ISLAM Sakti PRAMANIK Qiang ZHU
In recent years we have witnessed an increasing demand to process queries on large datasets in Non-ordered Discrete Data Spaces (NDDS). In particular, one type of query in an NDDS, called box queries, is used in many emerging applications including error corrections in bioinformatics and network intrusion detection in cybersecurity. Effective indexing methods are necessary for efficiently processing queries on large datasets in disk. However, most existing NDDS indexing methods were not designed for box queries. Several recent indexing methods developed for box queries on a large NDDS dataset in disk are based on the popular data-partitioning approach. Unfortunately, a space-partitioning based indexing scheme, which is more effective for box queries in an NDDS, has not been studied before. In this paper, we propose a novel indexing method based on space-partitioning, called the BINDS-tree, for supporting efficient box queries on a large NDDS dataset in disk. A number of effective strategies such as node split based on minimum span and cross optimal balance, redundancy reduction utilizing a singleton dimension inheritance property, and a space-efficient structure for the split history are incorporated in the constructing algorithm for the BINDS-tree. Experimental results demonstrate that the proposed BINDS-tree significantly improves the box query I/O performance, comparing to that of the state-of-the-artdata-partitioning based NDDS indexing method.
Order preserving matching refers to the problem of reporting substrings in the text which are order-isomorphic to the pattern. In this paper, we show a simple heuristic which runs in linear time on average, based on finding the largest elements in each substring and checking their locations against that of the pattern. It is easy to implement and experimental results showed that the running time grows linearly.
We propose a recursive algorithm to reduce the computational complexity of the r-order nonlinearity of n-variable Boolean functions. Applying the algorithm and using the sufficient and necessary condition put forward by [1] to cut the vast majority of useless search branches, we show that the covering radius of the Reed-Muller Code R(3, 7) in R(5, 7) is 20.
Taiki SHINOHARA Takashi YOSHIDA Naoyuki AIKAWA
Two-dimensional (2-D) maximally flat finite impulse response (FIR) digital filters have flat characteristics in both passband and stopband. 2-D maximally flat diamond-shaped half-band FIR digital filter can be designed very efficiently as a special case of 2-D half-band FIR filters. In some cases, this filter would require the reduction of the filter lengths for one of the axes while keeping the other axis unchanged. However, the conventional methods can realize such filters only if difference between each order is 2, 4 and 6. In this paper, we propose a closed-form frequency response of 2-D low-pass maximally flat diamond-shaped half-band FIR digital filters with arbitrary filter orders. The constraints to treat arbitrary filter orders are firstly proposed. Then, a closed-form transfer function is achieved by using Bernstein polynomial.
Huu-Anh TRAN Heyan HUANG Phuoc TRAN Shumin SHI Huu NGUYEN
Word order is one of the most significant differences between the Chinese and Vietnamese. In the phrase-based statistical machine translation, the reordering model will learn reordering rules from bilingual corpora. If the bilingual corpora are large and good enough, the reordering rules are exact and coverable. However, Chinese-Vietnamese is a low-resource language pair, the extraction of reordering rules is limited. This leads to the quality of reordering in Chinese-Vietnamese machine translation is not high. In this paper, we have combined Chinese dependency relation and Chinese-Vietnamese word alignment results in order to pre-order Chinese word order to be suitable to Vietnamese one. The experimental results show that our methodology has improved the machine translation performance compared to the translation system using only the reordering models of phrase-based statistical machine translation.
Yuan LIANG Xinyu DA Ruiyang XU Lei NI Dong ZHAI Yu PAN
We propose a novel bit error rate (BER) analysis model of weighted-type fractional Fourier transform (WFRFT)-based systems with WFRFT order offset Δα. By using the traditional BPSK BER analysis method, we deduce the equivalent signal noise ratio (SNR), model the interference in the channel as a Gaussian noise with non-zero mean, and provide a theoretical BER expression of the proposed system. Simulation results show that its theoretical BER performance well matches the empirical performance, which demonstrates that the theoretical BER analysis proposed in this paper is reliable.
Shogo KOYANAGI Teruyuki MIYAJIMA
In this paper, we consider full-duplex (FD) relay networks with filter-and-forward (FF)-based multiple relays (FD-FF), where relay filters jointly mitigate self-interference (SI), inter-relay interference (IRI), and inter-symbol interference. We consider the filter design problem based on signal-to-noise-plus-interference ratio maximization subject to a total relay transmit power constraint. To make the problem tractable, we propose two methods: one that imposes an additional constraint whereby the filter responses to SI and IRI are nulled, and the other that makes i.i.d. assumptions on the relay transmit signals. Simulation results show that the proposed FD-FF scheme outperforms a conventional FF scheme in half-duplex mode. We also consider the filter design when only second-order statistics of channel path gains are available.
Boolean functions used in stream ciphers and block ciphers should have high second-order nonlinearity to resist several known attacks and some potential attacks which may exist but are not yet efficient and might be improved in the future. The second-order nonlinearity of Boolean functions also plays an important role in coding theory, since its maximal value equals the covering radius of the second-order Reed-Muller code. But it is an extremely hard task to calculate and even to bound the second-order nonlinearity of Boolean functions. In this paper, we present a lower bound on the second-order nonlinearity of the generalized Maiorana-McFarland Boolean functions. As applications of our bound, we provide more simpler and direct proofs for two known lower bounds on the second-order nonlinearity of functions in the class of Maiorana-McFarland bent functions. We also derive a lower bound on the second-order nonlinearity of the functions which were conjectured bent by Canteaut and whose bentness was proved by Leander, by further employing our bound.
Teruaki KITASUKA Takayuki MATSUZAKI Masahiro IIDA
The order/degree problem consists of finding the smallest diameter graph for a given order and degree. Such a graph is beneficial for designing low-latency networks with high performance for massively parallel computers. The average shortest path length (ASPL) of a graph has an influence on latency. In this paper, we propose a novel order adjustment approach. In the proposed approach, we search for Cayley graphs of the given degree that are close to the given order. We then adjust the order of the best Cayley graph to meet the given order. For some order and degree pairs, we explain how to derive the smallest known graphs from the Graph Golf 2016 and 2017 competitions.
Gaoyuan ZHANG Hong WEN Longye WANG Xiaoli ZENG Jie TANG Runfa LIAO Liang SONG
A simple and novel multiple-symbol differential detection (MSDD) scheme is proposed for IEEE 802.15.4 binary phase shift keying (BPSK) receivers. The detection is initiated by estimating and compensating the carrier frequency offset (CFO) effect in the chip sample of interest. With these new statistics, the decisions are jointly made by allowing the observation window length to be longer than two bit intervals. Simulation results demonstrate that detection reliability of the IEEE 802.15.4 BPSK receivers is significantly improved. Namely, at packet error rate (PER) of 1×10-3, the signal-to-noise ratio (SNR) gap between ideal coherent detection (perfect carrier reference phase and no CFO) with differential decoding and conventional optimal single differential coherent detection (SDCD) is filled by 2.1dB when the observation window length is set to 6bit intervals. Then, the benefit that less energy consumed by retransmissions is successfully achieved.
Yuhei WATANABE Takanori ISOBE Masakatu MORII
Kreyvium is a NLFSR-based stream cipher which is oriented to homomorphic-ciphertext compression. This is a variant of Trivium with 128-bit security. Designers have evaluated the security of Kreyvium and concluded that the resistance of Kreyvium to the conditional differential cryptanalysis is at least the resistance of Trivium, and even better. However, we consider that this attack is effective for reduced Kreyvium due to the structure of it. This paper shows the conditional differential cryptanalysis for Kreyvium, and we propose distinguishing and key recovery attacks. We show how to arrange differences and conditions to obtain good higher-order conditional differential characteristics. We use two types of higher-order conditional differential characteristics to find a distinguisher, e.g. the bias of higher-order conditional differential characteristics of a keystream and the probabilistic bias of them. In the first one, we obtain the distinguisher on Kreyvium with 730 rounds from 20-th order characteristics. In the second one, we obtain the distinguisher on Kreyvium with 899 rounds from 25-th order conditional differential characteristics. Moreover, we show the key recovery attack on Kreyvium with 736 rounds from 20-th order characteristics. We experimentally confirm all our attacks. The second distinguisher shows that we can obtain the distinguisher on Kreyvium with more rounds than the distinguisher on Trivium. Therefore, Kreyvium has a smaller security margin than Trivium for the conditional differential cryptanalysis.
Chunxiao FAN Xiaopeng HONG Lei TIAN Yue MING Matti PIETIKÄINEN Guoying ZHAO
PCANet, as one noticeable shallow network, employs the histogram representation for feature pooling. However, there are three main problems about this kind of pooling method. First, the histogram-based pooling method binarizes the feature maps and leads to inevitable discriminative information loss. Second, it is difficult to effectively combine other visual cues into a compact representation, because the simple concatenation of various visual cues leads to feature representation inefficiency. Third, the dimensionality of histogram-based output grows exponentially with the number of feature maps used. In order to overcome these problems, we propose a novel shallow network model, named as PCANet-II. Compared with the histogram-based output, the second order pooling not only provides more discriminative information by preserving both the magnitude and sign of convolutional responses, but also dramatically reduces the size of output features. Thus we combine the second order statistical pooling method with the shallow network, i.e., PCANet. Moreover, it is easy to combine other discriminative and robust cues by using the second order pooling. So we introduce the binary feature difference encoding scheme into our PCANet-II to further improve robustness. Experiments demonstrate the effectiveness and robustness of our proposed PCANet-II method.
Hiroyuki ASAHARA Takuji KOUSAKA
In this research, we propose an effective stability analysis method to impacting systems with periodically moving borders (periodic borders). First, we describe an n-dimensional impacting system with periodic borders. Subsequently, we present an algorithm based on a stability analysis method using the monodromy matrix for calculating stability of the waveform. This approach requires the state-transition matrix be related to the impact phenomenon, which is known as the saltation matrix. In an earlier study, the expression for the saltation matrix was derived assuming a static border (fixed border). In this research, we derive an expression for the saltation matrix for a periodic border. We confirm the performance of the proposed method, which is also applicable to systems with fixed borders, by applying it to an impacting system with a periodic border. Using this approach, we analyze the bifurcation of an impacting system with a periodic border by computing the evolution of the stable and unstable periodic waveform. We demonstrate a discontinuous change of the periodic points, which occurs when a periodic point collides with a border, in the one-parameter bifurcation diagram.
Tao LIANG Flavia GRASSI Giordano SPADACINI Sergio Amedeo PIGNARI
This work presents a hybrid formulation of the stochastic reduced order model (SROM) algorithm, which makes use of Gauss quadrature, a key ingredient of the stochastic collocation method, to avoid the cumbersome optimization process required by SROM for optimal extraction of the sample set. With respect to classic SROM algorithms, the proposed formulation allows a significant reduction in computation time and burden as well as a remarkable improvement in the accuracy and convergence rate in the estimation of statistical moments. The method is here applied to a specific case study, that is the prediction of crosstalk in a two-conductor wiring structure with electrical and geometrical parameters not perfectly known. Both univariate and multivariate analyses are carried out, with the final objective being to compare the performance of the two SROM formulations with respected to Monte Carlo simulations.
Bimal CHANDRA DAS Satoshi TAKAHASHI Eiji OKI Masakazu MURAMATSU
This paper introduces robust optimization models for minimization of the network congestion ratio that can handle the fluctuation in traffic demands between nodes. The simplest and widely used model to minimize the congestion ratio, called the pipe model, is based on precisely specified traffic demands. However, in practice, network operators are often unable to estimate exact traffic demands as they can fluctuate due to unpredictable factors. To overcome this weakness, we apply robust optimization to the problem of minimizing the network congestion ratio. First, we review existing models as robust counterparts of certain uncertainty sets. Then we consider robust optimization assuming ellipsoidal uncertainty sets, and derive a tractable optimization problem in the form of second-order cone programming (SOCP). Furthermore, we take uncertainty sets to be the intersection of ellipsoid and polyhedral sets, and considering the mirror subproblems inherent in the models, obtain tractable optimization problems, again in SOCP form. Compared to the previous model that assumes an error interval on each coordinate, our models have the advantage of being able to cope with the total amount of errors by setting a parameter that determines the volume of the ellipsoid. We perform numerical experiments to compare our SOCP models with the existing models which are formulated as linear programming problems. The results demonstrate the relevance of our models in terms of congestion ratio and computation time.
Pei CHEN Dexiu HU Yongjun ZHAO Chengcheng LIU
Aiming at solving the performance degradation caused by the covariance matrix mismatch in wideband beamforming for conformal arrays, a novel adaptive beamforming algorithm is proposed in this paper. In this algorithm, the interference-plus-noise covariance matrix is firstly reconstructed to solve the desired signal contamination problem. Then, a sparse reconstruction method is utilized to reduce the high computational cost and the requirement of sampling data. A novel cost function is formulated by the focusing matrix and singular value decomposition. Finally, the optimization problem is efficiently solved in a second-order cone programming framework. Simulation results using a cylindrical array demonstrate the effectiveness and robustness of the proposed algorithm and prove that this algorithm can achieve superior performance over the existing wideband beamforming methods for conformal arrays.
An efficient reciprocity and passivity preserving balanced truncation for RLC networks is presented in this paper. Reciprocity and passivity are fundamental principles of linear passive networks. Hence, reduction with preservation of reciprocity and passivity is necessary to simulate behavior of the circuits including the RLC networks accurately and stably. Moreover, the proposed method is more efficient than the previous balanced truncation methods, because sparsity patterns of the coefficient matrices for the circuit equations of the RLC networks are fully available. In the illustrative examples, we will show that the proposed method is compatible with PRIMA, which is known as a general reduction method of RLC networks, in efficiency and used memory, and is more accurate at high frequencies than PRIMA.
Tomohiko UYEMATSU Tetsunao MATSUTA
We consider the intrinsic randomness problem for correlated sources. Specifically, there are three correlated sources, and we want to extract two mutually independent random numbers by using two separate mappings, where each mapping converts one of the output sequences from two correlated sources into a random number. In addition, we assume that the obtained pair of random numbers is also independent of the output sequence from the third source. We first show the δ-achievable rate region where a rate pair of two mappings must satisfy in order to obtain the approximation error within δ ∈ [0,1), and the second-order achievable rate region for correlated general sources. Then, we apply our results to non-mixed and mixed independently and identically distributed (i.i.d.) correlated sources, and reveal that the second-order achievable rate region for these sources can be represented in terms of the sum of normal distributions.
Hongmin LIU Lulu CHEN Zhiheng WANG Zhanqiang HUO
In this paper, the concept of gradient order is introduced and a novel gradient order curve descriptor (GOCD) for curve matching is proposed. The GOCD is constructed in the following main steps: firstly, curve support region independent of the dominant orientation is determined and then divided into several sub-regions based on gradient magnitude order; then gradient order feature (GOF) of each feature point is generated by encoding the local gradient information of the sample points; the descriptor is finally achieved by turning to the description matrix of GOF. Since both the local and the global gradient information are captured by GOCD, it is more distinctive and robust compared with the existing curve matching methods. Experiments under various changes, such as illumination, viewpoint, image rotation, JPEG compression and noise, show the great performance of GOCD. Furthermore, the application of image mosaic proves GOCD can be used successfully in actual field.
Rong CHEN Cunqian FENG Sisan HE Yi RAO
The extraction of micro-motion parameters is deeply influenced by the precision of estimation on translational motion parameters. Based on the periodicity of micro-motion, the quadratic polynomial fitting is carried out among range delays to align envelope. The micro-motion component of phase information is eliminated by conjugate multiplication after which the translational motion parameters are estimated. Then the translational motion is precisely compensated through the third order polynomial fitting. Results of simulation demonstrate that the algorithm put forward here can realize the precise compensation for translational motion parameters even under an environment with low signal noise ratio (SNR).