Ildefons MAGRANS DE ABRIL Masashi SUGIYAMA
This letter presents the ideas and methods of the winning solution* for the Kaggle Algorithmic Trading Challenge. This analysis challenge took place between 11th November 2011 and 8th January 2012, and 264 competitors submitted solutions. The objective of this competition was to develop empirical predictive models to explain stock market prices following a liquidity shock. The winning system builds upon the optimal composition of several models and a feature extraction and selection strategy. We used Random Forest as a modeling technique to train all sub-models as a function of an optimal feature set. The modeling approach can cope with highly complex data having low Maximal Information Coefficients between the dependent variable and the feature set and provides a feature ranking metric which we used in our feature selection algorithm.
For simply-typed term rewriting systems (STRSs) and higher-order rewrite systems (HRSs) a la Nipkow, we proposed a method for proving termination, namely the static dependency pair method. The method combines the dependency pair method introduced for first-order rewrite systems with the notion of strong computability introduced for typed λ-calculi. This method analyzes a static recursive structure based on definition dependency. By solving suitable constraints generated by the analysis, we can prove termination. In this paper, we extend the method to rewriting systems for functional programs (RFPs) with product, algebraic data, and ML-polymorphic types. Although the type system in STRSs contains only product and simple types and the type system in HRSs contains only simple types, our RFPs allow product types, type constructors (algebraic data types), and type variables (ML-polymorphic types). Hence, our RFPs are more representative of existing functional programs than STRSs and HRSs. Therefore, our result makes a large contribution to applying theoretical rewriting techniques to actual problems, that is, to proving the termination of existing functional programs.
Yikui ZHAI Junying GAN Jinwen LI Junying ZENG Ying XU
Due to security demand of society development, real-time face recognition has been receiving more and more attention nowadays. In this paper, a real-time face recognition system via Local Binary Pattern (LBP) plus Improved Biomimetic Pattern Recognition (BPR) has been proposed. This system comprises three main steps: real-time color face detection process, feature extraction process and recognition process. Firstly, a color face detector is proposed to detect face with eye alignment and simultaneous performance; while in feature extraction step, LBP method is adopted to eliminate the negative effect of the light heterogeneity. Finally, an improved BPR method with Selective Sampling construction is applied to the recognition system. Experiments on our established database named WYU Database, PUT Database and AR Database show that this real-time face recognition system can work with high efficiency and has achieved comparable performance with the state-of-the-art systems.
Dung Tien NGO Tuan Anh LE Choong Seon HONG Sungwon LEE Won-Tae LEE Jae-Jo LEE
Probabilistic Packet Marking (PPM) is a scheme for IP traceback where each packet is marked randomly with an IP address of one router on the attack path in order for the victim to trace the source of attacks. In previous work, a network coding approach to PPM (PPM+NC) where each packet is marked with a random linear combination of router IP addresses was introduced to reduce number of packets required to infer the attack path. However, the previous work lacks a formal proof for benefit of network coding to PPM and its proposed scheme is restricted. In this paper, we propose a novel method to prove a strong theorem for benefit of network coding to PPM in the general case, which compares different perspectives (interests of collecting) at the collector in PPM+NC scheme. Then we propose Core PPM+NC schemes based on our core network coding approach to PPM. From experiments, we show that our Core PPM+NC schemes actually require less number of packets than previous schemes to infer the attack path. In addition, based on the relationship between Coupon Collector's Problem (CCP) and PPM, we prove that there exists numerous designs that CCP still benefits from network coding.
Hiroshi YAMAMOTO Katsuyuki YAMAZAKI
With the wide-spread use of high-speed network connections and high performance mobile/sensor terminals available, new interactive services based on real-time contents have become available over the Internet. In these services, end-nodes (e.g, smart phone, sensors), which are dispersed over the Internet, generates the real-time contents (e.g, live video, sensor data about human activity), and those contents are utilized to support many kinds of human activities seen in the real world. For the services, a new decentralized contents distribution system which can accommodate a large number of content distributions and which can minimize the end-to-end streaming delay between the content publisher and the subscribers is proposed. In order to satisfy the requirements, the proposed content distribution system is equipped with utilizing two distributed resource selection methods. The first method, distributed hash table (DHT)-based contents management, makes it possible for the system to efficiently decide and locate the server managing content distributions in completely decentralized manner. And, the second one, location-aware server selection, is utilized to quickly select the appropriate servers that distribute the streamed contents to all subscribers in real time. This paper considers the performance of the proposed resource selection methods using a realistic computer simulation and shows that the system with the proposed methods has scalability for a large-scale distributed system that attracts a very large number of users, and achieves real-time locating of the contents without degrading end-to-end streaming delay of content.
Reed-Solomon (RS) code is one of the well-known and widely used error correction codes. Among the components of a hardware RS decoder, the key equation solver (KES) unit occupies a relatively large portion of the hardware. It is important to develop an efficient KES architecture to implement efficient RS decoders. In this paper, a novel polynomial division technique used in the Euclidean algorithm (EA) of the KES is presented which achieves the short critical path delay of one Galois multiplier and one Galois adder. Then a KES architecture with the EA is proposed which is efficient in the sense of the product of area and time.
Xuefeng BAI Tiejun ZHANG Chuanjun WANG Ahmed A. ABD EL-LATIF Xiamu NIU
Player detection is an important part in sports video analysis. Over the past few years, several learning based detection methods using various supervised two-class techniques have been presented. Although satisfactory results can be obtained, a lot of manual labor is needed to construct the training set. To overcome this drawback, this letter proposes a player detection method based on one-class SVM (OCSVM) using automatically generated training data. The proposed method is evaluated using several video clips captured from World Cup 2010, and experimental results show that our approach achieves a high detection rate while keeping the training set construction's cost low.
Atsushi KANNO Pham TIEN DAT Toshiaki KURI Iwao HOSAKO Tetsuya KAWANISHI Yoshihiro YASUMURA Yuki YOSHIDA Ken-ichi KITAYAMA
We propose a coherent optical and radio seamless network concept that allows broadband access without deployment of additional optical fibers within an optical fiber dead zone while enhancing network resilience to disasters. Recently developed radio-over-fiber (RoF) and digital coherent detection technologies can seamlessly convert between optical and radio signals. A millimeter-wave radio with a capacity greater than 10 Gb/s and high-speed digital signal processing is feasible for this purpose. We provide a preliminary demonstration of a high-speed, W-band (75–110 GHz) radio that is seamlessly connected to an optical RoF transmitter using a highly accurate optical modulation technique to stabilize the center frequencies of radio signals. Using a W-band digital receiver with a sensitivity of -37 dBm, we successfully transmitted an 18.6 Gb/s quadrature-phase-shift-keying signal through both air and an optical fiber.
Ryuichi FUJIMOTO Mizuki MOTOYOSHI Kyoya TAKANO Minoru FUJISHIMA
The design and measured results of a 120 GHz/140 GHz dual-channel OOK (ON-OFF Keying) receiver are presented in this paper. Because a signal with very wide frequency width is difficult to process in a single-channel receiver, a dual-channel configuration with channel selection is adopted in the proposed receiver. The proposed receiver is fabricated using 65 nm CMOS technology. The measured data rate of 3.0 and 3.6 Gbps, minimum sensitivity of -25.6 and -27.1 dBm, communication distance of 0.30 and 0.38 m are achieved in the 120- and 140-GHz receiver, respectively. The correct channel selection is achieved in the 120-GHz receiver. These results indicate the possibility of the CMOS multiband receiver operating at over 100 GHz for low-power high-speed proximity wireless communication systems.
Longjiang QU Qingping DAI Chao LI
In this paper, we give some results towards the conjecture that σ2t+1l-1,2t are the only nonlinear balanced elementary symmetric Boolean functions where t and l are positive integers. At first, a unified and simple proof of some earlier results is shown. Then a property of balanced elementary symmetric Boolean functions is presented. With this property, we prove that the conjecture is true for n=2m+2t-1 where m,t (m>t) are two non-negative integers, which verified the conjecture for a large infinite class of integer n.
Kazuhisa YAMAGISHI Taichi KAWANO Takanori HAYASHI Jiro KATTO
Three-dimensional (3D) video service is expected to be introduced as a next-generation television service. Stereoscopic video is composed of two 2D video signals for the left and right views, and these 2D video signals are encoded. Video quality between the left and right views is not always consistent because, for example, each view is encoded at a different bit rate. As a result, the video quality difference between the left and right views degrades the quality of stereoscopic video. However, these characteristics have not been thoroughly studied or modeled. Therefore, it is necessary to better understand how the video quality difference affects stereoscopic video quality and to model the video quality characteristics. To do that, we conducted subjective quality assessments to derive subjective video quality characteristics. The characteristics showed that 3D video quality was affected by the difference in video quality between the left and right views, and that when the difference was small, 3D video quality correlated with the highest 2D video quality of the two views. We modeled these characteristics as a subjective quality metric using a training data set. Finally, we verified the performance of our proposed model by applying it to unknown data sets.
Fast string matching is essential for deep packet inspection (DPI). Traditional string matchers cannot keep up with the continuous increases in data rates due to their natural speed limits. We add a multi-byte processing prefilter to the traditional string matcher to detect target patterns on a multiple character basis. The proposed winnowing prefilter significantly reduces the number of identity blocks, thereby reducing the memory requirements.
Chao-Min SU Chih-Wei YI Peng-Jun WAN
A wireless node is called isolated if it has no links to other nodes. The number of isolated nodes in a wireless network is an important connectivity index. However, most previous works on analytically determining the number of isolated nodes were not based on practical channel models. In this work, we study this problem using a generic probabilistic channel model that can capture the behaviors of the most widely used channel models, including the disk graph model, the Bernoulli link model, the Gaussian white noise model, the Rayleigh fading model, and the Nakagami fading model. We derive the expected number of isolated nodes and further prove that their distribution asymptotically follows a Poisson distribution. We also conjecture that the nonexistence of isolated nodes asymptotically implies the connectivity of the network, and that the probability of connectivity follows the Gumbel function.
Kenshi SAHO Takuya SAKAMOTO Toru SATO Kenichi INOUE Takeshi FUKUDA
The imaging of humans using radar is promising for surveillance systems. Although conventional radar systems detect the presence or position of intruders, it is difficult to acquire shape and motion details because the resolution is insufficient. This paper presents a high-resolution human imaging algorithm for an ultra-wideband (UWB) Doppler radar. The proposed algorithm estimates three-dimensional human images using interferometry and, using velocity information, rejects false images created by the interference of body parts. Experiments verify that our proposed algorithm achieves adequate pedestrian imaging. In addition, accurate shape and motion parameters are extracted from the estimated images.
Qian ZHANG Yuhan DONG Xuedan ZHANG Benzhou JIN Xiaokang LIN
The traditional selection cooperation scheme selects the relay with best instantaneous receive signal-to-noise ratio to forward the message and achieves good outage performance, which may however cause poor fairness among relays. In this letter, we propose two practical selection cooperation schemes in Decode-and-Forward (DF) fashion to improve the fairness of relay selection. Numerical results suggest that both of the proposed schemes can achieve fairness close to the strict fairness scheme without outage performance deterioration. It is also validated that these schemes have lower complexities than traditional ones and therefore are practical for real networks.
This paper presents analysis and design of passive RC polyphase filters (RCPFs) in tutorial style. Single-phase model of a single-stage RCPF is derived, and then, multi-stage RCPFs are analyzed and obtained some restrictions for realizable poles and zeros locations of RCPFs. Exact design methods of RCPFs with equal ripple type, and Butterworth type responses are explained for transfer function design and element value design along with some design examples.
As the number of nodes in high-performance computing (HPC) systems increases, parallel I/O becomes an important issue: collective I/O is the specialized parallel I/O that provides the function of single-file based parallel I/O. Collective I/O in most message passing interface (MPI) libraries follows a two-phase I/O scheme in which the particular processes, namely I/O aggregators, perform important roles by engaging the communications and I/O operations. This approach, however, is based on a single-core architecture. Because modern HPC systems use multi-core computational nodes, the roles of I/O aggregators need to be re-evaluated. Although there have been many previous studies that have focused on the improvement of the performance of collective I/O, it is difficult to locate a study regarding the assignment scheme for I/O aggregators that considers multi-core architectures. In this research, it was discovered that the communication costs in collective I/O differed according to the placement of the I/O aggregators, where each node had multiple I/O aggregators. The performance with the two processor affinity rules was measured and the results demonstrated that the distributed affinity rule used to locate the I/O aggregators in different sockets was appropriate for collective I/O. Because there may be some applications that cannot use the distributed affinity rule, the collective I/O scheme was modified in order to guarantee the appropriate placement of the I/O aggregators for the accumulated affinity rule. The performance of the proposed scheme was examined using two Linux cluster systems, and the results demonstrated that the performance improvements were more clearly evident when the computational node of a given cluster system had a complicated architecture. Under the accumulated affinity rule, the performance improvements between the proposed scheme and the original MPI-IO were up to approximately 26.25% for the read operation and up to approximately 31.27% for the write operation.
Tomoyuki KITADA Jun CHENG Yoichiro WATANABE
A direction-of-arrival estimation (DoA) scheme that uses a uniform circular array (UCA) is proposed for near-field sources, where multiple pairs-of-subarrays exist with central symmetry. First, multiple generalized ESPRIT (G-ESPRIT) spectrums are obtained by applying the conventional G-ESPRIT algorithm to each of multiple pairs-of-subarrays. Second, a parallel spectrum is found by adding up the reciprocals of these G-ESPRIT spectrums and taking the reciprocal of the total. The locations of peaks in the parallel spectrum give the DoAs being estimated. When a DoA approaches the translation direction of two subarrays, the conventional G-ESPRIT spectrum is broken by a false peak. Since the translation directions of pairs-of-subarrays are different from each other, the false peak, due to the DoA approaching one of translation directions, does not exist simultaneously in all G-ESPRIT spectrums. The parallel concatenation of the spectrums suppresses the false peak and enhances the true DoA peaks. Simulation shows that the proposed scheme reduces the root mean square error of the DoA estimation, compared with the conventional G-ESPRIT algorithm.
Errong PEI Xiaorong JING Fang CHENG
In OFDM-based cognitive radio systems, due to the out-of-band leakage from the secondary transmission, the interference to primary users must be considered in order to guarantee the quality of service of the primary transmission. For multiuser cognitive radio systems, there exist two crucial issues in resource allocation: fairness and efficiency, in order to balance the two issues, we proposed a new utility-based cross-layer resource allocation algorithm, which can not only control the interference to primary users caused by secondary users, but also balance the spectral efficiency and fairness among cognitive users. Further, the optimal NP-hard resource allocation problem in multiuser OFDM-based systems is reduced to the sub-optimal solution by dividing the original problem into the subcarrier allocation problem and the power allocation problem. It is shown that the proposed algorithm can obtain the best performance in terms of the average rate or the utility among existing algorithms, and at the same time, all the users obtain fair resource allocation.
There has recently been much research on content-based image retrieval (CBIR) that uses image features including color, shape, and texture. In CBIR, feature extraction is important because the retrieval result depends on the image feature. Query-by-sketch image retrieval is one of CBIR and query-by-sketch image retrieval is efficient because users simply have to draw a sketch to retrieve the desired images. In this type of retrieval, selecting the optimum feature extraction method is important because the retrieval result depends on the image feature. We have developed a query-by-sketch image retrieval method that uses an edge relation histogram (ERH) as a global and local feature intended for binary line images. This histogram is based on the patterns of distribution of other line pixels centered on each line pixel that have been obtained by global and local processing. ERH, which is a shift- and scale-invariant feature, focuses on the relation among the edge pixels. It is fairly simple to describe rotation- and symmetry-invariant features, and query-by-sketch image retrieval using ERH makes it possible to perform retrievals that are not affected by position, size, rotation, or mirroring. We applied the proposed method to 20,000 images in the Corel Photo Gallery. Experimental results showed that it was an effective means of retrieving images.