Minami SATO Sosuke MINAMOTO Ryuichi SAKAI Yasuyuki MURAKAMI
It is proven that many public-key cryptosystems would be broken by the quantum computer. The knapsack cryptosystem which is based on the subset sum problem has the potential to be a quantum-resistant cryptosystem. Murakami and Kasahara proposed a SOSI trapdoor sequence which is made by combining shifted-odd (SO) and super-increasing (SI) sequence in the modular knapsack cryptosystem. This paper firstly show that the key generation method could not achieve a secure density against the low-density attack. Second, we propose a high-density key generation method and confirmed that the proposed scheme is secure against the low-density attack.
Yushi OGIWARA Ayanori YOROZU Akihisa OHYA Hideyuki KAWASHIMA
In the Robot Operating System (ROS), a major middleware for robots, the Transform Library (TF) is a mandatory package that manages transformation information between coordinate systems by using a directed forest data structure and providing methods for registering and computing the information. However, the structure has two fundamental problems. The first is its poor scalability: since it accepts only a single thread at a time due to using a single giant lock for mutual exclusion, the access to the tree is sequential. Second, there is a lack of data freshness: it retrieves non-latest synthetic data when computing coordinate transformations because it prioritizes temporal consistency over data freshness. In this paper, we propose methods based on transactional techniques. This will allow us to avoid anomalies, achieve high performance, and obtain fresh data. These transactional methods show a throughput of up to 429 times higher than the conventional method on a read-only workload and a freshness of up to 1276 times higher than the conventional one on a read-write combined workload.
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.
Hiroshi FUJIWARA Kanaho HANJI Hiroaki YAMAMOTO
In the online removable knapsack problem, a sequence of items, each labeled with its value and its size, is given one by one. At each arrival of an item, a player has to decide whether to put it into a knapsack or to discard it. The player is also allowed to discard some of the items that are already in the knapsack. The objective is to maximize the total value of the knapsack. Iwama and Taketomi gave an optimal algorithm for the case where the value of each item is equal to its size. In this paper we consider a case with an additional constraint that the capacity of the knapsack is a positive integer N and that the sizes of items are all integral. For each positive integer N, we design an algorithm and prove its optimality. It is revealed that the competitive ratio is not monotonic with respect to N.
Naoki KAWASAKI Yuuki MACHIDA Takayuki MISU Keiichi ABE Hiroshi SUGIMURA Makiko OKUMURA
A line display that utilizes saccade has been proposed. When an observer moves his or her eyes on a one-dimensional fixed line display, two-dimensional information is perceived on the retina. In this paper, a high speed flashing line display was developed using a CPLD and PIC microcontroller. The flashing period was reduced to 20 µs, which was less than half that of our previous system. The relationship between the flashing frequency and the optimum distance that can be perceived with the least distortion was clarified. The results show that the higher the flashing frequency is, the more information can be perceived from a farther position. Calculated values, which were based on the relationship between the flashing period and the width of the light source, were almost identical with measured values at the flashing frequencies from 3.3 kHz to 10 kHz. Due to short flashing period, the developed line display not only was visible at distance of 15 m or more, which is suitable for outdoor use, but also realized 16 gray levels.
Bitcoin is one of popular cryptocurrencies widely used over the world, and its blockchain technology has attracted considerable attention. In Bitcoin system, it has been reported that transactions are prioritized according to transaction fees, and that transactions with high priorities are likely to be confirmed faster than those with low priorities. In this paper, we consider performance modeling of Bitcoin-blockchain system in order to characterize the transaction-confirmation time. We first introduce the Bitcoin system, focusing on proof-of-work, the consensus mechanism of Bitcoin blockchain. Then, we show some queueing models and its analytical results, discussing the implications and insights obtained from the queueing models.
The binary quadratic knapsack problem (QKP) aims at optimizing a quadratic cost function within a single knapsack. Its applications and difficulty make it appealing for various industrial fields. In this paper we present an efficient strategy to solve the problem by modeling it as an Ising spin model using an Ising machine to search for its ground state which translates to the optimal solution of the problem. Secondly, in order to facilitate the search, we propose a novel technique to visualize the landscape of the search and demonstrate how difficult it is to solve QKP on an Ising machine. Finally, we propose two software solution improvement algorithms to efficiently solve QKP on an Ising machine.
Hengyong XIANG Li ZHOU Xiaohui BA Jie CHEN
The traditional RANSAC samples uniformly in the dataset which is not efficient in the task with rich prior information. This letter proposes GUISAC (Guided Sample Consensus), which samples with the guidance of various prior information. In image matching, GUISAC extracts seed points sets evenly on images based on various prior factors at first, then it incorporates seed points sets into the sampling subset with a growth function, and a new termination criterion is used to decide whether the current best hypothesis is good enough. Finally, experimental results show that the new method GUISAC has a great advantage in time-consuming than other similar RANSAC methods, and without loss of accuracy.
Takahide OTOMO Shinya MOCHIDUKI Eriko ISHII Yuko HOSHINO Mitsuho YAMADA
We can enjoy various video contents such as movies in several ways. In this report, we show the effects of content differences on physiological parameters such as eye movements and CFF. This time we confirmed the difference in responses that after watching a movie. In addition, a consistent change that can infer that due to a movie was also indicated. Our results showed that content differences affect the parameters. This suggests the possibility that the influence of movie contents on the viewer can be evaluated by physiological parameters.
Tsuyoshi KUSHIMA Miyuki SUGANUMA Shinya MOCHIDUKI Mitsuho YAMADA
Over the last 10 years, tablets have spread to the point where we can now read electronic books (e-books) like paper books. There is a long history of studies of eye movement during reading. Remarkable results have been reported for reading experiments in which displayed letters are changed in conjunction with eye movement during reading. However, these studies were conducted in the 1970s, and it is difficult to judge the detailed descriptions of the experimental techniques and whether the display time was correctly controlled when changing letters. Here, we propose an experimental system to control the display information exactly, as well as the display time, and inspect the results of past reading research, with the aim of being at the forefront of reading research in the e-book era.
Haosheng ZHANG Aravind THARAYIL NARAYANAN Hans HERDIAN Bangan LIU Rui WU Atsushi SHIRANE Kenichi OKADA
This paper presents a high power efficient pulse VCO with tail-filter for the chip-scale atomic clock (CSAC) application. The stringent power and clock stability specifications of next-generation CSAC demand a VCO with ultra-low power consumption and low phase noise. The proposed VCO architecture aims for the high power efficiency, while further reducing the phase noise using tail filtering technique. The VCO has been implemented in a standard 45nm SOI technology for validation. At an oscillation frequency of 5.0GHz, the proposed VCO achieves a phase noise of -120dBc/Hz at 1MHz offset, while consuming 1.35mW. This translates into an FoM of -191dBc/Hz.
In this study, we propose a statistical reputation approach for constructing a reliable packet route in ad-hoc sensor networks. The proposed method uses reputation as a measurement for router node selection through which a reliable data route is constructed for packet delivery. To refine the reputation, a transaction density is defined here to showcase the influence of node transaction frequency over the reputation. And to balance the energy consumption and avoid choosing repetitively the same node with high reputation, node remaining energy is also considered as a reputation factor in the selection process. Further, a shortest-path-tree routing protocol is designed so that data packets can reach the base station through the minimum intermediate nodes. Simulation tests illustrate the improvements in the packet delivery ratio and the energy utilization.
Kousuke KANAZAWA Shota KAZUNO Makiko OKUMURA
In this paper, we developed saccade-induced line displays including flashing period controllers. The displays speeded up the flashing period of one line using LED drivers and Arduino Uno equipped with AVR microcomputers. It was shown that saccades were easily induced when the observer alternately looks at the two fast flashing line displays apart. Also, we were able to find the optimum flashing period using a controller that can speed up the flashing period and change its speed. We found that the relationship between the viewing angle of the observer and the optimum flashing period is almost proportional.
Hirofumi SUZUKI Shin-ichi MINATO
Finding Pareto-optimal solutions is a basic approach in multi-objective combinatorial optimization. In this paper, we focus on the 0-1 multi-objective knapsack problem, and present an algorithm to enumerate all its Pareto-optimal solutions, which improves upon the method proposed by Bazgan et al. Our algorithm is based on dynamic programming techniques using an efficient data structure called zero-suppressed binary decision diagram (ZDD), which handles a set of combinations compactly. In our algorithm, we utilize ZDDs for storing all the feasible solutions compactly, and pruning inessential partial solutions as quickly as possible. As an output of the algorithm, we can obtain a useful ZDD indexing all the Pareto-optimal solutions. The results of our experiments show that our algorithm is faster than the previous method for various types of three- and four-objective instances, which are difficult problems to solve.
Hyunhak SHIN Bonhwa KU Wooyoung HONG Hanseok KO
Most conventional research on target motion analysis (TMA) based on least squares (LS) has focused on performing asymptotically unbiased estimation with inaccurate measurements. However, such research may often yield inaccurate estimation results when only a small set of measurement data is used. In this paper, we propose an accurate TMA method even with a small set of bearing measurements. First, a subset of measurements is selected by a random sample consensus (RANSAC) algorithm. Then, LS is applied to the selected subset to estimate target motion. Finally, to increase accuracy, the target motion estimation is refined through a bias compensation algorithm. Simulated results verify the effectiveness of the proposed method.
Bilal MASOOD Waheed Aftab KHAN Manzoor ELLAHI Talha ARSHAD Muhammad Farooq AMJAD Arslan TAHIR Muhammad USMAN
This paper proposes a technique for broadcasting control of Smart Air Conditioners (SACs) by implementing the Narrowband Powerline Communications (NB-PLC) technology. The Master Control Room (MCR) generates commands for SACs operation that are sent over power lines by using the communication protocol known as Smart Energy Profile 1.0 (SEP 1.0). The proposed system can also offers features like Demand Response (DR) to facilitate the Smart Grid (SG). Field measurements elucidate the performance of NB-PLC systems. Measurements are carried out by injecting and receiving the NB-PLC signal over low voltage (LV) power lines, medium voltage (MV) power lines and across transformers. A hybrid communication system, NB-PLC integrated with Optical Fiber Network (OFN), is developed for the automation of Distribution System (DS) of Lahore Electric Supply Company (LESCO). The developed system was tested for the DR program in order to support the Smart Air Conditioning system within Lahore. It is suggested that by adjusting the commercial SACs parameters, the task of energy conservation can be achieved by optimizing the peak load curves for greater efficiency. Moreover, data of various types of appliances can also be communicated to the MCR for the purpose of demand side management.
Tomohiro YOSHIHARA Dai KOBAYASHI Haruo YOKOTA
Many concurrency control protocols for B-trees use latch-coupling because its execution is efficient on a single machine. Some studies have indicated that latch-coupling may involve a performance bottleneck when using multicore processors in a shared-everything environment, but no studies have considered the possible performance bottleneck caused by sending messages between processing elements (PEs) in shared-nothing environments. We propose two new concurrency control protocols, “LCFB” and “LCFB-link”, which require no latch-coupling in optimistic processes. The LCFB-link also innovates B-link approach within each PE to reduce the cost of modifications in the PE, as a solution to the difficulty of consistency management for the side pointers in a parallel B-tree. The B-link algorithm is well known as a protocol without latch-coupling, but B-link has the difficulty of guaranteeing the consistency of the side pointers in a parallel B-tree. Experimental results in various environments indicated that the system throughput of the proposed protocols was always superior to those of the conventional protocols, particularly in large-scale configurations, and using LCFB-link was effective for higher update ratios. In addition, to mitigate access skew, data should migrate between PEs. We have demonstrated that our protocols always improve the system throughput and are effective as concurrency controls for data migration.
Akitoshi ITAI Arao FUNASE Andrzej CICHOCKI Hiroshi YASUKAWA
This paper describes the background noise estimation technique of the tensor product expansion with absolute error (TPE-AE) to estimate multiple sources. The electroencephalogram (EEG) signal produced by the saccadic eye movement is adopted to analyze relationship between a brain function and a human activity. The electrooculogram (EOG) generated by eye movements yields significant problems for the EEG analysis. The denoising of EOG artifacts is important task to perform an accurate analysis. In this paper, the two types of TPE-AE are proposed to estimates EOG and other components in EEG during eye movement. One technique estimates two outer products using median filter based TPE-AE. The another technique uses a reference signal to separate the two sources. We show that the proposed method is effective to estimate and separate two sources in EEG.
Theint Theint THU Jimpei HAMAMURA Rie SOEJIMA Yuichiro SHIBATA Kiyoshi OGURI
Field Programmable Gate Array (FPGA) based robust model fitting enjoys immense popularity in image processing because of its high efficiency. This paper focuses on the tradeoff analysis of real-time FPGA implementation of robust circle and ellipse estimations based on the random sample consensus (RANSAC) algorithm, which estimates parameters of a statistical model from a data set of feature points which contains outliers. In particular, this paper mainly highlights implementation alternatives for solvers of simultaneous equations and compares Gauss-Jordan elimination and Cramer's rule by changing matrix size and arithmetic processes. Experimental evaluation shows a Cramer's rule approach coupled with long integer arithmetic can reduce most hardware resources without unacceptable degradation of estimation accuracy compared to floating point versions.
Keisuke MASHITA Maya TABUCHI Ryohei YAMADA Tomoaki TSUMURA
Lock-based thread synchronization techniques have been commonly used in parallel programming on multi-core processors. However, lock can cause deadlocks and poor scalabilites, and Transactional Memory (TM) has been proposed and studied for lock-free synchronization. On TMs, transactions are executed speculatively in parallel as long as they do not encounter any conflicts on shared variables. On general HTMs: hardware implementations of TM, transactions which have conflicted once each other will conflict repeatedly if they will be executed again in parallel, and the performance of HTM will decline. To address this problem, in this paper, we propose a conflict prediction to avoid conflicts before executing transactions, considering historical data of conflicts. The result of the experiment shows that the execution time of HTM is reduced 59.2% at a maximum, and 16.8% on average with 16 threads.