Fast and accurate estimation of missing relations, e.g., similarity, distance and kernel, among objects is now one of the most important techniques required by major data mining tasks, because the missing information of the relations is needed in many applications such as economics, psychology, and social network communities. Though some approaches have been proposed in the last several years, the practical balance between their required computation amount and obtained accuracy are insufficient for some class of the relation estimation. The objective of this paper is to formalize a problem to quickly and efficiently estimate missing relations among objects from the other known relations among the objects and to propose techniques called “PSD Estimation” and “Row Reduction” for the estimation problem. This technique uses a characteristic of the relations named “Positive Semi-Definiteness (PSD)” and a special assumption for known relations in a matrix. The superior performance of our approach in both efficiency and accuracy is demonstrated through an evaluation based on artificial and real-world data sets.

View full abstract

In this paper, we address latency issue in Xen-ARM virtual machines. Despite the advantages of virtualization in mobile systems, the current Xen-ARM is difficult to apply to mobile devices because it has unpredictable I/O latency. This paper analyzes the latency of incoming packet handling in Xen-ARM, and presents how virtualization affects the latency in detail. To make the latency predictable, firstly, we modify Xen-ARM scheduler so that the driver domain can be promptly scheduled by the hypervisor. Secondly, we introduce additional paravirtualization of guest OS that minimizes non-preemptible code path. With our enhancements, 99% of incoming packets are predictably handled within one millisecond at the destined guest OS, which is a feasible time bound for most soft real-time applications.

View full abstract

In recent years, user-supplied reviews have increased to become widely prevalent on many websites. Some reviewers (users who comment on items) provide valuable information. Others provide information many people already know. Our goal is to identify credible reviewers who provide valuable information. Two methods can be used to measure reviewer credibility: assessing reviewers based on the content of reviews that they have written in the past and assessing reviewers based on their review histories. By comparing these methods, we aim at obtaining knowledge to determine which method is most useful for identifying credible reviewers. Additionally, many features have been proposed for assessing reviews or reviewers in the previous methods, but they have not been compared. We compare these attributes and clarify what kinds of attribute are useful for identifying credible reviewers.

View full abstract

In recent years, there has been an increasing demand with regard to available elemental services provided by independent firms for compositing new services. Currently, however, whenever it is difficult to maintain the required level of quality of a new composite web service, assignment of the new computer's resources as provisioning at the data center is not always effective, especially in the area of performance for composite web service providers. Thus, a new approach might be required. This paper presents a new control method aiming to maintain the performance requirements for composite web services. There are three aspects of our method that are applied: first of all, the theory of constraints (TOC) proposed by E.M. Goldratt; secondly, an evaluation process in the non-linear feed forward controlling method: and finally multiple trials in applying policies with verification. In particular, we will discuss the architectural and theoretical aspects of the method in detail, and will show the insufficiency of combining the feedback controlling approach with TOC as a result of our evaluation.

View full abstract

An instrument that can efficiently measure individual competency of IT applications (ICITA) is presented. It allows an organization to develop and manage the IT application capability of individuals working in an enterprise IT environment. The measurement items are generated from the definition and major components of individual competency of IT applications. The reliability and validity of the instrument construct are verified by factor and correlation analysis. A 15-item instrument is proposed to efficiently measure individual competency of IT applications and the instrument will contribute to the improved ICITA of human resources working in an enterprise IT environment.

View full abstract

To acquire a second language, one must develop an ear and tongue for the correct stress and intonation patterns of that language. In English language teaching, there is an effective method called Jazz Chants for working on the sound system. In this paper, we propose a method for predicting stressed words, which play a crucial role in Jazz Chants. The proposed method is specially designed for stress prediction in Jazz chants. It exploits several sources of information including words, POSs, sentence types, and the constraint on the number of stressed words in a chant text. Experiments show that the proposed method achieves an F-measure of 0.939 and outperforms the other methods implemented for comparison. The proposed method is expected to be useful in supporting non-native teachers of English when they teach chants to students and create chant texts with stress marks from arbitrary texts.

View full abstract

Link prediction is the task of inferring the existence or absence of certain relationships among data objects such as identity, interaction, and collaboration. Link prediction is found in various applications in the fields of information integration, recommender systems, bioinformatics, and social network analysis. The increasing interest in dynamically changing networks has led to growing interest in a more general link prediction problem called temporal link prediction in the data mining and machine learning communities. However, only links among nodes at the same time point are considered in temporal link prediction. We propose a new link prediction problem called cross-temporal link prediction in which the links among nodes at different time points are inferred. A typical example of cross-temporal link prediction is cross-temporal entity resolution to determine the identity of real entities represented by data objects observed in different time periods. In dynamic environments, the features of data change over time, making it difficult to identify cross-temporal links by directly comparing observed data. Other examples of cross-temporal links are asynchronous communications in social networks such as Facebook and Twitter, where a message is posted in reply to a previous message. We adopt a dimension reduction approach to cross-temporal link prediction; that is, data objects in different time frames are mapped into a common low-dimensional latent feature space, and the links are identified on the basis of the distance between the data objects. The proposed method uses different low-dimensional feature projections in different time frames, enabling it to adapt to changes in the latent features over time. Using multi-task learning, it jointly learns a set of feature projection matrices from the training data, given the assumption of temporal smoothness of the projections. The optimal solutions are obtained by solving a single generalized eigenvalue problem. Experiments using a real-world set of bibliographic data for cross-temporal entity resolution and a real-world set of emails for unobserved asynchronous communication inference showed that introducing time-dependent feature projections improved the accuracy of link prediction.

View full abstract

This paper describes a new method for semi-supervised discriminative language modeling, which is designed to improve the robustness of a discriminative language model (LM) obtained from manually transcribed (labeled) data. The discriminative LM is implemented as a log-linear model, which employs a set of linguistic features derived from word or phoneme sequences. The proposed semi-supervised discriminative modeling is formulated as a multi-objective optimization programming problem (MOP), which consists of two objective functions defined on both labeled lattices and automatic speech recognition (ASR) lattices as unlabeled data. The objectives are coherently designed based on the expected risks that reflect information about word errors for the training data. The model is trained in a discriminative manner and acquired as a solution to the MOP problem. In transcribing Japanese broadcast programs, the proposed method reduced relatively a word error rate by 6.3% compared with that achieved by a conventional trigram LM.

View full abstract

Image warping is usually used to perform real-time geometric transformation of the images captured by the CMOS image sensor of video camera. Several existing look-up table (LUT)-based algorithms achieve real-time performance; however, the size of the LUT is still large, and it has to be stored in off-chip memory. To reduce latency and bandwidth due to the use of off-chip memory, this paper proposes an improved LUT (ILUT) scheme that compresses the LUT to the point that it can be stored in on-chip memory. First, a one-step transformation is adopted instead of using several on-line calculation stages. The memory size of the LUT is then reduced by utilizing the similarity of neighbor coordinates, as well as the symmetric characteristic of video camera images. Moreover, an elaborate pipeline hardware structure, cooperating with a novel 25-point interpolation algorithm, is proposed to accelerate the system and reduce further memory usage. The proposed system is implemented by a field-programmable gate array (FPGA)-based platform. Two different examples show that the proposed ILUT achieves real-time performance with small memory usage and low system requirements.

View full abstract

A novel enhancement for the memory-based particle filter is proposed for visual pose tracking under severe occlusions. The enhancement is the addition of a detection-based memory acquisition mechanism. The memory-based particle filter, called M-PF, is a particle filter that predicts prior distributions from past history of target state stored in memory. It can achieve high robustness against abrupt changes in movement direction and quick recovery from target loss due to occlusions. Such high performance requires sufficient past history stored in the memory. Conventionally, M-PF conducts online memory acquisition which assumes simple target dynamics without occlusions for guaranteeing high-quality histories of the target track. The requirement of memory acquisition narrows the coverage of M-PF in practice. In this paper, we propose a new memory acquisition mechanism for M-PF that well supports application in practical conditions including complex dynamics and severe occlusions. The key idea is to use a target detector that can produce additional prior distribution of the target state. We call it M-PFDMA for M-PF with detection-based memory acquisition. The detection-based prior distribution well predicts possible target position/pose even in limited-visibility conditions caused by occlusions. Such better prior distributions contribute to stable estimation of target state, which is then added to memorized data. As a result, M-PFDMA can start with no memory entries but soon achieve stable tracking even in severe conditions. Experiments confirm M-PFDMA's good performance in such conditions.

View full abstract

There are many web sites where net users can post and distribute their illustration images. A typical way to draw a digital illustration is first to draw rough lines on a paper and then to trace the lines on a graphics-tablet by hand. The input lines usually contain fluctuation due to hand-drawing, which limits the quality of illustration. Therefore, it is important to remove the fluctuation and to smooth the lines while maintaining sharp features such as corners. Although naive applications of moving average filters can smooth input lines, they may cause over-smoothing artifacts in which sharp features are lost by the filtering. This paper describes an improved line smoothing method using adaptive moving averages, which smoothes input lines while keeping high curvature points. The proposed method evaluates curvatures of input lines and adaptively controls the filter-size to reduce the over-smoothing artifacts. Experiments demonstrated advantages of the proposed method over the previous method in terms of achieving smoothing effect while still preserving sharp feature preservation.

View full abstract

In this paper we study the ploblem whether the language D(1) of all d-primitive words can be generated by a contextual grammar. It is proved that D(1) can be generated neither by an external contextual grammar nor by an internal contextual grammar, and that it can be generated by a total contextual grammar with choice.

View full abstract

Shisen-Sho is a tile-based one-player game. The instance is a set of 136 tiles embedded on 8×17 rectangular grids. Two tiles can be removed if they are labeled by the same number and if they are adjacent or can be connected with at most three orthogonal line segments. Here, line segments must not cross tiles. The aim of the game is to remove all of the 136 tiles. In this paper, we consider the generalized version of Shisen-Sho, which uses an arbitrary number of tiles embedded on rectangular grids. It is shown that deciding whether the player can remove all of the tiles is NP-complete.

View full abstract

We study the complexity of finding the minimum number of face guards which can observe the whole surface of a polyhedral terrain. Here, a face guard is allowed to be placed on the faces of a terrain, and the guard can walk around on the allocated face. It is shown that finding the minimum number of face guards is NP-hard.

View full abstract

In H.264/AVC intra frame coding, the rate-distortion optimization (RDO) is employed to select the optimal coding mode to achieve the minimum rate-distortion cost. Due to a large number of combinations of coding modes, the computational burden of Rate distortion optimization (RDO) becomes extremely high in intra prediction. In this paper, we proposed an efficient selective intra block size decision (SIB) that selects the appropriate block size for intra prediction, further proposed fast intra prediction algorithm reduces a number of modes required for RDO that significantly reduces the encoder complexity. Experimental results show that the proposed fast mode decision algorithm reduces the encoding time by up to 68% with negligible video quality degradation.

View full abstract

The problem of deciding whether a graph contains another graph appears in various applications. For solving this problem efficiently, we developed a numerical method to detect non-subgraphs, graphs which are not subgraphs of other graphs, by comparing eigenvalues of graphs. In this paper, we propose a method to make the detection more efficient by comparing of eigenvalues of graphs decomposed according to labels of the vertices and the edges. The new approach not only reduces the cost of computing eigenvalues but also increases the possibility of detecting non-subgraphs. The experimental evaluation shows the effectiveness of the proposed method.

View full abstract

Previous inter-domain fast authentication schemes only realize the authentication of user identity. We propose a trusted inter-domain fast authentication scheme based on the split mechanism network. The proposed scheme can realize proof of identity and integrity verification of the platform as well as proof of the user identity. In our scheme, when the mobile terminal moves to a new domain, the visited domain directly authenticates the mobile terminal using the ticket issued by the home domain rather than authenticating it through its home domain. We demonstrate that the proposed scheme is highly effective and more secure than contemporary inter-domain fast authentication schemes.

View full abstract

Conventional entropy measure is derived from full-band (range from 0Hz to 4kHz); however, it can not clearly describe the spectrum variability during voice-activity. Here we propose a novel concept of adaptive long-term sub-band entropy (ALT-SubEnpy) measure and combine it with a multi-thresholding scheme for voice activity detection. In detail, the ALT-SubEnpy measure developed with four part parameters of sub-entropy which uses different long-term spectral window length at each part. Consequently, the proposed ALT-SubEnpy-based algorithm recursively updates the four adaptive thresholds on each part. The proposed ALT-SubEnpy-based VAD method is shown to be an effective method while working at variable noise-level condition.

View full abstract

We introduce an entropy coding method to enhance the compression efficiency of JPEG. Because run-length coding and early-termination work more effectively for longer zero sequences, we extract ones and negative ones from the coefficients and reduce the magnitude of all coefficients by one. The extracted coefficients are encoded with a designated entropy coding method. The proposed method can transmit images in two parts progressively, where the first contains JPEG-compatible image with a small amount of degradation and the second is used to add fine details. Our method improves the compression ratio by more than 5% without sacrificing the efficiency of JPEG.

View full abstract

Microblogs are a rising social network with distinguishing features such as simplicity and convenience and has already attracted a large number of users and triggered massive information explosion concerning individuals' own statuses and opinions. While sentiment analysis of the messages in microblogs is of great value, most of present studies are on English microblogs and few are on Chinese microblogs. Compared to English, Chinese has its unique expression style, such as no spaces or other word delimiters. Furthermore, Chinese short text also has its own properties. Thus we are inspired to explore effective features for sentiment classification of Chinese short text. In this paper, we propose to study user-related sentiment classification of Chinese microblogs in terms of the statistical and semantic characteristics, and deisgn the corresponding features: ratio of positive words and negative words (PNR), position feature (POS), collocation of verbs (COL), auxiliary words (AU). Then we employ an SVM-based method to classify the sentiment. Experiments show that the features we design is effective in recognizing the sentiment of messages in microblogs.

View full abstract