Luo CHEN Ye WU Wei XIONG Ning JING
In terms of spatial online aggregation, traditional stand-alone serial methods gradually become limited. Although parallel computing is widely studied nowadays, there scarcely has research conducted on the index-based parallel online aggregation methods, specifically for spatial data. In this letter, a parallel multilevel indexing method is proposed to accelerate spatial online aggregation analyses, which contains two steps. In the first step, a parallel aR tree index is built to accelerate aggregate query locally. In the second step, a multilevel sampling data pyramid structure is built based on the parallel aR tree index, which contribute to the concurrent returned query results with certain confidence degree. Experimental and analytical results verify that the methods are capable of handling billion-scale data.
Toshiki SHIBAHARA Kohei YAMANISHI Yuta TAKATA Daiki CHIBA Taiga HOKAGUCHI Mitsuaki AKIYAMA Takeshi YAGI Yuichi OHSITA Masayuki MURATA
The number of infected hosts on enterprise networks has been increased by drive-by download attacks. In these attacks, users of compromised popular websites are redirected toward websites that exploit vulnerabilities of a browser and its plugins. To prevent damage, detection of infected hosts on the basis of proxy logs rather than blacklist-based filtering has started to be researched. This is because blacklists have become difficult to create due to the short lifetime of malicious domains and concealment of exploit code. To detect accesses to malicious websites from proxy logs, we propose a system for detecting malicious URL sequences on the basis of three key ideas: focusing on sequences of URLs that include artifacts of malicious redirections, designing new features related to software other than browsers, and generating new training data with data augmentation. To find an effective approach for classifying URL sequences, we compared three approaches: an individual-based approach, a convolutional neural network (CNN), and our new event de-noising CNN (EDCNN). Our EDCNN reduces the negative effects of benign URLs redirected from compromised websites included in malicious URL sequences. Evaluation results show that only our EDCNN with proposed features and data augmentation achieved a practical classification performance: a true positive rate of 99.1%, and a false positive rate of 3.4%.
This letter proposes a novel speech enhancement system based on the ‘L’ shaped triple-microphone. The modified coherence-based algorithm and the first-order differential beamforming are combined to filter the spatial distributed noise. The experimental results reveal that the proposed algorithm achieves significant performance in spatial filtering under different noise scenarios.
The Domain Name System (DNS) maps domain names to IP addresses. It is an important infrastructure in the Internet. Recently, DNS has experienced various security threats. DNS resolvers experience the security threats most frequently, since they interact with clients and they are the largest group of domain name servers. In order to eliminate security threats against DNS resolvers, it is essential to improve their “health status”. Since DNS resolvers' owners are not clear which DNS resolvers should be improved and how to improve “health status”, the evaluation of “health status” for DNS resolvers has become vital. In this paper, we emphasize five indicators describing “health status” for DNS resolvers, including security, integrity, availability, speed and stability. We also present nine metrics measuring the indicators. Based on the measurement of the metrics, we present a “health status” evaluation method with factor analysis. To validate our method, we measured and evaluated more than 30,000 DNS resolvers in China and Japan. The results showed that the proposed “health status” evaluation method could describe “health status” well. We also introduce instructions for evaluating a small number of DNS resolvers. And we discuss DNSSEC and its effects on resolution speed. At last, we make suggestions for inspecting and improving “health status” of DNS resolvers.
Shijie LIN Chen DONG Zhiqiang WANG Wenzhong GUO Zhenyi CHEN Yin YE
A Lévy search strategy based chaotic artificial bee colony algorithm (LABC) is proposed in this paper. The chaotic sequence, global optimal mechanism and Lévy flight mechanism were introduced respectively into the initialization, the employed bee search and the onlooker bee search. The experiments show that the proposed algorithm performed better in convergence speed, global search ability and optimization accuracy than other improved ABC.
Yilin HOU Ziwei DENG Xina CHENG Takeshi IKENAGA
In real-time 3D ball tracking of sports analysis in computer vision technology, complex algorithms which assure the accuracy could be time-consuming. Particle filter based algorithm has a large potential to accelerate since the algorithm between particles has the chance to be paralleled in heterogeneous CPU-GPU platform. Still, with the target multi-view 3D ball tracking algorithm, challenges exist: 1) serial flowchart for each step in the algorithm; 2) repeated processing for multiple views' processing; 3) the low degree of parallelism in reweight and resampling steps for sequential processing. On the CPU-GPU platform, this paper proposes the double stream system flow, the view priority based threads allocation, and the binary search oriented reweight. Double stream system flow assigns tasks which there is no data dependency exists into different streams for each frame processing to achieve parallelism in system structure level. View priority based threads allocation manipulates threads in multi-view observation task. Threads number is view number multiplied by particles number, and with view priority assigning, which could help both memory accessing and computing achieving parallelism. Binary search oriented reweight reduces the time complexity by avoiding to generate cumulative distribution function and uses an unordered array to implement a binary search. The experiment is based on videos which record the final game of an official volleyball match (2014 Inter-High School Games of Men's Volleyball held in Tokyo Metropolitan Gymnasium in Aug. 2014) and the test sequences are taken by multiple-view system which is made of 4 cameras locating at the four corners of the court. The success rate achieves 99.23% which is the same as target algorithm while the time consumption has been accelerated from 75.1ms/frame in CPU environment to 3.05ms/frame in the proposed system which is 24.62 times speed up, also, it achieves 2.33 times speedup compared with basic GPU implemented work.
Two kinds of problems - multiterminal hypothesis testing and one-to-many lossy source coding - are investigated in a unified way. It is demonstrated that a simple key idea, which is developed by Iriyama for one-to-one source coding systems, can be applied to multiterminal source coding systems. In particular, general bounds on the error exponents for multiterminal hypothesis testing and one-to-many lossy source coding are given.
In many applications, tables are distributively stored in different data sources, but the frequency of updates on each data source is different. Some techniques have been proposed to effectively express the temporal orders between different values, and the most current, i.e. up-to-date, value of a given data item can be easily picked up according to the temporal orders. However, the currency of the data items in the same table may be different. That is, when a user asks for a table D, it cannot be ensured that all the most current values of the data items in D are stored in a single table. Since different data sources may have overlaps, we can construct a conjunctive query on multiple tables to get all the required current values. In this paper, we formalize the conjunctive query as currency preserving query, and study how to generate the minimized currency preserving query to reduce the cost of visiting different data sources. First, a graph model is proposed to represent the distributed tables and their relationships. Based on the model, we prove that a currency preserving query is equivalent to a terminal tree in the graph, and give an algorithm to generate a query from a terminal tree. After that, we study the problem of finding minimized currency preserving query. The problem is proved to be NP-hard, and some heuristics strategies are provided to solve the problem. Finally, we conduct experiments on both synthetic and real data sets to verify the effectiveness and efficiency of the proposed techniques.
Chuang ZHU Xiao Feng HUANG Guo Qing XIANG Hui Hui DONG Jia Wen SONG
In this paper, we propose a highly efficient mobile visual search algorithm. For descriptor extraction process, we propose a low complexity feature detection which utilizes the detected local key points of the coarse octaves to guide the scale space construction and feature detection in the fine octave. The Gaussian and Laplacian operations are skipped for the unimportant area, and thus the computing time is saved. Besides, feature selection is placed before orientation computing to further reduce the complexity of feature detection by pre-discarding some unimportant local points. For the image retrieval process, we design a high-performance reranking method, which merges both the global descriptor matching score and the local descriptor similarity score (LDSS). In the calculating of LDSS, the tf-idf weighted histogram matching is performed to integrate the statistical information of the database. The results show that the proposed highly efficient approach achieves comparable performance with the state-of-the-art for mobile visual search, while the descriptor extraction complexity is largely reduced.
Hosung PARK Seungsoo NAM Eun Man CHOI Daeseon CHOI
Hidden Singer is a television program in Korea. In the show, the original singer and four imitating singers sing a song in hiding behind a screen. The audience and TV viewers attempt to guess who the original singer is by listening to the singing voices. Usually, there are few correct answers from the audience, because the imitators are well trained and highly skilled. We propose a computerized system for distinguishing the original singer from the imitating singers. During the training phase, the system learns only the original singer's song because it is the one the audience has heard before. During the testing phase, the songs of five candidates are provided to the system and the system then determines the original singer. The system uses a 1-class authentication method, in which only a subject model is made. The subject model is used for measuring similarities between the candidate songs. In this problem, unlike other existing studies that require artist identification, we cannot utilize multi-class classifiers and supervised learning because songs of the imitators and the labels are not provided during the training phase. Therefore, we evaluate the performances of several 1-class learning algorithms to choose which one is more efficient in distinguishing an original singer from among highly skilled imitators. The experiment results show that the proposed system using the autoencoder performs better (63.33%) than other 1-class learning algorithms: Gaussian mixture model (GMM) (50%) and one class support vector machines (OCSVM) (26.67%). We also conduct a human contest to compare the performance of the proposed system with human perception. The accuracy of the proposed system is found to be better (63.33%) than the average accuracy of human perception (33.48%).
Yutian CHEN Wenyan GAN Shanshan JIAO Youwei XU Yuntian FENG
Recent researches on mobile robots show that convolutional neural network (CNN) has achieved impressive performance in visual place recognition especially for large-scale dynamic environment. However, CNN leads to the large space of image representation that cannot meet the real-time demand for robot navigation. Aiming at this problem, we evaluate the feature effectiveness of feature maps obtained from the layer of CNN by variance and propose a novel method that reserve salient feature maps and make adaptive binarization for them. Experimental results demonstrate the effectiveness and efficiency of our method. Compared with state of the art methods for visual place recognition, our method not only has no significant loss in precision, but also greatly reduces the space of image representation.
Kohei MATSUZAKI Kazuyuki TASAKA Hiromasa YANAGIHARA
We propose a feature design method for a mobile visual search based on binary features and a bag-of-visual words framework. In mobile visual search, detection error and quantization error are unavoidable due to viewpoint changes and cause performance degradation. Typical approaches to visual search extract features from a single view of reference images, though such features are insufficient to manage detection and quantization errors. In this paper, we extract features from multiview synthetic images. These features are selected according to our novel reliability measure which enables robust recognition against various viewpoint changes. We regard feature selection as a maximum coverage problem. That is, we find a finite set of features maximizing an objective function under certain constraints. As this problem is NP-hard and thus computationally infeasible, we explore approximate solutions based on a greedy algorithm. For this purpose, we propose novel constraint functions which are designed to be consistent with the match conditions in the visual search method. Experiments show that the proposed method improves retrieval accuracy by 12.7 percentage points without increasing the database size or changing the search procedure. In other words, the proposed method enables more accurate search without adversely affecting the database size, computational cost, and memory requirement.
Pattaravut MALEEHUAN Yuki CHIBA Toshiaki AOKI
In multiprocessors, memory models are introduced to describe the executions of programs among processors. Relaxed memory models, which relax the order of executions, are used in the most of the modern processors, such as ARM and POWER. Due to a relaxed memory model could change the program semantics, the executions of the programs might not be the same as our expectation that should preserve the program correctness. In addition to relaxed memory models, the way to execute an instruction is described by an instruction semantics, which varies among processor architectures. Dealing with instruction semantics among a variety of assembly programs is a challenge for program verification. Thus, this paper proposes a way to verify a variety of assembly programs that are executed under a relaxed memory model. The variety of assembly programs can be abstracted as the way to execute the programs by introducing an operation structure. Besides, there are existing frameworks for modeling relaxed memory models, which can realize program executions to be verified with a program property. Our work adopts an SMT solver to automatically reveal the program executions under a memory model and verify whether the executions violate the program property or not. If there is any execution from the solver, the program correctness is not preserved under the relaxed memory model. To verify programs, an experimental tool was developed to encode the given programs for a memory model into a first-order formula that violates the program correctness. The tool adopts a modeling framework to encode the programs into a formula for the SMT solver. The solver then automatically finds a valuation that satisfies the formula. In our experiments, two encoding methods were implemented based on two modeling frameworks. The valuations resulted by the solver can be considered as the bugs occurring in the original programs.
Takeshi HOMMA Yasunari OBUCHI Kazuaki SHIMA Rintaro IKESHITA Hiroaki KOKUBO Takuya MATSUMOTO
For voice-enabled car navigation systems that use a multi-purpose cloud speech recognition service (cloud ASR), utterance classification that is robust against speech recognition errors is needed to realize a user-friendly voice interface. The purpose of this study is to improve the accuracy of utterance classification for voice-enabled car navigation systems when inputs to a classifier are error-prone speech recognition results obtained from a cloud ASR. The role of utterance classification is to predict which car navigation function a user wants to execute from a spontaneous utterance. A cloud ASR causes speech recognition errors due to the noises that occur when traveling in a car, and the errors degrade the accuracy of utterance classification. There are many methods for reducing the number of speech recognition errors by modifying the inside of a speech recognizer. However, application developers cannot apply these methods to cloud ASRs because they cannot customize the ASRs. In this paper, we propose a system for improving the accuracy of utterance classification by modifying both speech-signal inputs to a cloud ASR and recognized-sentence outputs from an ASR. First, our system performs speech enhancement on a user's utterance and then sends both enhanced and non-enhanced speech signals to a cloud ASR. Speech recognition results from both speech signals are merged to reduce the number of recognition errors. Second, to reduce that of utterance classification errors, we propose a data augmentation method, which we call “optimal doping,” where not only accurate transcriptions but also error-prone recognized sentences are added to training data. An evaluation with real user utterances spoken to car navigation products showed that our system reduces the number of utterance classification errors by 54% from a baseline condition. Finally, we propose a semi-automatic upgrading approach for classifiers to benefit from the improved performance of cloud ASRs.
Tomoki SUGIURA Jaehoon YU Yoshinori TAKEUCHI
A phase locking value (PLV) in electrocorticography is an essential indicator for analysis of cognitive activities and detection of severe diseases such as seizure of epilepsy. The PLV computation requires a simultaneous pursuit of high-throughput and low-cost implementation in hardware acceleration. The PLV computation consists of bandpass filtering, Hilbert transform, and mean phase coherence (MPC) calculation. The MPC calculation includes trigonometric functions and divisions, and these calculations require a lot of computational amounts. This paper proposes an MPC calculation method that removes high-cost operations from the original MPC with mathematically identical derivations while the conventional methods sacrifice either computational accuracy or throughput. This paper also proposes a hardware implementation of MPC calculator whose latency is 21 cycles and pipeline interval is five cycles. Compared with the conventional implementation with the same standard cell library, the proposed implementation marks 2.8 times better hardware implementation efficiency that is defined as throughput per gate counts.
Masayuki ARAI Shingo INUYAMA Kazuhiko IWASAKI
As semiconductor device manufacturing technology evolves toward higher integration and reduced feature size, the gap between the defect level estimated at the design stage and that reported for fabricated devices has become wider, making it more difficult to control total manufacturing cost including test cost and cost for field failure. To estimate fault coverage more precisely considering occurrence probabilities of faults, we have proposed weighted fault coverage estimation based on critical area corresponding to each fault. Previously different fault models were handled separately; thus, pattern compression efficiency and runtime were not optimized. In this study, we propose a fast test pattern generation scheme that considers weighted bridge and open fault coverage in an integrated manner. The proposed scheme applies two-step test pattern generation, wherein test patterns generated at second step that target only bridge faults are reordered with a search window of fixed size, achieving O(n) computational complexity. Experimental results indicate that with 10% of the initial target fault size and a fixed, small window size, the proposed scheme achieves approximately 100 times runtime reduction when compared to simple greedy-based reordering, in exchange for about 5% pattern count increment.
Taito MANABE Yuichiro SHIBATA Kiyoshi OGURI
The super-resolution technology is one of the solutions to fill the gap between high-resolution displays and lower-resolution images. There are various algorithms to interpolate the lost information, one of which is using a convolutional neural network (CNN). This paper shows an FPGA implementation and a performance evaluation of a novel CNN-based super-resolution system, which can process moving images in real time. We apply horizontal and vertical flips to input images instead of enlargement. This flip method prevents information loss and enables the network to make the best use of its patch size. In addition, we adopted the residue number system (RNS) in the network to reduce FPGA resource utilization. Efficient multiplication and addition with LUTs increased a network scale that can be implemented on the same FPGA by approximately 54% compared to an implementation with fixed-point operations. The proposed system can perform super-resolution from 960×540 to 1920×1080 at 60fps with a latency of less than 1ms. Despite resource restriction of the FPGA, the system can generate clear super-resolution images with smooth edges. The evaluation results also revealed the superior quality in terms of the peak signal-to-noise ratio (PSNR) and the structural similarity (SSIM) index, compared to systems with other methods.
Shotaro SUGIYAMA Hiromitsu AWANO Makoto IKEDA
A 256-bit $mathbb{F}_p$ ECDSA crypto processor featuring low latency, low energy consumption and capability of changing the Elliptic curve parameters is designed and fabricated in SOTB 65nm CMOS process. We have demonstrated the lowest ever reported signature generation time of 31.3 μs at 238MHz clock frequency. Energy consumption is 3.28 μJ/signature-generation, which is same as the lowest reported till date. We have also derived addition formulae on Elliptic curve useful for reduce the number of registers and operation cycles.
Masaru OYA Masao YANAGISAWA Nozomu TOGAWA
Modern digital integrated circuits (ICs) are often designed and fabricated by third parties and tools, which can make IC design/fabrication vulnerable to malicious modifications. The malicious circuits are generally referred to as hardware Trojans (HTs) and they are considered to be a serious security concern. In this paper, we propose a logic-testing based HT detection and classification method utilizing steady state learning. We first observe that HTs are hidden while applying random test patterns in a short time but most of them can be activated in a very long-term random circuit operation. Hence it is very natural that we learn steady signal-transition states of every suspicious Trojan net in a netlist by performing short-term random simulation. After that, we simulate or emulate the netlist in a very long time by giving random test patterns and obtain a set of signal-transition states. By discovering correlation between them, our method detects HTs and finds out its behavior. HTs sometimes do not affect primary outputs but just leak information over side channels. Our method can be successfully applied to those types of HTs. Experimental results demonstrate that our method can successfully identify all the real Trojan nets to be Trojan nets and all the normal nets to be normal nets, while other existing logic-testing HT detection methods cannot detect some of them. Moreover, our method can successfully detect HTs even if they are not really activated during long-term random simulation. Our method also correctly guesses the HT behavior utilizing signal transition learning.
Tsukasa YOSHIDA Kazuho WATANABE
Lasso regression based on the L1 regularization is one of the most popular sparse estimation methods. It is often required to set appropriately in advance the regularization parameter that determines the degree of regularization. Although the empirical Bayes approach provides an effective method to estimate the regularization parameter, its solution has yet to be fully investigated in the lasso regression model. In this study, we analyze the empirical Bayes estimator of the one-parameter model of lasso regression and show its uniqueness and its properties. Furthermore, we compare this estimator with that of the variational approximation, and its accuracy is evaluated.