The challenges posed by big data in the 21st Century are complex: Under the previous common sense, we considered that polynomial-time algorithms are practical; however, when we handle big data, even a linear-time algorithm may be too slow. Thus, sublinear- and constant-time algorithms are required. The academic research project, “Foundations of Innovative Algorithms for Big Data,” which was started in 2014 and will finish in September 2021, aimed at developing various techniques and frameworks to design algorithms for big data. In this project, we introduce a “Sublinear Computation Paradigm.” Toward this purpose, we first provide a survey of constant-time algorithms, which are the most investigated framework of this area, and then present our recent results on sublinear progressive algorithms. A sublinear progressive algorithm first outputs a temporary approximate solution in constant time, and then suggests better solutions gradually in sublinear-time, finally finds the exact solution. We present Sublinear Progressive Algorithm Theory (SPA Theory, for short), which enables to make a sublinear progressive algorithm for any property if it has a constant-time algorithm and an exact algorithm (an exponential-time one is allowed) without losing any computation time in the big-O sense.

Air quality index (AQI) is a non-dimensional index for the description of air quality, and is widely used in air quality management schemes. A novel method for Air Quality Index Forecasting based on Deep Dictionary Learning (AQIF-DDL) and machine vision is proposed in this paper. A sky image is used as the input of the method, and the output is the forecasted AQI value. The deep dictionary learning is employed to automatically extract the sky image features and achieve the AQI forecasting. The idea of learning deeper dictionary levels stemmed from the deep learning is also included to increase the forecasting accuracy and stability. The proposed AQIF-DDL is compared with other deep learning based methods, such as deep belief network, stacked autoencoder and convolutional neural network. The experimental results indicate that the proposed method leads to good performance on AQI forecasting.

A brain-computer interface (BCI) translates the brain activity into commands to control external devices. P300 speller based character recognition is an important kind of application system in BCI. In this paper, we propose a framework to integrate channel correlation analysis into P300 detection. This work is distinguished by two key contributions. First, a coefficient matrix is introduced and constructed for multiple channels with the elements indicating channel correlations. Agglomerative clustering is applied to group correlated channels. Second, the statistics of central tendency are used to fuse the information of correlated channels and generate virtual channels. The generated virtual channels can extend the EEG signals and lift up the signal-to-noise ratio. The correlated features from virtual channels are combined with original signals for classification and the outputs of discriminative classifier are used to determine the characters for spelling. Experimental results prove the effectiveness and efficiency of the channel correlation analysis based framework. Compared with the state-of-the-art, the recognition rate was increased by both 6% with 5 and 10 epochs by the proposed framework.

Visual adaptation is a universal phenomenon associated with human visual system. This adaptation affects not only the perception of low-level visual systems processing color, motion, and orientation, but also the perception of high-level visual systems processing complex visual patterns, such as facial identity and expression. Although it remains unclear for the mutual interaction mechanism between systems at different levels, this issue is the key to understand the hierarchical neural coding and computation mechanism. Thus, we examined whether the low-level adaptation influences on the high-level aftereffect by means of cross-level adaptation paradigm (i.e. color, figure adaptation versus facial identity adaptation). We measured the identity aftereffects within the real face test images on real face, color chip and figure adapting conditions. The cross-level mutual influence was evaluated by the aftereffect size among different adapting conditions. The results suggest that the adaptation to color and figure contributes to the high-level facial identity aftereffect. Besides, the real face adaptation obtained the significantly stronger aftereffect than the color chip or the figure adaptation. Our results reveal the possibility of cross-level adaptation propagation and implicitly indicate a high-level holistic facial neural representation. Based on these results, we discussed the theoretical implication of cross-level adaptation propagation for understanding the hierarchical sensory neural systems.

In policy-based management, in addition to deliver and enforce policies in managed systems, it is inevitable to manage the policy life-cycle. We mean the policy life-cycle as cyclic iteration of processes involving monitoring to see if the enforced policies actually work at operators' will and their adaptation based on monitoring. Enabling such policy life-cycle management by the current centralized management paradigm such as SNMP may, however, result in poor scalability and reliability. This is typically due to much bandwidth consumption for monitoring and communication failure between a management system and a managed system. It may also impose a heavy burden on the operators in analyzing management information for the policy adaptation. For a solution to that, we propose a scalable and reliable policy-based management scheme enabling the policy life-cycle management based on distributed management paradigm. In the scheme, we provide a new management script describing policies and how their life-cycle should be managed, and execute the script on the managed system with enough computation resources. The scheme can make the current policy-based management more scalable by reducing management traffic, more reliable by distributing management tasks to the managed systems, and more promising by relieving of the operators' burden. We implement a prototype system based on the scheme taking Differentiated Services as a policy enforcement mechanism, and evaluate the scheme from the following viewpoints: 1) the reliability, 2) relievability, and 3) scalability. The first two will be shown with a policy adaptation scenario in an operational network. The last one will be investigated in terms of the management traffic reduction by a management script, the management traffic required for the management of a management script, and the load on a managed system to execute management scripts. As deployment consideration of the proposed scheme besides technical aspects, we also discuss how the prototype system could be integrated with managed systems compliant to the standards emerging in the marketplace.

This paper describes the design and implementation of a testbed for predicting master/slave (M/S) programs written using Message Passing Interface (MPI) programs. The testbed, named M/S Emulator (MSE), aims at assisting developers in evaluating the performance of M/S programs and dynamic load-balancing strategies on clusters of PCs. In order to realize this, MSE predicts the communication time by using a realistic parallel computational model, an extension of the LogGPS model. This extended model improves the prediction accuracy on a large number of processors, because it captures the master's bottleneck: the overhead required for retrieving arrival messages from the slaves. Current MSE also employs a best effort emulation method for predicting the calculation time. In our experiments, MSE demonstrated an accurate prediction on clusters, especially on a larger number of nodes. Therefore, we believe that our extended model enables us to analyze the scalability of the M/S program performance.

This paper investigates multiple-valued code-division multiple access (MV-CDMA) techniques and circuits for intra/inter-chip communication to achieve efficient data transmission in VLSI systems. To address the problems caused by interconnection complexity, we transmit multiplexed signals inside LSI systems employing pseudo-random orthogonal m-sequences as information carriers. A new class of multiple-valued CDMA techniques for intra-chip communication is discussed to demonstrate the feasibility of eliminating co-channel interference caused by a propagation delay of signals, e.g., clock skew. This paper describes the circuit configuration and performance evaluation of MV-CDMA systems for intra-chip communication. We first explain the principle of MV-CDMA technique, and then propose a bidirectional current-mode CMOS technique to realize compact correlation circuits for CDMA. Finally, we show the Spice and MATLAB simulation results of MV-CDMA systems, which indicate the excellent capabilities of eliminating co-channel interference.

Systems comprised of multiple interacting mobile agents provide an alternate network computing paradigm that integrates remote data access, message exchange and migration; which up until now have largely been considered independently. On the surface distributed systems design could be helped by a complete specification of the different interaction patterns, however the number of possible designs in any large scale system undergoes a combinatorial explosion. As a consequence this paper focuses on basic one-to-one agent interactions, or paradigms, which can be used as building blocks; allowing larger system characteristics and performance to be understood in terms of their combination. This paper defines three basic agent paradigms and presents associated performance models. The paradigms are evaluated quantitatively in terms of network traffic, overall processing time and size of memory used, in the context of a distributed DB system developed using the Bee-gent Agent Framework. Comparison of the results and models illustrates the performance trade-off for each paradigm, which are not represented in the models, and some implementation issues of agent frameworks. The paper ends with a case study of how to select an appropriate paradigm.

This paper is intended as an investigation of scientific discoveries from a philosophical point of view. In the first half of this century, most of philosophers rather concentrated on the logical analysis of science and set the problem of discovery aside. Logical positivists distinguished a context of discovery from a context of justification and excluded the former from their analysis of scientific theories. Although Popper criticized their inductivism and suggested methodological falsificationism, he also left the elucidation of discovery to psychological inquiries. The problem of scientific discovery was proprely treated for the first time by the "New Philosophy of Science" school in the 1960's. Hanson reevaluated the method of "retroduction" on the basis of Peirce's logical theory and analysed Kepler's astronomical discovery in detail as a typical application of it. Kuhn's theory of paradigm located discoveries in the context of scientific revolutions. Moreover, he paid attention to the function of metaphor in scientific discoveries. Metaphorical use of existing terms and concepts to overcome theoretical difficulties often plays a decisive role in developping new ideas. In the period of scientific revolution, theoretical metaphors can open up new horizons of scientific research by way of juxtapositions of heterogeneous concepts. To explicate such a complicated situation we need the "rhetoric" of science rather than the "logic" of science.

This paper proposes applications of a code-division multiplexing technique to VLSI systems free from interconnection problems. We employ a pseudo-random orthogonal m-sequence carrier as a multiplexable information carrier to achieve efficient data transmission. Using orthogonal property of m-sequences, we can multiplex several computational activities into a single circuit, and execute in parallel using multiplexed data transmission with reduced interconnection. Also, randomness of m-sequences offers the high tolerance to interference (jamming), and suppression of dynamic range of signals while maintaining a sufficient signal-to-noise ratio (SNR). We demonstrate application examples of multiplex computing circuits, neural networks, and spread-spectrum image processing to show the advantages.

We present a novel replication technique for parallel applications where instances of the replicated application are active on different group of processors called replicas. The replication technique is based on the FTAG (Fault Tolerant Attribute Grammar) computation model. FTAG is a functional and attribute based model. The developed replication technique implements "active parallel replication," that is, all replicas are active and compute concurrently a different piece of the application parallel code. In our model replicas cooperate not only to detect and mask failures but also to perform parallel computation. The replication mechanisms are supported by FTAG run time system and are fully application-transparent. Different novel mechanisms for checkpointing and recovery are developed. In our model during rollback recovery only that part of the computation that was detected faulty is discarded. The replication technique takes full advantage of parallel computing to reduce overall computation time.

The Time-Slicing paradigm is a newly developed method for the training of neural networks for speech recognition. The neural net is trained to spot the syllables in a continuous stream of speech. It generates a transcription of the utterance, be it a word, a phrase, etc. Combined with a simple error recovery method the desired units (words or phrases) can be retrieved. This paradigm uses a recurrent neural network trained in a modular fashion with natural connectionist glue. It processes the input signal sequentially regardless of the input's length and immediately extracts the syllables spotted in the speech stream. As an example, this character string is then compared to a set of possible words, picking out the five closest candidates. In this paper we describe the time-slicing paradigm and the training of the recurrent neural network together with details about the training samples. It also introduces the concept of natural connectionist glue and the recurrent neural network's architecture used for this purpose. Additionally we explain the errors found in the output and the process to reduce them and recover the correct words. The recognition rates of the network and the recovery rates for the words are also shown. The presented examples and recognition rates demonstrate the potential of the time-slicing method for continuous speech recognition.

The issue about document structure recognition and document understanding is today one of interesting subjects from a viewpoint of practical applications. The research objective is to extract the meaningful data from document images interpretatively and also classify them as the predefined item data automatically. In comparison with the traditional image-processing-based approaches, the knowledge-based approaches, which make use of various knowledge in order to interpret structural/constructive features of documents, have been currently investigated as more flexible and applicable methods. In this paper, we propose a totally integrated paradigm for understanding table-form documents from a viewpoint of the architectural framework.