Konlakorn WONGPATIKASEREE Azman Osman LIM Mitsuru IKEDA Yasuo TAN
Activity recognition has recently been playing an important role in several research domains, especially within the healthcare system. It is important for physicians to know what their patients do in daily life. Nevertheless, existing research work has failed to adequately identify human activity because of the variety of human lifestyles. To address this shortcoming, we propose the high performance activity recognition framework by introducing a new user context and activity location in the activity log (AL2). In this paper, the user's context is comprised by context-aware infrastructure and human posture. We propose a context sensor network to collect information from the surrounding home environment. We also propose a range-based algorithm to classify human posture for combination with the traditional user's context. For recognition process, ontology-based activity recognition (OBAR) is developed. The ontology concept is the main approach that uses to define the semantic information and model human activity in OBAR. We also introduce a new activity log ontology, called AL2 for investigating activities that occur at the user's location at that time. Through experimental studies, the results reveal that the proposed context-aware activity recognition engine architecture can achieve an average accuracy of 96.60%.
Millimeter-wave synthetic aperture imaging radiometer (SAIR) is a powerful sensor for near-field high-resolution observations. However, the large receiver number and system complexity affect the application of SAIR. To overcome this shortage (receiver number), an accurate imaging algorithm based on compressed sensing (CS) theory is proposed in this paper. For reconstructing the brightness temperature images accurately from the sparse SAIR with fewer receivers, the proposed CS-based imaging algorithm is used to accomplish the sparse reconstruction with fewer visibility samples. The reconstruction is performed by minimizing the $l_{1}$ norm of the transformed image. Compared to the FFT-based methods based on Fourier transform, the required receiver number can be further reduced by this method. The simulation results demonstrate that the proposed CS-based method has higher reconstruction accuracy for the sparse SAIR.
Kotaro OKAMOTO Naofumi HOMMA Takafumi AOKI
This paper presents a graph-based approach to designing arithmetic circuits over Galois fields (GFs) using normal basis representations. The proposed method is based on a graph-based circuit description called Galois-field Arithmetic Circuit Graph (GF-ACG). First, we extend GF-ACG representation to describe GFs defined by normal basis in addition to polynomial basis. We then apply the extended design method to Massey-Omura parallel multipliers which are well known as typical multipliers based on normal basis. We present the formal description of the multipliers in a hierarchical manner and show that the verification time can be greatly reduced in comparison with those of the conventional techniques. In addition, we design GF exponentiation circuits consisting of the Massey-Omura parallel multipliers and an inversion circuit over composite field GF(((22)2)2) in order to demonstrate the advantages of normal-basis circuits over polynomial-basis ones.
Xuyun NIE Albrecht PETZOLDT Johannes BUCHMANN Fagen LI
The Piece in Hand method is a security enhancement technique for Multivariate Public Key Cryptosystems (MPKCs). Since 2004, many types of this method have been proposed. In this paper, we consider the 2-layer nonlinear Piece in Hand method as proposed by Tsuji et al. in 2009. The key point of this method is to introduce an invertible quadratic polynomial map on the plaintext variables to add perturbation to the original MPKC. An additional quadratic map allows the owner of the secret key to remove this perturbation from the system. By our analysis, we find that the security of the enhanced scheme depends mainly on the structure of the quadratic polynomials of this auxiliary map. The two examples proposed by Tsuji et al. for this map can not resist the Linearization Equations attack. Given a valid ciphertext, we can easily get a public key which is equivalent to that of the underlying MPKC. If there exists an algorithm that can recover the plaintext corresponding to a valid ciphertext of the underlying MPKC, we can construct an algorithm that can recover the plaintext corresponding to a valid ciphertext of the enhanced MPKC.
Shinobu NAGAYAMA Tsutomu SASAO Jon T. BUTLER Mitchell A. THORNTON Theodore W. MANIKAS
In the optimization of decision diagrams, variable reordering approaches are often used to minimize the number of nodes. However, such approaches are less effective for analysis of multi-state systems given by monotone structure functions. Thus, in this paper, we propose algorithms to minimize the number of edges in an edge-valued multi-valued decision diagram (EVMDD) for fast analysis of multi-state systems. The proposed algorithms minimize the number of edges by grouping multi-valued variables into larger-valued variables. By grouping multi-valued variables, we can reduce the number of nodes as well. To show the effectiveness of the proposed algorithms, we compare the proposed algorithms with conventional optimization algorithms based on a variable reordering approach. Experimental results show that the proposed algorithms reduce the number of edges by up to 15% and the number of nodes by up to 47%, compared to the conventional ones. This results in a speed-up of the analysis of multi-state systems by about three times.
Due to the recent development of underlying hardware technology and improvement in installing environments, public display has been becoming more common and attracting more attention as a new type of signage. Any signage is required to make its content more attractive to its viewers by evaluating the current attractiveness on the fly, in order to deliver the message from the sender more effectively. However, most previous methods for public display require time to reflect the viewers' evaluations. In this paper, we present a novel system, called Mood-Learning Public Display, which automatically adapts its content design. This system utilizes viewers' involuntary behaviors as a sign of evaluation to make the content design more adapted to local viewers' tastes evolutionarily on site. The system removes the current gap between viewers' expectations and the content actually displayed on the display, and makes efficient mutual transmission of information between the cyberworld and the reality.
Binyue LIU Guiguo FENG Wangmei GUO
This paper studies an underlay-based cognitive two-way relay network which consists of a primary network (PN) and a secondary network (SN). Two secondary users (SUs) exchange information with the aid of multiple single-antenna amplify-and-forward relays while a primary transmitter communicates with a primary receiver in the same spectrum. Unlike the existing contributions, the transmit powers of the SUs and the distributed beamforming weights of the relays are jointly optimized to minimize the sum interference power from the SN to the PN under the quality-of-service (QoS) constraints of the SUs determined by their output signal-to-interference-plus-noise ratio (SINR) and the transmit power constraints of the SUs and relays. This approach leads to a non-convex optimization problem which is computationally intractable in general. We first investigate two necessary conditions that optimal solutions should satisfy. Then, the non-convex minimization problem is solved analytically based on the obtained conditions for single-relay scenarios. For multi-relay scenarios, an iterative numerical algorithm is proposed to find suboptimal solutions with low computational complexity. It is shown that starting with an arbitrarily initial feasible point, the limit point of the solution sequence derived from the iterative algorithm satisfies the two necessary conditions. To apply this algorithm, two approaches are developed to find an initial feasible point. Finally, simulation results show that on average, the proposed low-complexity solution considerably outperforms the scheme without source power control and performs close to the optimal solution obtained by a grid search technique which has prohibitively high computational complexity.
Hiroyuki EBARA Yudai HIRANUMA Koki NAKAYAMA
Metaheuristic methods have been studied for combinational optimization problems for some time. Recently, a Consultant-Guided Search (CGS) has been proposed as a metaheuristic method for the Traveling Salesperson Problem (TSP). This approach is an algorithm in which a virtual person called a client creates a solution based on consultation with a virtual person called a consultant. In this research, we propose a parallel algorithm which uses the Ant Colony System (ACS) to create a solution with a consultant in a Consultant-Guided Search, and calculate an approximation solution for the TSP. Finally, we execute a computer experiment using the benchmark problems (TSPLIB). Our algorithm provides a solution with less than 2% error rate for problem instances using less than 2000 cities.
Jafar MANSOURI Morteza KHADEMI
A novel fusion method for semantic concept detection in images, called tree fusion, is proposed. Various kinds of features are given to different classifiers. Then, according to the importance of features and effectiveness of classifiers, the results of feature-classifier pairs are ranked and fused using C4.5 algorithm. Experimental results conducted on the MSRC and PASCAL VOC 2007 datasets have demonstrated the effectiveness of the proposed method over the traditional fusion methods.
Jung-Ho UM Miyoung JANG Jae-Woo CHANG
With the advances in wireless Internet and mobile positioning technology, location-based services (LBSs) have become popular. In LBSs, users must send their exact locations in order to use the services, but they may be subject to several privacy threats. To solve this problem, query processing algorithms based on a cloaking method have been proposed. The algorithms use spatial cloaking methods to blur the user's exact location in a region satisfying the required privacy threshold (k). With the cloaked region, an LBS server can execute a spatial query processing algorithm preserving their privacy. However, the existing algorithms cannot provide good query processing performance. To resolve this problem, we, in this paper, propose a k-NN query processing algorithm based on network Voronoi diagram for spatial networks. Therefore, our algorithm can reduce network expansion overhead and share the information of the expanded road network. In order to demonstrate the efficiency of our algorithms, we have conducted extensive performance evaluations. The results show that our algorithm achieves better performance on retrieval time than the existing algorithms, such as PSNN and kRNN. This is because our k-NN query processing algorithm can greatly reduce a network expansion cost for retrieving k POIs.
Shoichiro ODA Takahito TANIMURA Takeshi HOSHIDA Yuichi AKIYAMA Hisao NAKASHIMA Kyosuke SONE Zhenning TAO Jens C. RASMUSSEN
Nonlinearity compensation algorithm and soft-decision forward error correction (FEC) are considered as key technologies for future high-capacity and long-haul optical transmission system. In this report, we experimentally demonstrate the following three benefits brought by low complexity perturbation back-propagation nonlinear compensation algorithm in 224Gb/s DP-16QAM transmission over large-Aeff pure silica core fiber; (1) improvement of pre-FEC bit error ratio, (2) reshaping noise distribution to more Gaussian, and (3) reduction of cycle slip probability.
Fuxing CHEN Weiyang LIU Hui LI Dongcheng WU
The traditional multicast switch fabrics, which were mainly developed from the unicast switch fabrics, currently are not able to achieve high efficiency and flexible large-scale scalability. In the light of lattice theory and multicast concentrator, a novel multistage interconnection multicast switch fabric is proposed in this paper. Comparing to traditional multicast switch fabrics, this multicast switch fabric has the advantages of superior scalability, wire-speed, jitter-free multicast with low delay, and no queuing buffer. This paper thoroughly analyzes the performance of the proposed multicast switch fabric with supporting priority-based multicast. Simulations on packet loss rate and delay are discussed and presented at normalized load. Moreover, a detailed FPGA implementation is given. Practical network traffic tests provide evidence supporting the feasibility and stability of the proposed fabric.
Noboru KUNIHIRO Naoyuki SHINOHARA Tetsuya IZU
In this paper, we present a lattice based method on small secret exponent attack on the RSA scheme. Boneh and Durfee reduced the attack to finding the small roots of the bivariate modular equation: x(N+1+y)+1 ≡ 0 (mod e), where N is an RSA modulus and e is the RSA public key and proposed a lattice based algorithm for solving the problem. When the secret exponent d is less than N0.292, their method breaks the RSA scheme. Since the lattice used in the analysis is not full-rank, the analysis is not easy. Blömer and May proposed an alternative algorithm that uses a full-rank lattice, even though it gives a bound (d≤N0.290) that is worse than Boneh-Durfee. However, the proof for their bound is still complicated. Herrmann and May, however, have given an elementary proof for the Boneh-Durfee's bound: d≤N0.292. In this paper, we first give an elementary proof for achieving Blömer-May's bound: d≤N0.290. Our proof employs the unravelled linearization technique introduced by Herrmann and May and is rather simpler than that of Blömer-May's proof. We then provide a unified framework — which subsumes the two previous methods, the Herrmann-May and the Blömer-May methods, as a special case — for constructing a lattice that can be are used to solve the problem. In addition, we prove that Boneh-Durfee's bound: d≤N0.292 is still optimal in our unified framework.
Yichao LU Xiao PENG Guifen TIAN Satoshi GOTO
Majority-logic algorithms are devised for decoding non-binary LDPC codes in order to reduce computational complexity. However, compared with conventional belief propagation algorithms, majority-logic algorithms suffer from severe bit error performance degradation. This paper presents a low-complexity reliability-based algorithm aiming at improving error correcting ability of majority-logic algorithms. Reliability measures for check nodes are novelly introduced to realize mutual update between variable message and check message, and hence more efficient reliability propagation can be achieved, similar to belief-propagation algorithm. Simulation results on NB-LDPC codes with different characteristics demonstrate that our algorithm can reduce the bit error ratio by more than one order of magnitude and the coding gain enhancement over ISRB-MLGD can reach 0.2-2.0dB, compared with both the ISRB-MLGD and IISRB-MLGD algorithms. Moreover, simulations on typical LDPC codes show that the computational complexity of the proposed algorithm is closely equivalent to ISRB-MLGD algorithm, and is less than 10% of Min-max algorithm. As a result, the proposed algorithm achieves a more efficient trade-off between decoding computational complexity and error performance.
Katsuhisa YAMANAKA Shin-ichi NAKANO
A ladder lottery, known as the “Amidakuji” in Japan, is a network with n vertical lines and many horizontal lines each of which connects two consecutive vertical lines. Each ladder lottery corresponds to a permutation. Ladder lotteries are frequently used as natural models in many areas. Given a permutation π, an algorithm to enumerate all ladder lotteries of π with the minimum number of horizontal lines is known. In this paper, given a permutation π and an integer k, we design an algorithm to enumerate all ladder lotteries of π with exactly k horizontal lines.
Hirotoshi HONMA Yoko NAKAJIMA Yuta IGARASHI Shigeru MASUYAMA
Consider a simple undirected graph G = (V,E) with vertex set V and edge set E. Let G-u be a subgraph induced by the vertex set V-{u}. The distance δG(x,y) is defined as the length of the shortest path between vertices x and y in G. The vertex u ∈ V is a hinge vertex if there exist two vertices x,y ∈ V-{u} such that δG-u(x,y)>δG(x,y). Let U be a set consisting of all hinge vertices of G. The neighborhood of u is the set of all vertices adjacent to u and is denoted by N(u). We define d(u) = max{δG-u(x,y) | δG-u(x,y)>δG(x,y),x,y ∈ N(u)} for u ∈ U as detour degree of u. A maximum detour hinge vertex problem is to find a hinge vertex u with maximum d(u) in G. In this paper, we proposed an algorithm to find the maximum detour hinge vertex on an interval graph that runs in O(n2) time, where n is the number of vertices in the graph.
Hiroshi FUJIWARA Yasuhiro KONNO Toshihiro FUJITO
The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several options of paying both of a per-time fee and an initial fee, in addition to pure renting and buying options. Damaschke gave a lower bound of 3.62 on the competitive ratio for the case where arbitrary number of options can be offered. In this paper we propose a scheme that for the number of options given as an input, provides a lower bound on the competitive ratio, by extending the method of Damaschke. This is the first to establish a lower bound for each of the 5-or-more-option cases, for example, a lower bound of 2.95 for the 5-option case, 3.08 for the 6-option case, and 3.18 for the 7-option case. Moreover, it turns out that our lower bounds for the 3- and 4-option cases respectively coincide with the known upper bounds. We therefore conjecture that our scheme in general derives a matching lower and upper bound.
Yuma INOUE Takahisa TODA Shin-ichi MINATO
Pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure πDDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.
This paper proposes a new approach to defining and expressing algorithms: the notion of task logical algorithms. This notion allows the user to define an algorithm for a task T as a set of agents who can collectively perform T. This notion considerably simplifies the algorithm development process and can be seen as an integration of the sequential pseudocode and logical algorithms. This observation requires some changes to algorithm development process. We propose a two-step approach: the first step is to define an algorithm for a task T via a set of agents that can collectively perform T. The second step is to translate these agents into (higher-order) computability logic.
Qing LIU Tomohiro ODAKA Jousuke KUROIWA Haruhiko SHIRAI Hisakazu OGURA
This paper presents an artificial fish swarm algorithm (AFSA) to solve the multicast routing problem, which is abstracted as a Steiner tree problem in graphs. AFSA adopts a 0-1 encoding scheme to represent the artificial fish (AF), which are then subgraphs in the original graph. For evaluating each AF individual, we decode the subgraph into a Steiner tree. Based on the adopted representation of the AF, we design three AF behaviors: randomly moving, preying, and following. These behaviors are organized by a strategy that guides AF individuals to perform certain behaviors according to certain conditions and circumstances. In order to investigate the performance of our algorithm, we implement exhaustive simulation experiments. The results from the experiments indicate that the proposed algorithm outperforms other intelligence algorithms and can obtain the least-cost multicast routing tree in most cases.