This paper presents a pivot-set generation algorithm for accelerating exact similarity search in a large-scale data set. To deal with the large-scale data set, it is important to efficiently construct a search index offline as well as to perform fast exact similarity search online. Our proposed algorithm efficiently generates competent pivots with two novel techniques: hierarchical data partitioning and fast pivot optimization techniques. To make effective use of a small number of pivots, the former recursively partitions a data set into two subsets with the same size depending on the rank order from each of two assigned pivots, resulting in a complete binary tree. The latter calculates a defined objective function for pivot optimization with a low computational cost by skillfully operating data objects mapped into a pivot space. Since the generated pivots provide the tight lower bounds on distances between a query object and the data objects, an exact similarity search algorithm effectively avoids unnecessary distance calculations. We demonstrate that the search algorithm using the pivots generated by the proposed algorithm reduces distance calculations with an extremely high rate regarding a range query problem for real large-scale image data sets.

Query autocompletion is an important and practical technique when users want to search for desirable information. As mobile devices become more and more popular, one of the main applications is location-aware service, such as Web mapping. In this paper, we propose a new solution to location-aware query autocompletion. We devise a trie-based index structure and integrate spatial information into trie nodes. Our method is able to answer both range and top-k queries. In addition, we discuss the extension of our method to support the error tolerant feature in case user's queries contain typographical errors. Experiments on real datasets show that the proposed method outperforms existing methods in terms of query processing performance.

The performance of secret-sharing (SS)-based multiparty computation (MPC) has recently increased greatly, and several efforts to implement and use it have been put into practice. Authentication of clients is one critical mechanism for implementing SS-based MPC successfully in practice. We propose a password-based authentication protocol for SS-based MPC. Our protocol is secure in the presence of secure channels, and it is optimized for practical use with SS-based MPC in the following ways. Threshold security: Our protocol is secure in the honest majority, which is necessary and sufficient since most practical results on SS-based MPC are secure in the same environment. Establishing distinct channels: After our protocol, a client has distinct secure and two-way authenticated channels to each server. Ease of implementation: Our protocol consists of SS, operations involving SS, and secure channels, which can be reused from an implementation of SS-based MPC. Furthermore, we implemented our protocol with an optimization for the realistic network. A client received the result within 2 sec even when the network delay was 200 ms, which is almost the delay that occurs between Japan and Europe.

In this paper, we present a new three-way split formula for binary polynomial multiplication (PM) with five recursive multiplications. The scheme is based on a recently proposed multievaluation and interpolation approach using field extension. The proposed PM formula achieves the smallest space complexity. Moreover, it has about 40% reduced time complexity compared to best known results. In addition, using developed techniques for PM formulas, we propose a three-way split formula for Toeplitz matrix vector product with five recursive products which has a considerably improved complexity compared to previous known one.

Let G be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. Suppose that we are given two list edge-colorings f0 and fr of G, and asked whether there exists a sequence of list edge-colorings of G between f0 and fr such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer k ≥ 6 and planar graphs of maximum degree three, but any computational hardness was unknown for the non-list variant in which every edge has the same list of k colors. In this paper, we first improve the known result by proving that, for every integer k ≥ 4, the problem remains PSPACE-complete even for planar graphs of bounded bandwidth and maximum degree three. Since the problem is known to be solvable in polynomial time if k ≤ 3, our result gives a sharp analysis of the complexity status with respect to the number k of colors. We then give the first computational hardness result for the non-list variant: for every integer k ≥ 5, the non-list variant is PSPACE-complete even for planar graphs of bandwidth quadratic in k and maximum degree k.

There are many software systems that have been used and maintained for a long time. By undergoing such a maintenance process, similar code fragments were intentionally left in the source code of such software, and knowing how to manage a software system that contains a lot of similar code fragments becomes a major concern. In this study, we proposed a method to pick up components that were commonly used in similar code fragments from a target software system. This method was realized by using the component rank model and by checking the differences of evaluation values for each component before and after merging components that had similar code fragments. In many cases, components whose evaluation value had decreased would be used by both the components that were merged, so we considered that these components were commonly used in similar code fragments. Based on the proposed approach, we implemented a system to calculate differences of evaluation values for each component, and conducted three evaluation experiments to confirm that our method was useful for detecting components that were commonly used in similar code fragments, and to confirm how our method can help developers when developers add similar components. Based on the experimental results, we also discuss some improvement methods and provide the results from applications of these methods.

Tunstall code is known as an optimal variable-to-fixed length (VF) lossless source code under the criterion of average coding rate, which is defined as the codeword length divided by the average phrase length. In this paper we define the average coding rate of a VF code as the expectation of the pointwise coding rate defined by the codeword length divided by the phrase length. We call this type of average coding rate the average pointwise coding rate. In this paper, a new VF code is proposed. An incremental parsing tree construction algorithm like the one that builds Tunstall parsing tree is presented. It is proved that this code is optimal under the criterion of the average pointwise coding rate, and that the average pointwise coding rate of this code converges asymptotically to the entropy of the stationary memoryless source emitting the data to be encoded. Moreover, it is proved that the proposed code attains better worst-case coding rate than Tunstall code.

Block compressed sensing (CS) with optimal permutation is a promising method to improve sampling efficiency in CS-based image compression. However, the existing optimal permutation scheme brings a large amount of extra data to encode the permutation information because it needs to know the permutation information to accomplish signal reconstruction. When the extra data is taken into consideration, the improvement in sampling efficiency of this method is limited. In order to solve this problem, a new optimal permutation strategy for block CS (BCS) is proposed. Based on the proposed permutation strategy, an improved optimal permutation based BCS method called BCS-NOP (BCS with new optimal permutation) is proposed in this paper. Simulation results show that the proposed approach reduces the amount of extra data to encode the permutation information significantly and thereby improves the sampling efficiency compared with the existing optimal permutation based BCS approach.

This paper reports the development of a landmine visualization system based on complex-valued self-organizing map (CSOM) by employing one-dimensional (1-D) array of taper-walled tapered slot antennas (TSAs). Previously we constructed a high-density two-dimensional array system to observe and classify complex-amplitude texture of scattered wave. The system has superiority in its adaptive distinction ability between landmines and other clutters. However, it used so many (144) antenna elements with many mechanical radio-frequency (RF) switches and cables that it has difficulty in its maintenance and also requires long measurement time. The 1-D array system proposed here uses only 12 antennas and adopts electronic RF switches, resulting in easy maintenance and 1/4 measurement time. Though we observe stripe noise specific to this 1-D system, we succeed in visualization with effective solutions.

To aim to achieve a high-performance computation for microwave simulations with low cost, small size machine and low energy consumption, a method of the FDTD dedicated computer has been investigated. It was shown by VHDL logical circuit simulations that the FDTD dedicated computer with a dataflow architecture has much higher performance than that of high-end PC and GPU. Then the remaining task of this work is large scale computations by the dedicated computer, since microwave simulations for only 18×18×Z grid space (Z is the number of girds for z direction) can be executed in a single FPGA at most. To treat much larger numerical model size for practical applications, this paper considers an implementation of a domain decomposition method operation of the FDTD dedicated computer in a single FPGA.

In this letter, robust sparse signal recovery is considered in the presence of heavy-tailed impulsive noise. Two Bayesian approaches are developed where a Bayesian framework is constructed by utilizing the Laplace distribution to model the noise. By rewriting the noise-fitting term as a reweighted quadratic function which is optimized in the sparse signal space, the Type I Maximum A Posteriori (MAP) approach is proposed. Next, by exploiting the hierarchical structure of the sparse prior and the likelihood function, we develop the Type II Evidence Maximization approach optimized in the hyperparameter space. The numerical results verify the effectiveness of the proposed methods in the presence of impulsive noise.

This paper newly proposes a fast computation technique on the method of image Green's function for p-characteristic calculations, when a plane wave with the transverse wavenumber p is incident on a periodic rough surface having perfect conductivity. In the computation of p-characteristics, based on a spectral domain periodicity of the periodic image Green's function, the image integral equation for a given incidence p maintains the same form for other particular incidences except for the excitation term. By means of a quadrature method, such image integral equations lead to matrix equations. Once the first given matrix equation is performed by a solution procedure as calculations of its matrix elements and its inverse matrix, the other matrix equations for other particular incidences no longer need such a solution procedure. Thus, the total CPU time for the computation of p-characteristics is largely reduced in complex shaped surface cases, huge roughness cases or large period cases.

In this paper, we propose a low-complexity widely-linear minimum mean square error (WL-MMSE) signal detection based on the Chebyshev polynomials accelerated symmetric successive over relaxation (SSORcheb) algorithm for uplink (UL) over-loaded large-scale multiple-input multiple-output (MIMO) systems. The technique of utilizing Chebyshev acceleration not only speeds up the convergence rate significantly, and maximizes the data throughput, but also reduces the cost. By utilizing the random matrix theory, we present good estimates for the Chebyshev acceleration parameters of the proposed signal detection in real large-scale MIMO systems. Simulation results demonstrate that the new WL-SSORcheb-MMSE detection not only outperforms the recently proposed linear iterative detection, and the optimal polynomial expansion (PE) WL-MMSE detection, but also achieves a performance close to the exact WL-MMSE detection. Additionally, the proposed detection offers superior sum rate and bit error rate (BER) performance compared to the precision MMSE detection with substantially fewer arithmetic operations in a short coherence time. Therefore, the proposed detection can satisfy the high-density and high-mobility requirements of some of the emerging wireless networks, such as, the high-mobility Internet of Things (IoT) networks.

This paper discusses a mode for pseudorandom functions (PRFs) based on the hashing mode of Lesamnta-LW and the domain extension called Merkle-Damgård with permutation (MDP). The hashing mode of Lesamnta-LW is a plain Merkle-Damgård iteration of a block cipher with its key size half of its block size. First, a PRF mode is presented which produces multiple independent PRFs with multiple permutations and initialization vectors if the underlying block cipher is a PRP. Then, two applications of the PRF mode are presented. One is a PRF with minimum padding. Here, padding is said to be minimum if the produced message blocks do not include message blocks only with the padded sequence for any non-empty input message. The other is a vector-input PRF using the PRFs with minimum padding.

Interconnection network is one of the inevitable components in parallel computers, since it is responsible to communication capabilities of the systems. It affects the system-level performance as well as the physical and logical structure of the systems. Although many studies are reported to enhance the interconnection network technology, we have to discuss many issues remaining. One of the most important issues is congestion management. In an interconnection network, many packets are transferred simultaneously and the packets interfere to each other in the network. Congestion arises as a result of the interferences. Its fast spreading speed seriously degrades communication performance and it continues for long time. Thus, we should appropriately control the network to suppress the congested situation for maintaining the maximum performance. Many studies address the problem and present effective methods, however, the maximal performance in an ideal situation is not sufficiently clarified. Solving the ideal performance is, in general, an NP-hard problem. This paper introduces particle swarm optimization (PSO) methodology to overcome the problem. In this paper, we first formalize the optimization problem suitable for the PSO method and present a simple PSO application as naive models. Then, we discuss reduction of the size of search space and introduce three practical variations of the PSO computation models as repetitive model, expansion model, and coding model. We furthermore introduce some non-PSO methods for comparison. Our evaluation results reveal high potentials of the PSO method. The repetitive and expansion models achieve significant acceleration of collective communication performance at most 1.72 times faster than that in the bursty communication condition.

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).

Knowledge graphs have been shown to be useful to many tasks in artificial intelligence. Triples of knowledge graphs are traditionally structured by human editors or extracted from semi-structured information; however, editing is expensive, and semi-structured information is not common. On the other hand, most such information is stored as text. Hence, it is necessary to develop a method that can extract knowledge from texts and then construct or populate a knowledge graph; this has been attempted in various ways. Currently, there are two approaches to constructing a knowledge graph. One is open information extraction (Open IE), and the other is knowledge graph embedding; however, neither is without problems. Stanford Open IE, the current best such system, requires labeled sentences as training data, and knowledge graph embedding systems require numerous triples. Recently, distributed representations of words have become a hot topic in the field of natural language processing, since this approach does not require labeled data for training. These require only plain text, but Mikolov showed that it can perform well with the word analogy task, answering questions such as, “a is to b as c is to __?.” This can be considered as a knowledge extraction task from a text for finding the missing entity of a triple. However, the accuracy is not sufficiently high when applied in a straightforward manner to relations in knowledge graphs, since the method uses only one triple as a positive example. In this paper, we analyze why distributed representations perform such tasks well; we also propose a new method for extracting knowledge from texts that requires much less annotated data. Experiments show that the proposed method achieves considerable improvement compared with the baseline; in particular, the improvement in HITS@10 was more than doubled for some relations.

A TM010 cavity power combiner is presented, which achieves direct interface to microstrip lines via magnetic field coupling. A prototype is fabricated and its S-matrix measured. From the S-parameters we calculate that it shows less than 0.85 dB insertion loss over 250 MHz bandwidth at X-band. The return power to the input ports is less than -15 dB over this bandwidth. We verify the insertion loss estimation using S-matrix, by measuring transmission S-parameter of a concatenated 2-port divider-combiner network. Similarly analyzed is the case of performance of power combiner when one of the input fails. We find that we can achieve graceful degradation provided we ensure some particular reflection phase at the degraded port.

Object detection is an essential and expensive process in many computer vision systems. Standard off-the-shelf embedded processors are hard to achieve performance-power balance for implementation of object detection applications. In this work, we explore an Application Specific Instruction set Processor (ASIP) for object detection using Histogram of Oriented Gradients (HOG) feature. Algorithm simplifications are adopted to reduce memory bandwidth requirements and mathematical complexity without losing reliability. Also, parallel histogram generation and on-the-fly Support Vector Machine (SVM) calculation architecture are employed to reduce the necessary cycle counts. The HOG algorithm on the proposed ASIP was accelerated by a factor of 63x compared to the pure software implementation. The ASIP was synthesized for a standard 90nm CMOS library, with a silicon area of 1.31mm2 and 47.8mW power consumption at a 200MHz frequency. Our object detection processor can achieve 42 frames-per-second (fps) on VGA video. The evaluation and implementation results show that the proposed ASIP is both area-efficient and power-efficient while being competitive with commercial CPUs/DSPs. Furthermore, our ASIP exhibits comparable performance even with hard-wire designs.

A Tikhonov regularized RLS algorithm with an exponential weighting factor, i.e., a leaky RLS (LRLS) algorithm was proposed by the author. A quadratic version of the LRLS algorithm also exists in the literature of adaptive filters. In this letter, a cubic version of the LRLS filter which is computationally efficient is proposed when the length of the adaptive filter is short. The proposed LRLS filter includes only a divide per iteration although its multiplications and additions increase in number. Simulation results show that the proposed LRLS filter is faster for its short length than the existing quadratic version of the LRLS filter.