Cloud computing has garnered attention as a platform of query processing systems. However, data privacy leakage is a critical problem. Chowdhury et al. proposed Cryptε, which executes differential privacy (DP) over encrypted data on two non-colluding semi-honest servers. Further, the DP index proposed by these authors summarizes a dataset to prevent information leakage while improving the performance. However, two problems persist: 1) the original data are decrypted to apply sorting via a garbled circuit, and 2) the added noise becomes large because the sorted data are partitioned with equal width, regardless of the data distribution. To solve these problems, we propose a new method called DP-summary that summarizes a dataset into differentially private data over a homomorphic encryption without decryption, thereby enhancing data security. Furthermore, our scheme adopts Li et al.’s data-aware and workload-aware (DAWA) algorithm for the encrypted data, thereby minimizing the noise caused by DP and reducing the errors of query responses. An experimental evaluation using torus fully homomorphic encryption (TFHE), a bit-wise fully homomorphic encryption library, confirms the applicability of the proposed method, which summarized eight 16-bit data in 12.5 h. We also confirmed that there was no accuracy degradation even after adopting TFHE along with the DAWA algorithm.

Considering the continuous increase in the number of web pages worldwide, detecting unreliable pages, such as those containing fake news, is indispensable. Natural language processing and social-information-based methods have been proposed for web page credibility evaluation. However, the applicability of the former to web pages is limited because a model is required for each language, while the latter is poorly adapted to changes, owing to its dependence on external services that can be discontinued. To solve these problems, herein we propose a first-impression-based web credibility evaluation method. Our experimental evaluation of a fake news corpus gave an accuracy of 0.898, which is superior to those of existing methods.

Fully homomorphic encryption (FHE), which is used to evaluate arbitrary functions in addition and multiplication operations via modular arithmetic (mod q) over ciphertext, can be applied in various privacy-preserving applications. However, big data is difficult to adopt owing to its high computational cost and the challenges associated with the efficient handling of complex functions such as log(x). To address these problems, we propose a method for handling any multi-input function using a lookup table (LUT) to replace the original calculations with array indexing operations over integer-based FHE. In this study, we extend our LUT-based method to handle any input values, i.e., including non-matched element values in the LUT, to match with a near indexed value and return an approximated output over FHE. In addition, we propose a technique for splitting the table to handle large integers for improved accuracy with only a slight increase in the execution time. For the experiments, we use the Microsoft/SEAL library, and the results show that our proposed method can evaluate a 16-bit to 16-bit function in 2.110 s and a 16-bit to 32-bit function in 2.268 s, thereby outperforming previous methods implemented via bit-wise calculation over FHE.

Homomorphic encryption enables computations over encrypted data without decryption, and can be used for outsourcing computations to some untrusted source. In homomorphic encryption based on the hardness of ring-learning with errors, offering promising security and functionality, a plaintext is represented by a polynomial. A plaintext is treated as a vector whose homomorphic evaluation enables component-wise addition and multiplication, as well as rotation across the components. We focus on a commonly used and time-consuming subroutine that enables homomorphically summing-up the components of the vector or homomorphically extracting the coefficients of the polynomial, and call it homomorphic trace-type function. We improve the efficiency of the homomorphic trace-type function evaluation. The homomorphic trace-type function evaluation is performed by repeating homomorphic rotation followed by addition (rotations-and-sums). To correctly add up a rotated ciphertext and an unrotated one, a special operation called key-switching should be performed on the rotated one. As key-switching is computationally expensive, the rotations-and-sums is inherently inefficient. We propose a more efficient trace-type function evaluation by using loop-unrolling, which is compatible with other optimization techniques such as hoisting, and can exploit multi-threading. We show that the rotations-and-sums is not the optimal solution in terms of runtime complexity and that a trade-off exists between time and space. Experimental results demonstrate that our proposed method works 1.32-2.12 times faster than the previous method.

© 2020 IEEE. In location-based social networks (LBSNs), personalized point-of-interest (POI) recommendation helps users mine their interests and find new locations conveniently and quickly. It is one of the most important services to improve users' quality of life and travel. Most POI recommendation systems devoted to improve accuracy, however in recent years, diversity of POI recommendations, such as categorical and geographical diversity, receives much attention because a single type of POIs easily causes loss of users' interest. Different from previous diversity related recommendations, in this paper, we focus on visiting time of POI- A unique attribute of the interaction between users and POIs. Users usually have different active visiting time patterns and different frequently visiting POIs depending on time. If a set of proper visiting times of recommended POIs concentrates on a small range of time, the user might be unsatisfied because they cannot cover whole of the user's active time range that results in inappropriateness for the user to visit those POIs. To solve this problem, we propose a new concept-time diversity and a time distribution based recommendation method to improve time diversity of recommended POIs. Our experimental result with Gowalla dataset shows our proposed method effectively improves time diversity 25.9% compared with USG with only 7.9% accuracy loss.

In this paper, we present a novel framework for privacy-preserving anomaly-based data falsification attack detection in a smart grid advanced metering infrastructure (AMI). Specifically, we propose an anomaly detection framework over homomorphically encrypted data. Unlike existing privacy-preserving anomaly detectors, our framework detects the presence of not only energy theft (i.e., deductive attack), but also more advanced data integrity attacks (i.e., additive and camouflage attacks) over encrypted data without diminishing detection sensitivity. We optimize the anomaly detection procedure such that potentially expensive operations over homomorphically encrypted space are avoided. Moreover, we optimize the encryption method designed for a resource constrained device such as smart meters, and the time to complete encryption gets 40x faster over the naïve adoption of the encryption method. We also validate the proposed framework using a real dataset from smart metering infrastructures, and demonstrate that the data integrity attacks can be detected with high sensitivity, without sacrificing user privacy. Experimental results with a real dataset of 200 houses from an AMI in Texas showed that the detection sensitivity of the plaintext algorithm is not degraded due to the use of homomorphic encryption.

Online advertising is widely used by commercial companies to attract customers. Tuning advertisement delivery to achieve a high conversion rate (CVR) is crucial for improving advertising effectiveness. Because advertisers require demandside platforms (DSPs) to deliver a certain number of ads within a fixed period, it is challenging to maximize CVR while satisfying ads delivery constraints. Such a combinatorial optimization problem is NP-hard when we have a considerable number of both ads and users. In this paper, we adopt Digital Annealer (DA), a quantum-inspired Ising computer, to solve the combinatorial optimization problem. The experimental evaluation result shows that the proposed method increases accuracy from 0.176 to 0.326 and achieves 20.8 times speed-up compared to baseline.

In the big data era, cloud-based machine learning as a service (MLaaS) has attracted considerable attention. However, when handling sensitive data, such as financial and medical data, a privacy issue emerges, because the cloud server can access clients' raw data. A common method of handling sensitive data in the cloud uses homomorphic encryption, which allows computation over encrypted data without decryption. Previous research adopted a low-degree polynomial mapping function, such as the square function, for data classification. However, this technique results in low classification accuracy. This study seeks to improve the classification accuracy for inference processing in a convolutional neural network (CNN) while using homomorphic encryption. We apply various orders of the polynomial approximations of Google's Swish and ReLU activation functions. We also adopt batch normalization to normalize the inputs for the approximated activation functions to fit the input range to minimize the error. We implemented CNN inference labeling over homomorphic encryption using the Microsoft's Simple Encrypted Arithmetic Library (SEAL) for the Cheon-Kim-Kim-Song (CKKS) scheme. The experimental evaluations confirmed classification accuracies of 99.29% and 81.06% for MNIST and CIFAR-10, respectively, which entails 0.11% and 4.69% improvements, respectively, over previous methods.

Deep neural networks (DNNs) have improved the performance of artificial intelligence systems in various fields including image analysis, speech recognition, and text classification. However, the consumption of enormous computation resources prevents DNNs from operating on small computers such as edge sensors and handheld devices. Network pruning (NP), which removes parameters from trained DNNs, is one of the prominent methods of reducing the resource consumption of DNNs. In this paper, we propose a novel method of NP, hereafter referred to as PHPM, using persistent homology (PH). PH investigates the inner representation of knowledge in DNNs, and PHPM utilizes the investigation in NP to improve the efficiency of pruning. PHPM prunes DNNs in ascending order of magnitudes of the combinational effects among neurons, which are calculated using the one-dimensional PH, to prevent the deterioration of the accuracy. We compared PHPM with global magnitude pruning method (GMP), which is one of the common baselines to evaluate pruning methods. Evaluation results show that the classification accuracy of DNNs pruned by PHPM outperforms that pruned by GMP.

Smart computing aims to improve the quality of life by utilizing Internet-of-Things devices and cloud computing. Typically, this computing handles private and/or personal information so concealing such sensitive information is a challenge. Adopting fully homomorphic encryption (FHE) is one approach for handling such sensitive information safely; that is, we can calculate the encrypted data without decryption. However, the time and space complexity of the FHE operation is high. Thus, its computation takes a long time. In this study, we aim to shorten FHE execution time by adopting our new scheduling algorithm, which divides a task into several macro-tasks and then assigns a set of threads. We assume a cloud computing system that is equipped with a many-core CPU. Thus, we propose the dynamic allocation method of computation resource to macro-tasks (DAMCREM), which dynamically allocates a certain number of threads (selected from pre-defined candidates) to each macro-task of every given job. In the evaluation, we compared DAMCREM to naive methods that allocate a pre-defined number of threads to each macro-task. The result shows that the average latency and maximum latency of job execution is less than those of naive methods, even when the average interval of job arrival is short.

The inner representation of deep neural networks (DNNs) is indecipherable, which makes it difficult to tune DNN models, control their training process, and interpret their outputs. In this paper, we propose a novel approach to investigate the inner representation of DNNs through topological data analysis (TDA). Persistent homology (PH), one of the outstanding methods in TDA, was employed for investigating the complexities of trained DNNs. We constructed clique complexes on trained DNNs and calculated the one-dimensional PH of DNNs. The PH reveals the combinational effects of multiple neurons in DNNs at different resolutions, which is difficult to be captured without using PH. Evaluations were conducted using fully connected networks (FCNs) and networks combining FCNs and convolutional neural networks (CNNs) trained on the MNIST and CIFAR-10 data sets. Evaluation results demonstrate that the PH of DNNs reflects both the excess of neurons and problem difficulty, making PH one of the prominent methods for investigating the inner representation of DNNs.

Today’s widespread use of stroke-based touchscreen devices creates numerous associated security concerns and requires efficient security measures in response. We propose an imitation-resistant passive authentication interface for stroke-based touch screen devices employing classifiers for each individual stroke, which is evaluated with respect to 26 features. For experimental validation, we collect stroke-based touchscreen data from 23 participants containing target and imitation stroke patterns using a photo-matching game in the form of an iOS application. The equal error rate (EER), depicting the rate at which false rejection and false acceptance of target and imitator strokes are equal, is assumed as an indicator of the classification accuracy. Leave-one-out cross-validation was employed to evaluate the datasets based on the mean EER. For each cross-validation, one out of the two target datasets, an imitator dataset, and the remaining 20 imitator datasets were selected as genuine data, imitator test data, and imitator training data, respectively. Our results confirm stroke imitation as a serious threat. Among the 26 stroke features evaluated in terms of their imitation tolerance, the stroke velocity was identified as the most difficult to imitate. Dividing classifiers based on the stroke direction was found to further contribute to classification accuracy.

The Smart Systems and Services Innovative Professional Education (Smart SE) program is a certification program developed as part of the education network for the Practical information Technologies (enPiT-Pro) project, which is funded by the Japan Ministry of Education, Culture, Sports, Science and Technology. The Smart SE program provides industry professionals working in fields related to information and communication technology (ICT) with additional training and education in smart systems and services that utilize various technologies such as IoT, Cloud, Big Data, and Artificial Intelligence (AI) for businesses. Here, we illustrate its purpose, curriculum and features to respond to the needs of industrial professional education.

To protect data in cloud servers, fully homomorphic encryption (FHE) is an effective solution. In addition to encrypting data, FHE allows a third party to evaluate arithmetic circuits (i.e., computations) over encrypted data without decrypting it, guaranteeing protection even during the calculation. However, FHE supports only addition and multiplication. Functions that cannot be directly represented by additions or multiplications cannot be evaluated with FHE. A naive implementation of such arithmetic operations with FHE is a bit-wise operation that encrypts numerical data as a binary string. This incurs huge computation time and storage costs, however. To overcome this limitation, we propose an efficient protocol to evaluate multi-input functions with FHE using a lookup table. We extend our previous work, which evaluates a single-integer input function, such as f(x). Our extended protocol can handle multi-input functions, such as f(x, y). Thus, we propose a new method of constructing lookup tables that can evaluate multi-input functions to handle general functions. We adopt integer encoding rather than bit-wise encoding to speed up the evaluations. By adopting both permutation operations and a private information retrieval scheme, we guarantee that no information from the underlying plaintext is leaked between two parties: a cloud computation server and a decryptor. Our experimental results show that the runtime of our protocol for a two-input function is approximately 13 minutes, when there are 8,192 input elements in the lookup table. By adopting a multi-threading technique, the runtime can be further reduced to approximately three minutes with eight threads. Our work is more practical than a previously proposed bit-wise implementation, which requires 60 minutes to evaluate a single-input function.

In the personalized Point-Of-Interest (POI) (or venue) recommendation, the diversity of recommended POIs is an important aspect. Diversity is especially important when POIs are recommended in the target users' frequently visited areas, because users are likely to revisit such areas. In addition to the (POI) category diversity that is a popular diversification objective in recommendation domains, diversification of recommended POI locations is an interesting subject itself. Despite its importance, existing POI recommender studies generally focus on and evaluate prediction accuracy. In this article, geographical diversification (geo-diversification), a novel diversification concept that aims to increase recommendation coverage for a target users' geographic areas of interest, is introduced, from which a method that improves geo-diversity as an addition to existing state-of-the-art POI recommenders is proposed. In experiments with the datasets from two real Location Based Social Networks (LSBNs), we first analyze the performance of four state-of-the-art POI recommenders from various evaluation perspectives including category diversity and geo-diversity that have not been examined previously. The proposed method consistently improves geo-diversity (CPR(geo)@20) by 5 to 12% when combined with four state-of-the-art POI recommenders with negligible prediction accuracy (Recall@20) loss and provides 6 to 18% geo-diversity improvement with tolerable prediction accuracy loss (up to 2.4%).

Recommender systems are used to analyze users' preferences through their past activities and to personalize recommendations for each user based on what they might be interested in. The performance of the recommender system is most commonly measured using only recommendation accuracy. However, recommending accurate items does not mean that the generated recommendation is the best for the user because it can be biased towards some items that have a higher chance of being liked by users, such as popular items. Recommendations become repetitive and obvious with biased item selection and are less likely to be personalized. To mitigate bias and repetitiveness, recommendation diversity has been studied. However, diversity has a trade-off relationship with accuracy. Modifying the recommendation algorithm to consider diversity while learning about user preferences would not only cause loss in accuracy, but also lead to less precise reading of user preferences. Instead, using ranking methods to re-rank the priority of items predicted, the recommendation algorithm would keep the preciseness of the algorithm. In this study, a ranking method using the appearance frequency of items to restrict the items from being frequently recommended will be proposed. The experimental results showed that the proposed method consistently improved diversity in multiple diversity metrics.

Location-based recommendation services, such as Foursquare, enhance the convenience in the life of consumers. Users are usually sensitive to disclose their personal information. Unavoidable security concerns arise because malicious third parties could misuse confidential information, such as the users' preferences. The mainstream research to this problem is employing the privacy-preserving k-NN search algorithm. However, two major bottlenecks exist. One is that it only provides the nearest points of interest (POI) to the users without any recommendations based on the users' behavior history. This limited service eventually results in a situation in which no user would prefer to continue using it. The other is that only a single user holds the private key; thus, the service providers cannot obtain any user's information to analyze to make a profit. To solve the first problem, our proposed protocol provides recommendation services by adopting collaborative filtering techniques with an encrypted database based on fully homomorphic encryption aside from encrypting both the user's location and preferences. For the second problem, a privacy service provider (PSP) is designed to generate and hold the private key. Thus, service providers can homomorphically compute aggregate information concerning user behavior patterns and send the encrypted results to PSP to ensure decryption while maintaining the privacy of individual users. Compared with the previous studies, the novelty of the proposed protocol is the design of a commercially valuable privacy recommendation mechanism that could benefit both consumers and service providers on LBS.

Smart grids are indispensable applications in smart connected communities (SCC). To construct privacy-preserving anomaly detection systems on a smart grid, we adopt fully homomorphic encryption (FHE) to protect users' sensitive data. Although FHE allows a third party to perform calculations on encrypted data without decryption, FHE only supports addition and multiplication on encrypted data. In anomaly detection, we must calculate both harmonic and arithmetic means consisting of logarithms. A naive implementation of such arithmetic operations with FHE is a bitwise operation; thus, it requires huge computation time. To speed up such calculations, we propose an efficient protocol to evaluate any functions with FHE using a lookup table (LUT). Our protocol allows integer encoding, i.e., a set of integers is encrypted as a single ciphertext, rather than using bitwise encoding. Our experimental results in a multi-threaded environment show that the runtime of our protocol is approximately 51 s when the size of the LUT is 448,000. Our protocol is more practical than the previously proposed bitwise implementation.

© 2019 Association for Computing Machinery. Phishing is a type of personal information theft in which phishers lure users to steal sensitive information. Phishing detection mechanisms using various techniques have been developed. Our hypothesis is that phishers create fake websites with as little information as possible in a webpage, which makes it difficult for content- A nd visual similarity-based detections by analyzing the webpage content. To overcome this, we focus on the use of Uniform Resource Locators (URLs) to detect phishing. Since previous work extracts specific special-character features, we assume that non- A lphanumeric (NAN) character distributions highly impact the performance of URL-based detection. We hence propose a new feature called the entropy of NAN characters for URL-based phishing detection. Experimental evaluation with balanced and imbalanced datasets shows 96% ROC AUC on the balanced dataset and 89% ROC AUC on the imbalanced dataset, which increases the ROC AUC as 5 to 6% from without adopting our proposed feature.

© 2019 Association for Computing Machinery. The preservation of privacy during a search has become a serious problem in recent years. There is an increasing requirement to ensure that user queries are not abused by a third party, including the search provider. Fully homomorphic encryption (FHE) can conduct addition and multiplication directly over ciphertext. Using FHE, privacy, concerning both the user queries and the database of the search provider, can be protected. In this paper, we propose a privacy-preserving query system model. We implemented the proposed model in a real-world medicine side-effect query system. We applied a filtering technique, prior to the query deployment, to reduce the size of the database and used multi-threading to accelerate the search. The system was tested 10,000 times with a random query, using a database comprising 40,000 records of simulation data, and completed 99.84% of the queries within 60 seconds (s), proving the real-world applicability of our system.

© 2019 Association for Computing Machinery. In the era of big data and cloud computing, outsourcing data storage to the cloud poses the risk of its abuse or leakage. Thus, we address the problem of delegating computation on outsourced private datasets while maintaining privacy. In this study, we consider a scenario involving two data owners outsourcing their datasets to a cloud service. The cloud performs a set union computation, after which the querier sends a query to obtain information from both datasets. We propose a protocol that uses fully homomorphic encryption (FHE) and Cartesian-join of Bloom filters (CBF) as proposed by Wang et al. The protocol obtains information on the existence of a particular set of elements without learning about the residing source. To the best of our knowledge, our protocol, by using the FHE and CBF matrix, is a novel approach to ensuring the security of outsourced set union operations.

© 2019 Association for Computing Machinery. Machine learning classification has a wide range of applications. In the big data era, a client may want to outsource classification tasks to reduce the computational burden at the client. Meanwhile, an entity may want to provide a classification model and classification services to such clients. However, applications such as medical diagnosis require sensitive data that both parties may not want to reveal. Fully homomorphic encryption (FHE) enables secure computation over encrypted data without decryption. By applying FHE, classification can be outsourced to a cloud without revealing any data. However, existing studies on classification over FHE do not achieve the scenario of outsourcing classification to a cloud while preserving the privacy of the classification model, client's data and result. In this work, we apply FHE to a naïve Bayes classifier and, to the best of our knowledge, propose the first concrete secure classification protocol that satisfies the above scenario.

© 2019 IEEE. Point of interest (POI) recommendation is one of the indispensable services in location-based social networks (LBSNs). POI recommendation helps users find new locations and better understand the city. In LBSNs, the aspects, such as geographical information and categorical information, improve the accuracy of POI recommendation. In this paper, we propose two new techniques to improve the recommendation accuracy; 1) weighted center of a target user's each active area and 2) category-dependent threshold for categorical preference. The weighted center represents density-based center of a target user's active area. The geographical aspect usually adopts the target user's active areas that he frequently visited. Although previous researches define the active area by its active center and its radius, they choose the location of the most frequently visited POI as the active center even if there exist several POIs that have similar number of check-ins, which results in miss-definition of active center. Our weighted center is able to handle the target user's check-in probability, which follows a power-law distribution. Besides, previous researches predict users' preference for categories; however, they neglect the fact that different categories have different users' preference distributions. For example, a specific category has wide-range of subcategories to be preferred by user, but another category has a few subcategories to be preferred, even if there are many subcategories in the category. Thus, we set different thresholds to select candidate subcategories in each category. Experimental result with Weeplaces dataset shows that our method outperforms other baselines by at least 16.93% in F1-score@5.

© 2019, Springer Nature Switzerland AG. Biometric authentication has become popular in modern society. It takes less time and effort for users when compared to conventional password authentication. Furthermore, biometric authentication was considered more secure than password authentication because it was more difficult to steal biometric information when compared to passwords. However, given the development of high-spec cameras and image recognition technology, the risk of the theft of biometric information, such as fingerprints, is increasing. Additionally, biometric authentication exhibits lower and less stable accuracy than that of password authentication. To solve the aforementioned issues, we propose two-factor authentication combining password-input and biometric authentication of the hand. We adopt Leap Motion to measure physical and behavioral features related to hands. Subsequently, a random forest classifier determines whether the hand features belongs to a genuine user. Our authentication system architecture completes the biometric authentication by using a limited amount of data obtained within a few seconds when a user enters a password. The advantage of the proposed method is that it prevents intrusion by biometric authentication even if a password is stolen. Our experimental results for 21 testers exhibit 94.98% authentication accuracy in a limited duration, 2.52 s on an average while inputting a password.

Unreliable web pages, such as fake news, have become an unavoidable problem. To tackle this problem, recent researches have adopted both content and social features to predict the credibility of the web pages; however, the accuracy is almost saturated. In this paper, we propose the adoption of Google Lighthouse features to predict web page credibility. Our experimental results show that the proposed method achieves an increased accuracy of 7.9% in comparison with state-of-the-art methods.

© 2018 IEEE. In recent years, many users have uploaded data to the cloud for easy storage and sharing with other users. At the same time, security and privacy concerns for the data are growing. Attribute-based encryption (ABE) enables both data security and access control by defining users with attributes so that only those users who have matching attributes can decrypt them. For real-world applications of ABE, revocation of users or their attributes is necessary so that revoked users can no longer decrypt the data. In actual implementations, ABE is used in hybrid with a symmetric encryption scheme such as the advanced encryption standard (AES) where data is encrypted with AES and the AES key is encrypted with ABE. The hybrid encryption scheme requires re-encryption of the data upon revocation to ensure that the revoked users can no longer decrypt that data. To re-encrypt the data, the data owner (DO) must download the data from the cloud, then decrypt, encrypt, and upload the data back to the cloud, resulting in both huge communication costs and computational burden on the DO depending on the size of the data to be re-encrypted. In this paper, we propose an attribute-based proxy re-encryption method in which data can be re-encrypted in the cloud without downloading any data by adopting both ABE and Syalim's encryption scheme. Our proposed scheme reduces the communication cost between the DO and cloud storage. Experimental results show that the proposed method reduces the communication cost by as much as one quarter compared to that of the trivial solution.

The primary challenge in focused crawling research is how to efficiently utilize computing resources, e.g., bandwidth, disk space, and time, to find as many web pages related to a specific topic as possible. To meet this challenge, we previously introduced a machine-learning-based focused crawler that aims to crawl a group of relevant web pages located in the same directory path, called a website segment, and has achieved high efficiency so far. One of the limitations of our previous approach is that it may repeatedly visit a website that does not serve any relevant website segments, in the scenario where the website segments share the same linkage characteristics as the relevant ones in the training dataset. In this paper, we propose a "history-enhanced focused website segment crawler" to solve the problem. The idea behind it is that the priority score of an unvisited website segment should be reduced if the crawler has consecutively downloaded many irrelevant web pages from the website. To implement this idea, we propose a new prediction feature, called the "history feature", that is extracted from the recent crawling results, i.e., relevant and irrelevant web pages gathered from the target website. Our experiment shows that our newly proposed feature could improve the crawling efficiency of our focused crawler by a maximum of approximately 5%.

A focused web crawler is an essential tool for gathering domain-specific data used by national web corpora, vertical search engines, and so on, since it is more efficient than general Breadth-First or Depth-First crawlers. The problem in focused crawling research is the prioritization of unvisited web pages in the crawling frontier followed by crawling these web pages in the order of their priority. The most common feature, adopted in many focused crawling researches, to prioritize an unvisited web page is the relevancy of the set of its source web pages, i.e., its in-linked web pages. However, this feature is limited, because we cannot estimate the relevancy of the unvisited web page correctly if we have few source web pages. To solve this problem and enhance the efficiency of focused web crawlers, we propose a new feature, called the "neighborhood feature". This enables the adoption of additional already-downloaded web pages to estimate the priority of a target web page. The additionally adopted web pages consist both of web pages located at the same directory as that of the target web page and web pages whose directory paths are similar to that of the target web page. Our experimental results show that our enhanced focused crawlers outperform the crawlers not utilizing the neighborhood feature as well as the state-of-the-art focused crawlers, including HMM crawler.

Cloud database services have attracted considerable interest with the increase in the amount of data to be analyzed. Delegating data management to cloud services, however, causes security and privacy issues because cloud services are not always trustable. In this study, we address the problem of answering join queries across outsourced private datasets while maintaining data confidentiality. We particularly consider a scenario in which two data owners each own a set of elements and a querier asks the cloud to perform join operations to obtain the size of the common elements in the two datasets. To process the join operations without revealing the contents of data to the cloud, we propose two protocols, a basic protocol and a querier-friendly protocol, which adopt a functionality of outsourced private set intersection cardinality (OPSI-CA) with fully homomorphic encryption (FHE) and bloom filters. The querier-friendly protocol achieves a reduction in communication and computation costs for the querier. Our experimental results show that it takes 436 s for the basic protocol and 298 s for the querier-friendly protocol to execute the join query on the two datasets with 100 elements each. The novelty of this study is that our protocols are the first approaches for outsourced join operations adopting FHE.

Smartphone user authentication is still an open challenge because the balance between both security and usability is indispensable. To balance between them, active authentication is one way to overcome the problem. In this paper, we tackle to improve the accuracy of active authentication by adopting online learning with touch pressure. In recent years, it becomes easy to use the smartphones equipped with pressure sensor so that we have confirmed the effectiveness of adopting the touch pressure as one of the features to authenticate. Our experiments adopting online AROW algorithm with touch pressure show that equal error rate (EER), where the miss rate and false rate are equal, is reduced up to one-fifth by adding touch pressure feature. Moreover, we have confirmed that training with the data from both sitting posture and prone posture archives the best when testing variety of postures including sitting, standing and prone, which achieves EER up to 0.14%.

© 2018, Springer Nature Switzerland AG. Private comparison protocols are fundamental to the field of secure computation. Recently, Lu et al. (ASIACCS 2018) proposed a new protocol, XCMP,, which is based on a ring-based fully homomorphic encryption (FHE) scheme. In that scheme, two μ-bit integers a and b are compared in encrypted form without revealing the plaintext to an evaluator. The protocol outputs a bit in encrypted form, which indicates whether a > b. XCMP has the following three advantages: the output can be reused for further processing, the evaluation is performed without any interactions with a decryptor having a secret key, and the required multiplicative depth is only 1. However, XCMP has two potential disadvantages. First, the protocol result preserves both additive and multiplicative homomorphisms over ℤ t only, whereas the underlying FHE scheme can support a much larger plaintext space of (Formula Presented) for a prime t and a power-of-two N; this restricts the functionality of applications using the comparison result. Second, the bit length μ of the integers to be compared is no more than log N (typically 16 bits, at most). Thus, it is difficult for XCMP to handle larger integers. In this paper, we propose a non-interactive private comparison protocol that solves the aforementioned problems and outputs an additively and multiplicatively reusable comparison result over the ring without adding an extremely large computational overhead over XCMP. Moreover, by regarding a μ (>16 -bit integer as a sequence of chunks, we show that the multiplicative depth required for our comparison protocol is logarithmic in the number of chunks. This value is much smaller than the naïve solution with a multiplicative depth of log μ. Experiment results demonstrate that our protocol introduces a subtle overhead over XCMP. Remarkably, we experimentally demonstrate that our protocol for a larger domain is comparable to the construction given by one of the state-of-the-art bitwise FHE schemes.

Unreliable web pages such as fake news has become a global problem in big data era. The motivation to publish fake news is often for profit; for example, earning advertisement income by putting ads on their web pages. In this paper, we focus on different usage of HTML source tags between reliable and unreliable web pages, then propose new features for predicting their credibility. The experimental result shows that our proposed features increase accuracy when used together with previously proposed Contents features.

Recommender systems have been used for analyzing users' preference through their past activities and recommend items in which they might be interested in. There are numerous research on improving the accuracy of recommendation being conducted, so the recommender system reads user preference more accurately. However, it is important to consider the recommendation diversity, because lacking diversity will lead to recommendation being repetitive and obvious. In this paper, we propose a method to re-rank the recommendation list by appearance frequency of items to recommend more range of items. The experimental result shows that our method consistently performs better than a related work to improve recommendation diversity.

In recommending to another individual an item that one loves, accuracy is important, however in most cases, focusing only on accuracy generates less satisfactory recommendations. Studies have repeatedly pointed out that aspects that go beyond accuracy-such as the diversity and novelty of the recommended items-are as important as accuracy in making a satisfactory recommendation. Despite their importance, there is no global consensus about definitions and evaluations regarding beyond-accuracy aspects, as such aspects closely relate to the subjective sensibility of user satisfaction. In addition, devising algorithms for this purpose is difficult, because algorithms concurrently pursue the aspects in trade-off relation (i.e., accuracy vs. novelty). In the aforementioned situation, for researchers initiating a study in this domain, it is important to obtain a systematically integrated view of the domain. This paper reports the results of a survey of about 70 studies published over the last 15 years, each of which addresses recommendations that consider beyond-accuracy aspects. From this survey, we identify diversity, novelty, and coverage as important aspects in achieving serendipity and popularity unbiasedness-factors that are important to user satisfaction and business profits, respectively. The five major groups of algorithms that tackle the beyond-accuracy aspects are multi-objective, modified collaborative filtering (CF), clustering, graph, and hybrid; we then classify and describe algorithms as per this typology. The off-line evaluation metrics and user studies carried out by the studies are also described. Based on the survey results, we assert that there is a lot of room for research in the domain. Especially, personalization and generalization are considered important issues that should be addressed in future research (e.g., automatic per-user-trade-off among the aspects, and properly establishing beyond-accuracy aspects for various types of applications or algorithms).

Copyright © 2017 The Institute of Electronics, Information and Communication Engineers. In recommending to another individual an item that one loves, accuracy is important, however in most cases, focusing only on accuracy generates less satisfactory recommendations. Studies have repeatedly pointed out that aspects that go beyond accuracy—such as the diversity and novelty of the recommended items—are as important as accuracy in making a satisfactory recommendation. Despite their importance, there is no global consensus about definitions and evaluations regarding beyond-accuracy aspects, as such aspects closely relate to the subjective sensibility of user satisfaction. In addition, devising algorithms for this purpose is difficult, because algorithms concurrently pursue the aspects in trade-off relation (i.e., accuracy vs. novelty). In the aforementioned situation, for researchers initiating a study in this domain, it is important to obtain a systematically integrated view of the domain. This paper reports the results of a survey of about 70 studies published over the last 15 years, each of which addresses recommendations that consider beyond-accuracy aspects. From this survey, we identify diversity, novelty, and coverage as important aspects in achieving serendipity and popularity unbiasedness—factors that are important to user satisfaction and business profits, respectively. The five major groups of algorithms that tackle the beyond-accuracy aspects are multi-objective, modified collaborative filtering (CF), clustering, graph, and hybrid; we then classify and describe algorithms as per this typology. The off-line evaluation metrics and user studies carried out by the studies are also described. Based on the survey results, we assert that there is a lot of room for research in the domain. Especially, personalization and generalization are considered important issues that should be addressed in future research (e.g., automatic per-user-trade-off among the aspects, and properly establishing beyond-accuracy aspects for various types of applications or algorithms).

With the rapid development of cloud storage services and IoT environment, how to securely and efficiently search without compromising privacy has been an indispensable problem. In order to address such a problem, much works have been proposed for searching over encrypted data. Motivated by storing sensitive data such as genomic and medical data, substring search for encrypted data has been studied. Previous work either leaks query access pattern using vulnerable cryptographic model or performs search over plaintext data by an encrypted query. Thus they are not compatible with outsourcing scenario where searched data is stored in encrypted form which is searched by an encrypted substring query without leaking query access pattern, i.e., private substring search. In order to perform private substring search, Fully Homomorphic Encryption (FHE) can be adopted although it induces computationally huge overhead. Because of the huge overhead, performing private substring search efficiently over FHE is a challenging task. In this work, we propose a private substring search protocol over encrypted data by adopting FHE followed by examining its feasibility. In particular, we make use of batching technique which can accelerate homomorphic computation in SIMD manner. In addition, we propose a data structure which can be useful to specific searching function for batched computation. Our experimental result showed our proposed method is feasible.

In recommending POIs(Point-Of-Interests), factors such as the diversity of the recommended POIs are as important as accuracy for providing a satisfactory recommendation. Although existing diversification methods can help POI recommender systems suggest more diverse POIs, they lack "geographical diversification," which results in the concentration of the supposedly "diverse" recommended POIs on "a small portion" in areas where the target-user is most active. This is caused by the neglect of POI locations in the diversification, i.e., existing diversification methods try to diversify the categories of recommended items. However, geographical diversification is essential for users whose activity interests comprise many sub-areas and who require a variety of recommended POIs encompassing all their activity interests. In this paper, we propose a novel proportional geographical diversification method that recommends a variety of POIs located in the activity district of a user such that the variety of sub-areas in the district is proportional to the frequency of his/her activity in each sub-area. We compare the performance of the proposed method with existing diversification methods using real datasets. The evaluation result shows that no method except the proposed one can significantly increase geographical diversity at the expense of tolerable accuracy loss.

Recently, a research on eating habits of Japanese college students revealed that they have a highly desire to communicate with others through co-eating. Even though better eating experience through co-eating is important, they often tend to be alone even more because of some reasons like small households, living alone, and having no time to find others for co-eating. Therefore, we believe that it may improve eating experience by incorporating a fictional character into the real space as a partner to eat together. For validating the idea, we have developed a virtual co-eating system for solving issues caused from solitary eating, and show some insights from its user study.

Discovery of repeated patterns, known as motifs, from long time series is essential for providing hidden knowledge to real-world applications like medical, financial and weather analysis. Motifs can be discovered on raw time series directly or on their transformed abstract representation alternatively. Most of time series motif discovery methods require predefined motif length, which results in long execution time because we have to vary the length to discover motifs with different lengths. To solve the problem, we propose an efficient method for discovering variable length motifs in combination of approximate method with exact verification. First, symbolic representation is adopted to discover motifs roughly followed by exact examination of the found motifs with original real-valued data to achieve fast and exact discovery. The experiments show that our proposed method successfully discovered significant motifs efficiently in comparison with state-of-the-art methods: MK and SBF.

This position paper highlights security and privacy issues in smart environments based on cyber-physical systems. It also summarizes some of our recent research activities and projects in this area.

In the big data era, many users upload data to cloud while security concerns are growing. By using attribute-based encryption (ABE), users can securely store data in cloud while exerting access control over it. Revocation is necessary for real-world applications of ABE so that revoked users can no longer decrypt data. In actual implementations, however, revocation requires re-encryption of data in client side through download, decrypt, encrypt, and upload, which results in huge communication cost between the client and the cloud depending on the data size. In this paper, we propose a new method where the data can be re-encrypted in cloud without downloading any data. The experimental result showed that our method reduces the communication cost by one quarter in comparison with the trivial solution where re-encryption is performed in client side.

In the big data era, multithreaded processing on a many-core machine, whose core number is still increasing, has become essential to parallelize the execution of big data applications, besides distributed computing. In such a machine, malloc-intensive applications cannot scale due to lock contentions among threads, which becomes worse as the number of threads increases. To solve the problem, we propose a new method to reduce lock contentions by batch malloc, pseudo free, and fine-grained data-locking. Experimental result shows 4.72 times speed-up in comparison with JEmalloc which is the fastest memory allocator among previous ones.

© 2017 Information Processing Society of Japan. Users’ visiting patterns to POIs (Points-Of-Interest) varied with regard to the users’ familiarity with their visited areas. For instance, users visit tourist sites in unfamiliar cities rather than in their familiar home city. Previous studies have shown that familiarity can improve POI recommendation performance. However, such studies have focused on the differences between home and other cities, and not among small urban neighborhoods in the same city where user activities frequently occur. Applying the studies directly to the areas is difficult because simple distance-based familiarity measures, or visit-pattern differences represented on topics, groups of POIs that share common functions such as Arts, French restaurants, are too coarse for capturing the differences observed among different areas. In the urban neighborhoods in the same city, user visit-pattern differences originate from more precise POI levels. In order to extend the previously proposed familiarity-aware POI recommendation to be adopted in different areas in the same city, we propose a method that employs visit-frequency-based familiarity and precise POI level of visit-pattern differentiation. In experiments on real LBSN data consists of over 800,000 check-ins for three cities: NYC, LA, and Tokyo, our proposed method outperforms state-of-the-art methods by 0.05 to 0.06 in Recall@20 metric.

Purpose - The paper aims to estimate the segment size and alphabet size of Symbolic Aggregate approXimation (SAX). In SAX, time series data are divided into a set of equal-sized segments. Each segment is represented by its mean value and mapped with an alphabet, where the number of adopted symbols is called alphabet size. Both parameters control data compression ratio and accuracy of time series mining tasks. Besides, optimal parameters selection highly depends on different application and data sets. In fact, these parameters are iteratively selected by analyzing entire data sets, which limits handling of the huge amount of time series and reduces the applicability of SAX.Design/methodology/approach - The segment size is estimated based on Shannon sampling theorem (autoSAXSD_S) and adaptive hierarchical segmentation (autoSAXSD_M). As for the alphabet size, it is focused on how mean values of all the segments are distributed. The small number of alphabet size is set for large distribution to easily distinguish the difference among segments.Findings - Experimental evaluation using University of California Riverside (UCR) data sets shows that the proposed schemes are able to select the parameters well with high classification accuracy and show comparable efficiency in comparison with state-of-the-art methods, SAX and auto_iSAX.Originality/value - The originality of this paper is the way to find out the optimal parameters of SAX using the proposed estimation schemes. The first parameter segment size is automatically estimated on two approaches and the second parameter alphabet size is estimated on the most frequent average (mean) value among segments.

© 2016 ACM. The challenges in effcient data representation and similarity measures on massive amounts of time series have enormous impact on many applications. This paper addresses an improvement on Symbolic Aggregate approXimation (SAX), is one of the effcient representations for time series mining. Because SAX represents its symbols by the average (mean) value of a segment with the assumption of Gaussian distribution, it is insuficient to serve the entire deterministic information and causes sometimes incorrect results in time series classiffcation. In this work, SAX representation and distance measure is improved with the addition of another moment of the prior distribution, standard deviation; SAX SD is proposed. We provide comprehensive analysis for the proposed SAX SD and conrm both the highest classi-fication accuracy and the highest dimensionality reduction ratio on University of California, Riverside (UCR) datasets in comparison to state of the art methods such as SAX, Extended SAX (ESAX) and SAX Trend Distance (SAX TD).

Native language identification (NLI) is a process by which an author's native language can be identified from essays written in the second language of the author. In this work, a supervised model is built to accomplish this based on a Chinese learner corpus. In the NLI field, this is the first work to (1) eliminate noisy data automatically before the training phase and (2) employ a BM25 term weighting technique to score each feature. We also adopt a hierarchical structure of linear support vector machine classifiers to achieve high accuracy and a state-of-the-art accuracy of 77.1%, which is greater than those of other Chinese NLI methods by over 10%.

Short linear motifs (SLiMs) play a central role in several biological functions, such as cell regulation, scaffolding, cell signaling, post-translational modification, and cleavage. Identifying SLiMs is an important step for understanding their functions and mechanism. Due to their short length and particular properties, discovery of SLiMs in proteins is a challenge both experimentally and computationally. So far, many existing computational methods adopted many predicted sequence or structures features as input for prediction, there is no report about using position-specific scoring matrix (PSSM) profiles of proteins directly for SLiMs prediction. In this study, we describe a simple method, named as PSSMpred, which only use the evolutionary information generated in form of PSSM profiles of protein sequences for SLiMs prediction. When comparing with other methods tested on the same datasets, PSSMpred achieves the best performances: (1) achieving 0.03-0.1 higher AUC than other methods when tested on HumanTest151; (2) achieving 0.03-0.05 and 0.03-0.06 higher AUC than other methods when tested on ANCHOR-short and ANCHOR-long respectively.

Focused web crawler has become indispensable for vertical search engines that provide a search service for specialized datasets. These vertical search engines have to collect specific web pages in the web space, whereas search engines such as Google and Bing gather web pages from all over the world. The problem in focused crawling research is how to collect specific web pages with minimal computing resources. We previously addressed this problem by proposing a focused crawling strategy, which utilizes an ensemble machine learning classifier to find the group of relevant web pages, referred to as relevant website segment. In this paper, we enhance the proposed crawler as follows: 1) We increase the accuracy of predicting website segments, by preparing two predictors: a predictor learned by features extracted from relevant source website segments and another predictor learned by features from irrelevant ones. The idea is that there may exist different characteristics between these two types of source website segments. 2) We also propose a noisy data elimination method when updating the predictor incrementally during the crawling process. A preliminary experiment shows that our enhanced crawler outperforms a crawler that equips neither of these approaches by around 12%, at most.

We propose an efficient and secure frequent pattern mining protocol with fully homomorphic encryption (FHE). Nowadays, secure outsourcing of mining tasks to the cloud with FHE is gaining attentions. However, FHE execution leads to significant time and space complexities. P3CC, the first proposed secure protocol with FHE for frequent pattern mining, has these particular problems. It generates ciphertexts for each component in item-transaction data matrix, and executes numerous operations over the encrypted components. To address this issue, we propose efficient frequent pattern mining with ciphertext packing. By adopting the packing method, our scheme will require fewer ciphertexts and associated operations than P3CC, thus reducing both encryption and calculation times. We have also optimized its implementation by reusing previously produced results so as not to repeat calculations. Our experimental evaluation shows that the proposed scheme runs 430 times faster than P3CC, and uses 94.7% less memory with 10,000 transactions data.

Privacy-preserving string search is a crucial task for analyzing genomics-driven big data. In this work, we propose a cryptographic protocol that uses Fully Homomorphic Encryption (FHE) to enable a client to search on a genome sequence database without leaking his/her query to the server. Though FHE supports both addition and multiplication over encrypted data, random noise inside ciphertexts grows with every arithmetic operation especially multiplication, which results in incorrect decryption when the noise amount exceeds its threshold called level. There are two approaches to avoid the incorrect decryption: one is setting the sufficient level that assures correct decryption within the limited number of operations, and the other is resetting the noise by the method called bootstrapping. It is important to find an optimal balance between overhead caused by the level and overhead caused by the bootstrapping, since using higher level deteriorates the performance of all the arithmetic operations, while the more number of bootstrappings causes more expensive overhead. In this study, we propose an efficient approach to minimize the number of bootstrappings while reducing the level as much as possible. Our experimental result shows that it runs at most 10 times faster than a naive approach.

In the big data era, security and privacy concerns are growing. One of the big challenges is secure Frequent Pattern Mining (FPM) over Fully Homomorphic Encryption (FHE). There exist some research efforts aimed at speeding-up, however, we have a big room so as to decrease time and space complexity. Apriori over FHE, in particular, generates a large number of ciphertexts during the support calculation, which results in both large time and space complexity. To solve it, we proposed a speed-up technique, around 430 times faster and 18.9 times smaller memory usage than the state-of-the-art method, by adopting both packing and caching mechanism. In this paper, we further propose to decrease the memory space used for caching. Our goal is to discard redundant cached ciphertexts without increasing the execution time. Our experimental results show that our method decreases the memory usage by 6.09% at most in comparison with our previous method without increasing the execution time.

Purpose - The purpose of this paper is to clarify the correlations between amount of individual's knowledge of a specific area and his/her visit pattern to point of interest (POI, interested places) located in the area.Design/methodology/approach - This paper proposes a visit-frequency-based familiarity estimation method that estimates individuals' knowledge of areas in a quantitative manner. Based on the familiarity degree, individuals' visit logs to POIs are divided into a set of groups followed by analyzing the differences among the groups from various points of view, such as user preference, POI categories/popularity, visit time/date and subsequent visits.Findings - Existence of statistically significant correlations between individuals' familiarity to areas and their visit patterns is observed by our analysis using 1.4-million POI visit logs collected from a popular location-based social network (LBSN), Foursquare. There exist different skewness of the visit time and visited POI distribution/popularity with regard to the familiarity. For instance, users go to unfamiliar areas on weekends and visit POIs for cultural experiences, such as museums. Anotable point is that the correlations can be detected even in the areas in home city, which have not been known so far.Originality/value - This is the first in-depth work that studies both estimation of individuals' familiarity and correlations between the familiarity and individuals' mobility patterns by analyzing massive LBSN data. The methodologies used and the findings of this work can be applicable not only to human mobility analysis for sociology, but also to POI recommendation system design.

Human mobility analysis with Location-Based Social Network (LBSN) data is the basis of personalized point-of-interest (POI) recommendations or location-aware advertisements. In addition to personal preference and spatiotemporal factors such as time and distance, personal context has a strong influence on mobility. An individual's familiarity with an area is an interesting context because it can bias the influence of certain factors. For example, the mobility patterns of two persons who have similar preferences are different when their familiarity with the area is different, even in the same area. In this paper, we analyze familiarity's effect on mobility patterns by using over 1.4 million check-ins gathered from Foursquare. The analysis indicates that there is a skewness of the visit time and visited venue distribution in unfamiliar areas. For instance, people go to unfamiliar areas on weekends
and venues for cultural experiences, such as museums, strongly contribute to the motivation of visit.

An effective learning system is indispensable for human beings with a limited life span. Traditional learning systems schedule repetition based on both the results of a recall test and learning theories such as the spacing effect. However, there is room for improvement from the perspective of remembrance-level estimation. In this paper, we focus on on-line handwritten data obtained from handwriting using a computer. We collected handwritten data from remembrance tests to both analyze the problem of traditional estimation methods and to build a new estimation model using handwritten data as the input data. The evaluation found that our proposed model can output a continuous remembrance-level value of zero to 1, whereas traditional methods output a only binary decision. In addition, the experiment showed that our proposed model achieves the best performance with an F-value of 0.69.

Predicting various types of user-attributes in social networks has become indispensable for personalizing applications since there are many non-disclosed attributes in social networks. However, extracted attributes in existing works are limited to pre-defined types of attributes, which results in no extraction of unexpected-types of attributes. In this paper, we therefore propose a novel method that extracts various, i.e., unlimited, types of attributes by adopting personalized PageRank to a large social network. The experimental results using over 7.9 million of Japanese twitter-users show that our proposed method successfully extracts four types of attributes per-user in average with 0.841 of MAP@20.

protein functional sites. However, it is 20-dimentional and contains many redundant features. The Kidera factors were reported to contain information relating almost all physical properties of amino acids, but it requires appropriate weighting coefficients to express their properties. We developed a novel method, named as KSPSSMpred, which integrated PSSM and the Kidera Factors into a 10-dimensional matrix (KSPSSM) for ligand-binding site prediction. Flavin adenine dinucleotide (FAD) was chosen as a representative ligand for this study. When compared with five other feature-based methods on a benchmark dataset, KSPSSMpred performed the best. This study demonstrates that, KSPSSM is an effective feature extraction method which can enrich PSSM with information relating 188 physical properties of residues, and reduce 50% feature dimensions without losing information included in the PSSM.

Handwriting annotation on paper-based documents is widely performed for both appending information and emphasizing a part of the document. When we perform it on electronic documents using a computer, there are some problems about improving availability such as searching and sharing by using these annotation information. We have to estimate where is annotated on the document to solve the problem. However, the accuracy of traditional methods indicate insufficient recognition accuracy because they proposed heuristic method ignoring human habit of annotations. In this paper, we therefore propose a recognition model of handwriting targeting annotations that is important to solve these problems. Our recognition model enables to detect common targeting annotation by users such as underline, enclosure and vertical. Our user study found that the proposed model can estimate selected region for 85% on average in the selection of characters and for 91% in the selection of text lines.

Annotating documents is one of the indispensable interaction between human and documents. The annotation system of electronic documents enables to implement effective functions, such as information retrieval and annotation-based navigation, by using the annotation information
however, traditional systems require users to perform gestures in addition to common gestures for paper-based documents. This can reduce "learnability" of the system. We propose an intelligent ink annotation framework that helps the system to increase the learnability of annotation systems by detecting recognizable intentions from natural annotation behavior on paper-based documents. Our framework recognizes "Targeting Content" and "Commenting," which are related to extraction of annotation information. We have developed a prototype annotation system using our proposed framework and conducted a user study to identify future direction.

Evolutionary conservation information included in position-specific scoring matrix (PSSM) has been adopted by almost all sequence-based methods for identifying protein functional sites, because all functional sites, whether in ordered or disordered proteins, are found to be conserved to some extent. However, different functional sites have different conservation patterns, some of them are linear contextual, some of them are mingled with highly variable residues, and some others seem to be conserved independently. All existing studies used the direct output of PSSM for functional sites prediction, without considering the relationship between conservation patterns of residues and the distribution of conservation scores in PSSMs. In order to demonstrate the importance of analyzing conservation patterns, three PSSM-based methods for identifying 3 kinds of functional sites have been compared. Experiment results show that, although all the methods are based on the same feature - PSSM of protein sequence, they are competent in identifying different patterns of functional sites: the PSSM-based method is competent for identifying functional site which is independently conserved; the smoothed-PSSM is competent for identifying functional site which is continuous conserved; and the masked-smoothed- PSSM based method is competent for identifying functional site which is mingled with intensively highly flexible and highly conserved residues. Copyright © (2014) by the International Society for Computers and Their Applications.

In this paper, we propose a new image annotation method by combining content-based image annotation and tag-based image annotation techniques. Content-based image annotation technique is adopted to extract "loosely defined concepts" by analyzing pre-given images' features such as color moment (CM), edge orientation histogram (EOH), and local binary pattern (LBP); followed by constructing a set of SVMs for 100 loosely defined concepts. A base-vector for each concept, similar to tag-based image annotation technique, is then constructed by using SVMs' predicted probabilistic results for sample-images whose main concepts are known. Finally cosine similarity between a query-image vector and the base vector is calculated for each concept. Experimental results show that our proposed method outperforms content-based image annotation technique by about 23% in accuracy.

Owing to the recent development of handwriting input devices such as tablets and digital pens, digital notebooks have become an alternative to traditional paper-based notebooks. Digital notebooks are available for various device types. To display a list of text documents on a device screen, we often use scaled thumbnails or text snippets summarized through natural language processing or structural analyses. However, these are ineffective in conveying summaries of handwritten documents, because informal and unstructured handwritten data are difficult to summarize using traditional methods. We therefore propose the use of emphasis-based snippets, i.e., summarized handwritten documents based on natural emphasis annotations, such as underlines and enclosures. Our proposed method places emphasized words into thumbnails or text snippets. User studies showed that the proposed method is effective for keyword-based navigation.

Internet security issues require authorship identification for all kinds of internet contents; however, authorship identification for microblog users is much harder than other documents because microblog texts are too short. Moreover, when the number of candidates becomes large, i.e., big data, it will take long time to identify. Our proposed method solves these problems. The experimental results show that our method successfully identifies the authorship with 53.2% of precision out of 10,000 microblog users in the almost half execution time of previous method.

Evolutionary conservation information included in position-specific scoring matrix (PSSM) has been widely adopted by sequence-based methods for identifying protein functional sites, because all functional sites, whether in ordered or disordered proteins, are found to be conserved at some extent. However, different functional sites have different conservation patterns, some of them are linear contextual, some of them are mingled with highly variable residues, and some others seem to be conserved independently. Every value in PSSMs is calculated independently of each other, without carrying the contextual information of residues in the sequence. Therefore, adopting the direct output of PSSM for prediction fails to consider the relationship between conservation patterns of residues and the distribution of conservation scores in PSSMs. In order to demonstrate the importance of combining PSSMs with the specific conservation patterns of functional sites for prediction, three different PSSM-based methods for identifying three kinds of functional sites have been analyzed. Results suggest that, different PSSM-based methods differ in their capability to identify different patterns of functional sites, and better combining PSSMs with the specific conservation patterns of residues would largely facilitate the prediction.

Background: Identifying ligand-binding sites is a key step to annotate the protein functions and to find applications in drug design. Now, many sequence-based methods adopted various predicted results from other classifiers, such as predicted secondary structure, predicted solvent accessibility and predicted disorder probabilities, to combine with position-specific scoring matrix (PSSM) as input for binding sites prediction. These predicted features not only easily result in high-dimensional feature space, but also greatly increased the complexity of algorithms. Moreover, the performances of these predictors are also largely influenced by the other classifiers.Results: In order to verify that conservation is the most powerful attribute in identifying ligand-binding sites, and to show the importance of revising PSSM to match the detailed conservation pattern of functional site in prediction, we have analyzed the Adenosine-5'-triphosphate (ATP) ligand as an example, and proposed a simple method for ATP-binding sites prediction, named as CLCLpred (Contextual Local evolutionary Conservation-based method for Ligand-binding prediction). Our method employed no predicted results from other classifiers as input; all used features were extracted from PSSM only. We tested our method on 2 separate data sets. Experimental results showed that, comparing with other 9 existing methods on the same data sets, our method achieved the best performance.Conclusions: This study demonstrates that: 1) exploiting the signal from the detailed conservation pattern of residues will largely facilitate the prediction of protein functional sites; and 2) the local evolutionary conservation enables accurate prediction of ATP-binding sites directly from protein sequence.

Web crawlers must collect Web data while performing tasks such as detecting crawled URLs and preventing consecutive accesses to a particular Web server. Parallel-distributed crawling is carried out at a high speed for the enormous number of URLs existing on the Web. However, in order to crawl efficiently, a crawler must realize load balancing between computers in addition to reducing time and space complexities in the crawling process. The Web crawler proposed in this paper crawls the Web using producer-consumer modules, which compose the crawler, and it realizes load balancing per module and not per crawled Web site. In other words, it realizes load balancing that is appropriate to certain computer resources necessary for the modules that compose the Web crawler; in this way, it improves biases in computation loads and memory utilization between computers. Moreover, the crawler is able to crawl the Web on a large scale while conserving resources, because the modules that manage host names or URLs are implemented by data structures that are temporally and spatially efficient.

Detecting states of frustration among students engaged in learning activities is critical to the success of teaching assistance tools. We examine the relationship between a student's pen activity and his/her state of frustration while solving handwritten problems. Based on a user study involving mathematics problems, we found that our detection method was able to detect student frustration with a precision of 87% and a recall of 90%. We also identified several particularly discriminative features, including writing stroke number, erased stroke number, pen activity time, and air stroke speed. © 2013 Authors.

When SVM is adopted for image annotation, we know that high quality sample images will improve image recognition accuracy. Images with the same visual/semantic features are adopted as positive sample images, and images with different visual/semantic features are adopted as negative sample images. But it is labor intensive in high quality sample images selection, especially when collecting by visual features. Most researchers randomly choose positive and negative sample images for classifier training. In many applications, adopting different negative sample image datasets will vary annotation accuracy. In this research, we will discuss the accuracy between different negative sample images dataset collected by semantic features. We adopted ImageNet as image dataset in this study, and we adopted WordNet for building semantic hierarchical tree. Semantic hierarchical structure tree is adopted to calculate the distance between each node. Then we adopt this distance relationship to prepare positive and negative sample images. We prepare one baseline method and suggest six different negative sample images selection methods for experiment. The binary SVM classifier training and prediction is implemented to compare the accuracy and Mean Reciprocal Rank (MRR) between baseline and each proposed method. Our results show that if we select uniform amount of negative sample images in each distance in the semantic hierarchical tree, we will achieve highest accuracy.

We propose intensity constraint-based closed sequential pattern mining algorithm, called IC-BIDE, for a coding pattern extraction. Source code often contains frequent patterns of function calls or control flows, i.e., "coding patterns." Previous studies used sequential pattern mining to extract coding pattern; however, these algorithms have not been optimized for coding pattern extraction, which results in useless patterns as well as long execution times. We propose a new constraint, called "intensity constraint," in order to enhance closed sequential pattern mining and efficiently extract coding patterns. Our proposed algorithm is based on BI-Directional Execution (BIDE), an algorithm proposed expressly for closed sequential pattern mining. BIDE algorithm is not able to adapt to constraint-based closed sequential pattern mining. We extend BIDE algorithm and prove that our extended algorithm is able to adapt to intensity constraint-based closed sequential pattern mining. Our contributions are as follow; 1) We propose a new constraint, which we call "intensity"; 2) We propose intensity constraint-based closed sequential pattern mining algorithm, which we call "IC-BIDE" algorithm. Experimental results with open source software (Bullet Physics, MySQL, and OpenCV) show that IC-BIDE algorithm successfully excludes useless pattern effectively. Moreover, our proposed method is able to accelerate the extraction by a factor of 8.9 in comparison with the BIDE algorithm.

Background: Molecular recognition features (MoRFs) are short binding regions located in longer intrinsically disordered protein regions. Although these short regions lack a stable structure in the natural state, they readily undergo disorder-to-order transitions upon binding to their partner molecules. MoRFs play critical roles in the molecular interaction network of a cell, and are associated with many human genetic diseases. Therefore, identification of MoRFs is an important step in understanding functional aspects of these proteins and in finding applications in drug design.Results: Here, we propose a novel method for identifying MoRFs, named as MFSPSSMpred (Masked, Filtered and Smoothed Position-Specific Scoring Matrix-based Predictor). Firstly, a masking method is used to calculate the average local conservation scores of residues within a masking-window length in the position-specific scoring matrix (PSSM). Then, the scores below the average are filtered out. Finally, a smoothing method is used to incorporate the features of flanking regions for each residue to prepare the feature sets for prediction. Our method employs no predicted results from other classifiers as input, i.e., all features used in this method are extracted from the PSSM of sequence only. Experimental results show that, comparing with other methods tested on the same datasets, our method achieves the best performance: achieving 0.004 similar to 0.079 higher AUC than other methods when tested on TEST419, and achieving 0.045 similar to 0.212 higher AUC than other methods when tested on TEST2012. In addition, when tested on an independent membrane proteins-related dataset, MFSPSSMpred significantly outperformed the existing predictor MoRFpred.Conclusions: This study suggests that: 1) amino acid composition and physicochemical properties in the flanking regions of MoRFs are very different from those in the general non-MoRF regions; 2) MoRFs contain both highly conserved residues and highly variable residues and, on the whole, are highly locally conserved; and 3) combining contextual information with local conservation information of residues facilitates the prediction of MoRFs.

Recently, there have been numerous studies that rely on the number of search results, i.e., hit count. However, hit counts returned by search engines can vary unnaturally when observed on different days, and may contain large errors that affect researches that depend on those results. Such errors can result in low precision of machine translation, incorrect extraction of synonyms and other problems. Thus, it is indispensable to evaluate and to improve the reliability of hit counts. There exist several researches to show the phenomenon
however, none of previous researches have made clear how much we can trust them. In this paper, we propose hit counts' reliability metrics to quantitatively evaluate hit counts' reliability to improve hit count selection. The evaluation results with Google show that our metrics successfully adopt reliable hit counts - 99.8% precision, and skip to adopt unreliable hit counts - 74.3% precision. © 2012 Springer-Verlag Berlin Heidelberg.

Nowadays, web search engines have features to blend other vertical search results into web search results. It is called aggregated search. Here, vertical search includes news, blog, image, video, real time information search such as twitter, and so on. Web search engines do not always blend these vertical search results. Instead, they decide when they should blend vertical search results, and which vertical search results should be blended depending on input queries. In this paper, we survey the techniques and evaluation schemes to blend vertical search results into web search results. Afte...

We investigate temporal factors in assessing the authoritativeness of web pages. We present three different metrics related to time: age, event, and trend. These metrics measure recentness, special event occurrence, and trend in revisions, respectively. An experimental dataset is created by crawling selected web pages for a period of several months. This data is used to compare page rankings by human users with rankings computed by the standard PageRank algorithm (which does not include temporal factors) and three algorithms that incorporate temporal factors, including the Time-Weighted PageRank (TWPR) algorithm introduced here. Analysis of the rankings shows that all three temporal-aware algorithms produce rankings more like those of human users than does the PageRank algorithm. Of these, the TWPR algorithm produces rankings most similar to human users', indicating that all three temporal factors are relevant in page ranking. In addition, analysis of parameter values used to weight the three temporal factors reveals that age factor has the most impact on page rankings, while trend and event factors have the second and the least impact. Proper weighting of the three factors in TWPR algorithm provides the best ranking results.

既存データベースを利用してミドルウェアでデータベース複製を行う手法において,トランザクション中の更新ごとに複製を行う同期複製手法は,データベースの一貫性を損なうことなく,照会中心のアプリケーションの性能を向上することが可能である.しかし,従来手法は,レプリカをまたがったデッドロックを検出できない,繰返し可能読取りの分離性を提供できない問題がある.本論文では,排他制御をミドルウェア内で行うことで,繰返し可能読取りの分離性を保障し,かつ,デッドロックを検出可能とする同期複製ミドルウェア,Yamaを提案する.Yamaの排他制御は,SQL記述の解析とレプリカへの直接問合せで,SQLを処理する際に必要となるロック対象を特定し,Yama内の排他制御機構よりロックを獲得する.また,各レプリカに非コミット読込み分離性の処理を要求することで,レプリカ内部の排他制御で処理が停滞することを防ぐ.我々は,本手法をTPC-Wに適用したところ,従来手法に比べ,高いスループットを示すことが分かった.

In recent years, digital notebooks have been replacing traditional paper-based notebooks with the development of handwriting input devices. Currently, we can access digital notebooks in various devices, including mobile devices. When we use such mobile devices, however, their limited screen size results in difficulty in understanding the summary of hand-written documents, without the use of a zoom feature. In this paper, we therefore propose the "Legible Thumbnail" that helps us to understand the summary without zooming. Our method detects the important words based on emphasis, such as an underline, and the method outputs the emphasized words to the thumbnail. Experiments show our thumbnail reduces search time by 21%. © 2011 Authors.

The widespread of word of mouth using retweets on Twitter has enabled us to estimate trends in the real world. Previous research methods estimate the value of a tweeted content by calculating the number of subscribers who receive the tweet. However, we should consider the numbers of followers for both the tweeter and retweeter(s) as a greater number of followers may result in more retweets, which we call "bias." In this paper, we propose a bias-free evaluation method for tweeted contents. Experiments show that our method is successful at evaluating tweets without biases. Copyright © 2011, Association for the Advancement of Artificial Intelligence. All rights reserved.

データベースの幅広い普及により,更新トランザクションを多用するアプリケーションが増えている.更新トランザクションは,高価な高可用サーバで処理する必要があるため,スケールアップが求められる.そのためには,複数のトランザクションを一つのトランザクションとして処理するグループコミットが有効である.しかし,グループコミットを利用するには,アプリケーションの修正が必要で,既存のアプリケーションに適用することができなかった.本論文では,トランザクション処理内容の事前知識や,アプリケーションの修正を必要とせず,ミドルウェア内でグループコミットを行う手法を提案する.アプリケーションの修正を行わない場合,グループコミットの対象とするトランザクション集を特定し,バッチ更新をスケジュールする必要がある.本手法では,トランザクションの実行履歴をもとに,トランザクション中のSQLを事前に予測し,グループコミット対象,バッチ更新のスケジュールを行う.本手法をJavaで実装し,5クライアントの環境で評価したところ,データベースのCPU利用率を抑えながら,従来の約2倍のスループットを実現可能であることが分かった.

In this paper, we propose a non-blocking buffer management scheme based on a lock-free variant of the GCLOCK page replacement algorithm. Concurrent access to the buffer management module is a major factor that prevents database scalability to processors. Therefore, we propose a non-blocking scheme for bufferfix operations that fix buffer frames for requested pages without locks by combining Nb-GCLOCK and a non-blocking hash table. Our experimental results revealed that our scheme can obtain nearly linear scalability to processors up to 64 processors, although the existing locking-based schemes do not scale beyond 16 processors.

In this paper, we investigate the trustworthiness of search engines' hit counts, numbers returned as search result counts. Since many studies adopt search engines' hit counts to estimate the popularity of input queries, the reliability of hit counts is indispensable for archiving trustworthy studies. However, hit counts are unreliable because they change, when a user clicks the "Search" button more than once or clicks the "Next" button on the search results page, or when a user queries the same term on separate days. In this paper, we analyze the characteristics of hit count transition by gathering various types of hit counts over two months by using 10,000 queries. The results of our study show that the hit counts with the largest search offset just before search engines adjust their hit counts are the most reliable. Moreover, hit counts are the most reliable when they are consistent over approximately a week.

In this paper, we propose a lock-free variant of the GCLOCK page replacement algorithm, named Nb-GCLOCK. Concurrent access to the buffer management module is a major factor that prevents database scalability to processors. Therefore, we propose a non-blocking scheme for bufferfix operations that fix buffer frames for requested pages without locks by combining Nb-GCLOCK and a wait-free hash table. Our experimental results revealed that our scheme can obtain nearly linear scalability to processors up to 64 processors, although the existing locking-based schemes do not scale beyond 16 processors.

Webページ数は,2006年11月時点で537億ページと推測されている.我々は,2004年1月〜2006年7月の間に,全世界の5,548万台のWebサーバからテキストのみを対象に収集を行い,ユニークなWebページ数として約144.5億ページを収集した.また,収集済みWebページに対して,トップレベルドメイン分布,記述言語分布,Webサーバの地理的位置の解析,バックリンク解析やPageRank計算を進め,Web空間の現状分析を行った.さらに,Webページの解析がビジネスに利用可能であることを示すために,企業のWebサイト上の活動を可視化するe企業調査プロトタイプを構築し,企業の特徴,戦略,評判などの抽出を行った.

The estimated number of static web pages in Oct 2005 was over 20.3 billion, which was determined by multiplying the average number of pages per web server based on the results of three previous studies, 200 pages, by the estimated number of web servers on the Internet, 101.4 million. However, based on the analysis of 8.5 billion web pages that we crawled by Oct. 2005, we estimate the total number of web pages to be 53.7 billion. This is because the number of dynamic web pages has increased rapidly in recent years. We also analyzed the web structure using 3 billion of the 8.5 billion web pages that we have crawled. Our results indicate that the size of the "CORE," the central component of the bow tie structure, has increased in recent years, especially in the Chinese and Japanese web.

The purpose of this study is to show the effectiveness of shell script execution on multi-core and/or SMT (Simultaneous Multi-Threading) processors. recently, multi-core processor and SMT technique have become popular even at home and in business. However, using programs or compilers without consideration of parallelism does not give us the benefits of multi-core and multi-thread. Programmers have to do parallel programming to receive the benefits. Therefore, automatic parallelizing technique has been studied actively. This paper proposes automatic parallelizing scheme for shell script prog...

In this paper, we propose a new system extracting potentially copyright infringement texts from the Web, called EPCI. EPCI extracts them in the following way: (1) generating a set of queries based on a given copyright reserved seed-text, (2) putting every query to search engine API, (3) gathering the search result Web pages from high ranking until the similarity between the given seed-text and the search result pages becomes less than a given threshold value, and (4) merging all the gathered pages, then re-ranking them in the order of their similarity. Our experimental result using 40 seed-texts shows that EPCI is able to extract 132 potentially copyright infringement Web pages per a given copyright reserved seed-text with 94% precision in average.

Background: Multiple sequence alignment (MSA) is a useful tool in bioinformatics. Although many MSA algorithms have been developed, there is still room for improvement in accuracy and speed. In the alignment of a family of protein sequences, global MSA algorithms perform better than local ones in many cases, while local ones perform better than global ones when some sequences have long insertions or deletions (indels) relative to others. Many recent leading MSA algorithms have incorporated pairwise alignment information obtained from a mixture of sources into their scoring system to improve accuracy of alignment containing long indels.Results: We propose a novel group-to-group sequence alignment algorithm that uses a piecewise linear gap cost. We developed a program called PRIME, which employs our proposed algorithm to optimize the well-defined sum-of-pairs score. PRIME stands for Profile-based Randomized Iteration MEthod. We evaluated PRIME and some recent MSA programs using BAliBASE version 3.0 and PREFAB version 4.0 benchmarks. The results of benchmark tests showed that PRIME can construct accurate alignments comparable to the most accurate programs currently available, including L-INS-i of MAFFT, ProbCons, and T-Coffee.Conclusion: PRIME enables users to construct accurate alignments without having to employ pairwise alignment information. PRIME is available at http://prime.cbrc.jp/.

Conventional frequent itemset mining algorithms require some user-specified minimum support, and then mine frequent itemsets with support values that are higher than the minimum support. As it is difficult to predict how many frequent itemsets will be mined with a specified minimum support, the Top-κ mining concept has been proposed. The Top-κ Mining concept is based on an algorithm for mining frequent itemsets without a minimum support, but with the number of most κ frequent itemsets ordered according to their support values. However, the Top-κ mining concept still requires a threshold κ. ...

The branch prediction is installed on the recent processor to avoid stalling pipeline. Branch prediction is a kind of speculative execution for control dependence. In the recent year, the deeper pipeline gets, the higher branch miss prediction penalty reaches. Thus, branch miss prediction rate must lower to rise processor performance. The branch prediction predicts a branch direction and a branch target address. BTB (Branch Target Buffer) registers Taken branch. We found that the most branches, which do not have BTB entry are NotTaken branches. We propose the branch predictor reffering a BT...

Search engines are indispensable for using the Internet, today. However, their architecture is somewhat unknown. In this paper, the architecture of search engines is described by way of Google as an example, focusing on Web crawlers, the indexing and the searching scheme. Moreover, the problems to manage many queries and the cost of running the search engines is taken up.

総務省の調査によれば,日本における家庭へのインターネット普及率は,2002年末に全世帯の8割を超えた.全世帯へのインターネット普及率が10%を超えたのは1998年末であり,普及率10%までの所要年数は5年である.この所要年数をパソコンの13年,自動車・携帯電話の15年等に比較すると,いかに急ピッチで普及してきたかが分かる.本稿では,インターネットと家庭との関係に焦点を当て,具体的データに基づいて,家庭からのインターネットアクセスの過去・現在・未来を紹介する.

In this paper, the design of the intermediate code interpreter, which executes a sequential program in parallel using speculative method, is discussed. Software techniques which enable an efficient parallel speculative execution without hardware support, such as the check point execution mechanism with which an appropriate parallel execution granularity is established, and the efficient implementation of the speculative memory operations which minimize the overhead of searching, recording and the mutual exclusion, are proposed. Experiment results to see the basic performance of these techni...

In this paper, we discuss efficient parallel execution of a dense-matrix problem considering trade-offs between fine-grain and coarse-grain communication in distributed memory machines. The solution of the triangular system of equations involves data dependencies between consecutive iterations in the outer-loop. The dependencies can be naturally solved and processed in parallel by wavefront computation. Two ways of parallelizing are presented; the element-wise fine-grain approach and the coarse-grain approach. We implemented these algorithms on both EM-X and AP 1000+. Fine-grain support mec...

Abstract This paper presents the experiments of col-lecting the documents on the WWW using distributed WWW robots. We propose distributed WWW robots to collect the documents quickly. Our final goal is to col-lect all of the documents on the WWW in Japan within one day. Currently, eight distributed WWW Robots are running in Japan. The experimental results show that we are able to gain 5.8 to 9.7 times speedup when four distributed WWW robots are placed at different places in comparison with when only one WWW robot is used. 1

Overlapping computation with communication is central to obtaining high performance on distributed-memory multiprocessors. Identifying the capability of overlapping, machine architects and programmers will be able to provide tools which can effectively utilize the underlying architecture. This report explicates the overlapping capability of two distributed-memory multiprocessors: the laboratory prototype EM-X multithreaded multiprocessor and a commercially available IBM SP2 with wide nodes. The well-known bitonic sorting algorithm is selected for experiments. Various message sizes are used to determine when, where, how much and why overlapping takes place. Experimental results indicate that both multiprocessors would yield up to 30% to 40% overlap of communication time when the message size is approximately 1K integers. EM-X is found message-size insensitive yielding high overlap for various message sizes while SP2 was effective for a window of message size of 512 to 2K integers, depen...

The purpose of this paper is to propose a new fast control scheme of macrotasks with speculation. A macrotask is a coarse grain task which is a unit of speculation. Previous works have reported that the speedup ratio is 12 to 630 times in comparison with conventional execution schems without speculation when both the speculation depth and the computational resource are infinite, that is called oracle model. The control overhead,however, prevents the speedup from attaining the theoretical speedup ratio. Thus, the control scheme with small overhead is desired. The distributed control scheme archieves small control overhead by adopting two mechanisms-1) Each macrotask creates its successive macrotasks and 2) Each macrotask snoops the broadcasted control signals and determines its next state by itself. Thus, the control of macrotasks can be parallelized and the overhead to control macrotasks does not depend on the number of macrotasks. The scheme has been implemented on the EM-4 multiprocessor. Preliminary evaluations using Boolean Recurrence loops show that the control overhead of the proposed scheme is smaller than that of conventional control schemes-centralized control schemes.

近年の分散共有メモリ型並列計算機は,プロセッサの処理と独立に非同期でデータ転送を行う機構を備え,プロセッサがデータ転送に忙殺されるのを防いでいる.また,プロセッサの高速化と64bitアーキテクチャ化により,演算性能は向上したが,コストパフォーマンスの関係からネットワークの転送性能は,プロセッサの演算性能より低く設定される場合が多い.本論文では,このような分散共有メモリ型並列計算機において,1重Doacross型ループの実行時間算出法を提案する.実行時間算出にあたっては,ネットワークの転送性能として,プロセッサとネットワーク間のデータ入出力時間間隔であるデータ転送ピッチを新たに導入すると共に,データ転送余裕時間およびデータ転送発行遅延時間を定義し,ループ実行時間を求める.また,求められたループ実行時間の利用例としてデータ転送ピッチを考慮した場合,データ転送順序の変更によって実行時間を小さくすることができることを示す.T3Dを対象としたシミュレーションの結果,従来法に比較して,より実測値に近い実行時間を算出できることを確認した.

Multithreading is known be effective for tolerating communication latency in distributed-memory multiprocessors. Two types of support for multithreading have been used to date including software and hardware. This paper presents the impact of multithreading on performance through empirical studies. In particular, we explicate the performance difference between software support and hardware support for the 80-processor EM-X distributed-memory multiprocessor which we have designed and implemented. The EMX provides three types of hardware supports for fine-grain multithreading including direct remote memory access, fast thread invocation, and dedicated instructions for generating fixed-sized communication packets. To demonstrate the effect of multithreading, we have performed various experiments using micro benchmark programs and MP3D, one of the SPLASH benchmarks. Three types of performance parameters have been measured including processor efficiency, remote memory latency, and network load. Experimental results indicate that the EM-X architecture is highly effective for supporting the multithreading principles of execution through dedicated hardware and software. keywords Multithreading, latency hiding, fine grain communication, direct remote memory access, shared memory benchmark, synthetic workload. 1

本論文では,並列処理システム上ではFORTRANプログラムを高速に実行する方式として,多段の条件分岐に渡る先行評価を用いたプログラムの並列化と実行方式を提案する.従来,条件分岐を含むプログラムを並列化する手法がいくつか提案されている.先行評価を用いない手法としては,(1)タスクの最早実行条件求出法があり,先行評価を用いる手法としては,(2)スーパスカラプロセッサやVLIW計算機を対象とした条件分岐1段に限った先行評価方式,および,(3)特定のループを対象とした多段の先行評価方式,が提案されている.しかし,(1)最早実行条件を求めるのみでは十分な並列性が得られない.(2)1段の条件分岐の先行評価で得られる速度向上はたかだか2倍である,(3)適用対象が特定ループに限られる,という問題をもつ.これらの問題に対して,本論文では,プログラムをマクロタスクに分割し,マクロタスク間の多段の先行評価方式を一般的な並列処理システム上で定義する.そして,各々のマクロタスクについと,実行開始条件・制御確定条件・実行停止条件を用いたマクロタスクの実行制御手法を提案する.

In this paper, we propose an efficient techniques, called CD translation, to compile a FORTRAN program to a optimized dataflow code. The CD translation generates the dataflow control information from a control flow graph by using the data flow analysis with the branch node operation, and enables to analyze a sequential program with any type of the control structures (e.g. goto statement and irreducible loop) correctly, while the previous method cannot compile a FORTRAN to the dataflow program perfectly. This analysis technique is much worthy of not only the construction of the compiler for dataflow machines but also the analysis technique for the parallelizing compiler because the dataflow program represents all the program dependencies with only data dependencies unifyingly and enables to analyze all the program dependencies identically. Moreover the FORTRAN compiler implementing the CD translation is introduced.

This paper proposes a parallel processing system - Harray-for scientific computations. Data flow computers are expected to obtain the high performance because they can extract parallelism fully from a program. However, they have many problems, such as the difficulty of controlling the sequence of execution. The - Harray - system is an array processor which adapts two levels of control mechanism
data flow execution in each processor and control flow between processors, in order to take full advantage of both mechanisms. A task which is assigned to a processor is called a "macro-block". Three types of macro-blocking and three types of activation schemes for the macro-block which initiates its execution are introduced in order to attain the high performance. Moreover, a hardware synchronization mechanism is used to reduce synchronization overhead and to gain the liner speedup of the - Harray - system. In this paper, the system architecture of the - Harray - system and its performance evaluation by software simulation are presented.

Native Language Identification, the task of identifying the native language (L1) of a writer based solely on a sample of his/her writing in non-native language (L2), is one of the authorship attribution problem. In this paper, we propose i) "upper phrase information" as a new feature, ii) discarding essay data which seem to be outliers from the training dataset. NLI is able to applicable to many other NLP tasks such as Second Language Acquisition. From 2005, many researchers have approached this task in different ways. Combining all the proposed techniques and existing methods, our system archives 85.6% accuracy on the NLI Shared Task 2014 data. To the best of our knowledge, this is a state-of-the-art accuracy in the NLI tasks.

漢字や英単語を記憶する暗記学習は，忘却せずに再生可能となるよう記憶を定着させることが目標であり，より効率的に記憶を定着可能な学習システムは学習者にとって有用である．記憶を定着させるためには，暗記する対象を再学習する反復学習を繰り返す必要があると言われており，効率的に暗記を行うためには定着していない記憶を選び出して優先的に反復学習を行うことが必要である．しかし，学習者の正解・不正解のテスト結果だけでは，正解しているがすぐに忘れてしまう定着度の低い暗記対象が検出できないため，未定着記憶を網羅することができない．また定着・未定着の 2 値判定にとどまり，反復学習の優先順位を決めることができない．そこで本研究では，タブレット端末等から取得可能な時系列情報や筆圧が含まれるオンライン手書き情報を用いて，学習者の記憶定着度を推定する手法を提案する．提案システムによって得られる連続値である 「記憶度」 の数値が低い事象を優先的に学習することで，効率的に暗記可能な学習支援システムの構築が実現可能となる．

従来,著者推定研究は小説に対する著者推定を中心に研究が行われており,推定対象を限定した,少人数に対する著者候補者群が取り扱われてきた.これに対し,我々はマイクロブログを対象にした,不特定多数の候補者群に対する著者推定の提案を行った.その際,精度向上のためマイクロブログ特有の叫喚フレーズに対する正規化手法,および計算量削減のため推定に必要となるメッセージ数を削減する手法を提案してきた.本稿では,より多くのマイクロブログ利用者を対象にした著者推定を行う上での問題点,特に学習用データとテストデータの取得期間の差異が精度に与える影響について検証し,学習用データの取得期間が精度に与える影響を小さくする手法を提案する.実験ではTwitterユーザ10,000人に対して著者推定を行い,Precision@1で0.535,MRRで0.602を達成した.

Twitterのような大規模なソーシャルサービスにおいて,ユーザの興味や所属などのプロフィールを知ることは,効果的なマーケティングを行う上で重要である.このような背景から,Twitterにおけるプロフィール推定に関する研究が行われてきた.従来のプロフィール推定手法では,フォロー情報によって構築されるソーシャルグラフからコミュニティを抽出し,対象のユーザが属するコミュニティの属性を推定することでプロフィール推定を行なっている.しかし,各々のフォローの目的や,活発な交流があるかという点を考慮することができないため,実際に親密な関係を持つユーザ群をコミュニティとして抽出することが困難であるという問題が存在する.それに対して奥谷らは,フォローに代えてメンション情報を用いてソーシャルグラフを構築することで,これらの問題を解決する手法を提案している.しかし同手法には,プロフィール推定の対象となるユーザの周辺ユーザのプロフィールに幅広く共通して出現する単語が,プロフィールとして出力されにくいという問題がある.そこで本論文では,奥谷らのプロフィール推定手法における単語の重要度の算出方法を変更し,Twitterユーザ全体からランダムにサンプリングした100,000ユーザのデータを利用して一般語をフィルタリングすることで,この問題を解決する手法を提案する.6人の被験者による実験の結果,奥谷らの手法と比較して,Precision@10が0.37から0.78,MRRが1.44から2.61に向上した.

Twitter, as one of the most popular social network services, draws the attention of more and more researchers worldwide. With a large amount of information tweeted every day, it turns essential to identify the influential users we are interested in. In the previous research, researchers mainly identify topics from tweets and rank users by utilizing the follow relationship; however, the following relationship is strongly related to their reputation in real world and cannot describe their influence and activity level in Twitter exactly. Instead, in this paper, to identify topics and influential users, we use "Twitter List," whose name represents the topic of listed members. By analyzing Twitter List, we are able to detect topics and identify influential users in the corresponding topic more efficiently. Based on our experimental evaluation using the selected two topics, the influential users identified by our proposed method have the average influence score related to the topic made by interviewees of 3.7 and 3.33 outweigh the methods of ranking by follower numbers with the average score of 3.22 and 3.27 respectively.

Twitter, as one of the most popular social network services, is widely used to query public opinions. In this research, a large corpus of Twitter data, along with online reviews, are used to apply sentimental and culture-based analysis, so as to figure out the cultural effects on user evaluations. Posts written in more than 30 languages from more than 30 countries are collected. In order to implement the cross-domain investigations, global restaurants and world attractions are taken as the research subjects, and a series of classifiers with high performances are trained and applied in the experiment steps. Then various analyzing methods are applied to obtain informative results and conclusions about the user evaluations for the targets. As the contributions, this research validates the capability and field transferability of the proposed methods for cross-lingual sentiment analysis, and arrives at the conclusions that the cultural effects on user evaluations for both restaurant domain and travel domain actually exist, and are obvious for some countries and cultural backgrounds.

研究者は,研究意義や既存手法を知るために,自らの研究分野に関連する論文の調査を行う.論文の調査に広く用いられる論文検索システムは,ユーザがキーワードをクエリとして与えるキーワード検索が一般的である.専門用語の多い技術分野などでは,特に研究分野にまだ精通していない研究者が,適切なキーワードを与えて検索を行い,満足な結果を得ることは難しい.この問題を解決するため,我々は論文の概要を入力とする関連論文検索システムを提案した.同システムでは,入力の概要に含まれる単語が持つ意味を意味概念行列として表現し考慮することで,検索に用いるクエリの自動生成を行っている.本稿では,我々が以前提案したシステムの拡張を行う.具体的には,1)日本語論文検索への対応,および2)RSMによる論文クラスタリングを用いてより質の高いキーワード生成を実現する.日本語に対応している既存の論文検索システムとの比較により,p@10を平均で0.17向上させることに成功した.

Twitter, as one of the most popular social network services, draws the attention of more and more researchers worldwide. With a large amount of information tweeted every day, it turns essential to identify the influential users we are interested in. In the previous research, researchers mainly identify topics from tweets and rank users by utilizing the follow relationship; however, the following relationship is strongly related to their reputation in real world and cannot describe their influence and activity level in Twitter exactly. Instead, in this paper, to identify topics and influential users, we use "Twitter List," whose name represents the topic of listed members. By analyzing Twitter List, we are able to detect topics and identify influential users in the corresponding topic more efficiently. Based on our experimental evaluation using the selected two topics, the influential users identified by our proposed method have the average influence score related to the topic made by interviewees of 3.7 and 3.33 outweigh the methods of ranking by follower numbers with the average score of 3.22 and 3.27 respectively.

従来，著者推定研究は小説に対する著者推定を中心に研究が行われており，推定対象を限定した，少人数に対する著者候補者群が取り扱われてきた．これに対し，我々はマイクロブログを対象にした，不特定多数の候補者群に対する著者推定の提案を行った．その際，精度向上のためマイクロブログ特有の叫喚フレーズに対する正規化手法，および計算量削減のため推定に必要となるメッセージ数を削減する手法を提案してきた．本稿では，より多くのマイクロブログ利用者を対象にした著者推定を行う上での問題点，特に学習用データとテストデータの取得期間の差異が精度に与える影響について検証し，学習用データの取得期間が精度に与える影響を小さくする手法を提案する．実験では Twitter ユーザ 10,000 人に対して著者推定を行い，Precision@1 で 0.535，MRR で 0.602 を達成した．

Twitter のような大規模なソーシャルサービスにおいて，ユーザの興味や所属などのプロフィールを知ることは，効果的なマーケティングを行う上で重要である．このような背景から，Twitter におけるプロフィール推定に関する研究が行われてきた．従来のプロフィール推定手法では，フォロー情報によって構築されるソーシャルグラフからコミュニティを抽出し，対象のユーザが属するコミュニティの属性を推定することでプロフィール推定を行なっている．しかし，各々のフォローの目的や，活発な交流があるかという点を考慮することができないため，実際に親密な関係を持つユーザ群をコミュニティとして抽出することが困難であるという問題が存在する．それに対して奥谷らは，フォローに代えてメンション情報を用いてソーシャルグラフを構築することで，これらの問題を解決する手法を提案している．しかし同手法には，プロフィール推定の対象となるユーザの周辺ユーザのプロフィールに幅広く共通して出現する単語が，プロフィールとして出力されにくいという問題がある．そこで本論文では，奥谷らのプロフィール推定手法における単語の重要度の算出方法を変更し，Twitter ユーザ全体からランダムにサンプリングした 100,000 ユーザのデータを利用して一般語をフィルタリングすることで，この問題を解決する手法を提案する．6 人の被験者による実験の結果，奥谷らの手法と比較して，Precision@10 が 0.37 から 0.78，MRR が 1.44 から 2.61 に向上した．

Twitter のような大規模なソーシャルサービスにおいて，ユーザの興味や所属などのプロフィールを知ることは，効果的なマーケティングを行う上で重要である．このような背景から，Twitter におけるプロフィール推定に関する研究が行われてきた．従来のプロフィール推定手法では，フォロー情報によって構築されるソーシャルグラフからコミュニティを抽出し，対象のユーザが属するコミュニティの属性を推定することでプロフィール推定を行なっている．しかし，各々のフォローの目的や，活発な交流があるかという点を考慮することができないため，実際に親密な関係を持つユーザ群をコミュニティとして抽出することが困難であるという問題が存在する．それに対して奥谷らは，フォローに代えてメンション情報を用いてソーシャルグラフを構築することで，これらの問題を解決する手法を提案している．しかし同手法には，プロフィール推定の対象となるユーザの周辺ユーザのプロフィールに幅広く共通して出現する単語が，プロフィールとして出力されにくいという問題がある．そこで本論文では，奥谷らのプロフィール推定手法における単語の重要度の算出方法を変更し，Twitter ユーザ全体からランダムにサンプリングした 100,000 ユーザのデータを利用して一般語をフィルタリングすることで，この問題を解決する手法を提案する．6 人の被験者による実験の結果，奥谷らの手法と比較して，Precision@10 が 0.37 から 0.78，MRR が 1.44 から 2.61 に向上した．

Twitter, as one of the most popular social network services, draws the attention of more and more researchers worldwide. With a large amount of information tweeted every day, it turns essential to identify the influential users we are interested in. In the previous research, researchers mainly identify topics from tweets and rank users by utilizing the follow relationship; however, the following relationship is strongly related to their reputation in real world and cannot describe their influence and activity level in Twitter exactly. Instead, in this paper, to identify topics and influential users, we use "Twitter List," whose name represents the topic of listed members. By analyzing Twitter List, we are able to detect topics and identify influential users in the corresponding topic more efficiently. Based on our experimental evaluation using the selected two topics, the influential users identified by our proposed method have the average influence score related to the topic made by interviewees of 3.7 and 3.33 outweigh the methods of ranking by follower numbers with the average score of 3.22 and 3.27 respectively.

Twitter のユーザ数が増加を続ける一方で，不正に ID 及びパスワードを入手され，他人によってツイートを投稿される被害が増加している．これに対し，我々はアカウント乗っ取りによって投稿されるメッセージの一部であるスパムツイートの検出手法を提案し，8 割程度の正答率を得ている．同手法では特定の単語が含まれているスパムツイートを検出対象とし，検出の有効性を示している．本研究では同検出対象を広げ，アカウントの所持者以外が投稿したツイート全体を 「乗っ取りツイート」 として定義し，これを検出する手法を提案する．また本研究では，以前提案した手法に対してパラメータの再調整を行うと同時に，頻繁に用いるハッシュタグの種類及びリプライを送る相手が各アカウントにおいて特徴的であることを利用し，F 値の向上を図った．100 アカウントに対して評価実験を行った結果，我々が提案している従来手法と比較し，F 値を 0.1984 向上させ F 値 0.8570 を達成した．

医薬品の服用に伴う副作用の早期発見と対策は,医療現場において重要な課題である.副作用の早期発見と対策のためには,医師や薬剤師が全医薬品の全副作用を把握しておく必要がある.しかし,一つの医薬品に既知の副作用は数多くあり,全ての副作用の把握は困難である.また副作用には同義に解される類似表記が多くあり,同一の副作用にも関わらず表記違いにより異なる副作用として誤認し,副作用の発見が遅れる可能性がある.さらに,医薬品との関連性が立証されていない未知の副作用も想定される.そこで本稿では副作用の表記ゆれに頑健かつ,医薬品の未知の副作用検索に対応した副作用検索システムを提案する.提案手法では,医薬品の添付文書中の副作用や,副作用が疑われる症例報告を元に医薬品の未知の副作用を推定する.実験では,実際に副作用が疑われる症例報告があった事例150件を入力し,副作用の検索結果と,副作用が疑われる症例報告にある,医薬品との関連性が疑われる副作用を比較することにより有用性を評価した.実験の結果,副作用の検出率は72.7%であり,うち42.2%を未知の副作用として検出した.また従来,表記ゆれにより同一の副作用として検出できなかった既知の副作用29.3%を,副作用の表記ゆれを解消して同一の副作用として検出でき,提案手法が有用であることを確認した.

従来，著者推定研究は小説に対する著者推定を中心に研究が行われており，限定された人数の著者候補者群を取り扱ってきた．またこれまでに，インターネットに投稿された文章を対象に 1 万人レベルでの著者推定手法を提案し，8 割程度の精度を得ている．しかし，多数のユーザが存在する，マイクロブログに投稿されるメッセージは，投稿数は多いが一度に投稿される文章量が短く，未知語や誤字脱字が多いという特徴が存在するため，これまでの手法では精度が低下してしまう．そこで，本研究ではメッセージから辞書を作成し，その辞書を用いた形態素解析器を利用することで少数のメッセージを利用した大規模人数に対する著者推定を行う手法を提案する．900 人の候補者から著者を推定する評価実験を行った結果，既存の著者推定手法よりも精度が上昇することが確認できた．

従来,著者推定研究は小説に対する著者推定を中心に研究が行われており,限定された人数の著者候補者群を取り扱ってきた.またこれまでに,インターネットに投稿された文章を対象に 1 万人レベルでの著者推定手法を提案し,8 割程度の精度を得ている.しかし,多数のユーザが存在する,マイクロブログに投稿されるメッセージは,投稿数は多いが一度に投稿される文章量が短く,未知語や誤字脱字が多いという特徴が存在するため,これまでの手法では精度が低下してしまう.そこで,本研究ではメッセージから辞書を作成し,その辞書を用いた形態素解析器を利用することで少数のメッセージを利用した大規模人数に対する著者推定を行う手法を提案する.900 人の候補者から著者を推定する評価実験を行った結果,既存の著者推定手法よりも精度が上昇することが確認できた.

医薬品の服用に伴う副作用の早期発見と対策は，医療現場において重要な課題である．副作用の早期発見と対策のためには，医師や薬剤師が全医薬品の全副作用を把握しておく必要がある．しかし，一つの医薬品に既知の副作用は数多くあり，全ての副作用の把握は困難である．また副作用には同義に解される類似表記が多くあり，同一の副作用にも関わらず表記違いにより異なる副作用として誤認し，副作用の発見が遅れる可能性がある．さらに，医薬品との関連性が立証されていない未知の副作用も想定される．そこで本稿では副作用の表記ゆれに頑健かつ，医薬品の未知の副作用検索に対応した副作用検索システムを提案する．提案手法では，医薬品の添付文書中の副作用や，副作用が疑われる症例報告を元に医薬品の未知の副作用を推定する．実験では，実際に副作用が疑われる症例報告があった事例 150 件を入力し，副作用の検索結果と，副作用が疑われる症例報告にある，医薬品との関連性が疑われる副作用を比較することにより有用性を評価した．実験の結果，副作用の検出率は 72.7% であり，うち 42.2% を未知の副作用として検出した．また従来，表記ゆれにより同一の副作用として検出できなかった既知の副作用 29.3% を，副作用の表記ゆれを解消して同一の副作用として検出でき，提案手法が有用であることを確認した．

従来,著者推定研究は小説に対する著者推定を中心に研究が行われており,限定された人数の著者候補者群を取り扱ってきた.またこれまでに,インターネットに投稿された文章を対象に1万人レベルでの著者推定手法を提案し,8割程度の精度を得ている.しかし,多数のユーザが存在する,マイクロブログに投稿されるメッセージは,投稿数は多いが一度に投稿される文章量が短く,未知語や誤字脱字が多いという特徴が存在するため,これまでの手法では精度が低下してしまう.そこで,本研究ではメッセージから辞書を作成し,その辞書を用いた形態素解析器を利用することで少数のメッセージを利用した大規模人数に対する著者推定を行う手法を提案する.900人の候補者から著者を推定する評価実験を行った結果,既存の著者推定手法よりも精度が上昇することが確認できた.

G-protein-coupled receptors (GPCRs) are involved in the transduction of signals carried by the endogenous ligands into cytosolic regions, which are regarded as important targets to develop new drugs. Accurate prediction of interaction between GPCRs and chemical compounds is keenly required for drug development, because the number of the combinations of GPCR and the compounds is too large to be examined by experiments. Therefore, such computational approaches have been extensively investigated. One of the preceding studies by Okuno et al. had succeeded to achieve high performance in prediction by using the entire amino acid sequence of a GPCR and the chemical feature of a chemical compound. However, the amino acid residues involved in the ligand binding are quite limited. We estimate that the residues could strongly affect the binding. So, we identified the amino acid residues constituting ligand binding region from the 3D structure of GPCR. Then, we examined whether the use of the residues, instead of entire amino acid sequence, can improve the prediction. Support vector machine (SVM) was used for the prediction. Experimental result showed that the accuracy was improved by 3.6%, Fvalue was improved by 0.038% and AUC was improved by 0.002%, comparing to the approach by Okuno et al.

Recently, Twitter has become an efficient tool for product promotion. Thus, both how to measure the influence of individuals and to identify influential Twitter users have great research value. Most of previous researches about influential Twitter users identification have been concentrated on the following and/or friend relationships over user network without taking the factors of real information propagation into account. We believe influential users are those who spread information in the propagation and thus they are key figures in advertising for commercial companies. In this paper, we proposed a new method to identify influential Twitter users in some popular topics in Twitter based on retweet relationship. We use LDA to detect topics and then rank Twitter users in each topic.

In this paper, we propose a novel method, named SCPSSMpred (Smoothed and Condensed PSSM based prediction), which uses a simplified position-specific scoring matrix (PSSM) for predicting ligand-binding sites. Although the simplified PSSM has only ten dimensions, it combines abundant features, such as amino acid arrangement, information of neighboring residues, physicochemical properties, and evolutionary information. Our method employs no predicted results from other classifiers as input, i.e., all features used in this method are extracted from the sequences only. Three ligands (FAD, NAD and ATP) were used to verify the versatility of our method, and three alternative traditional methods were also analyzed for comparison. All the methods were tested at both the residue level and the protein sequence level. Experimental results showed that the SCPSSMpred method achieved the best performance besides reducing 50% of redundant features in PSSM. In addition, it showed a remarkable adaptability in dealing with unbalanced data compared to other methods when tested on the protein sequence level. This study not only demonstrates the importance of reducing redundant features in PSSM, but also identifies sequence-derived hallmarks of ligand-binding sites, such that both the arrangements and physicochemical properties of neighboring residues significantly impact ligand-binding behavior. ©2013 Information Processing Society of Japan.

データストリーム処理のアプリケーションには,アルゴリズム取引やネットワークパケット監視のように,大容量データストリームを低レイテンシで処理することが必要なものがある.マルチコアCPUを用いた並列処理により大容量ストリームの処理が可能であるが,オペレータごとにスレッドを割り当てると,CPUコア間通信やスレッド待機のオーバヘッドによりレイテンシが増大する.逆にスレッド数が少なすぎては並列性を生かせず,処理できるデータ量に限界が生じる.本論文では,CPUアーキテクチャやスレッド待機のオーバヘッドを考慮し,処理レイテンシを短縮するスレッド割当手法を提案する.マルチコア環境におけるデータストリーム処理のレイテンシ定義を与え,モデル上で最適なスレッド割当が求まることを示す.更に,入力ストリームのデータレート変化に応じてオペレータを再配置する際,ストリーム処理を止めずにタプル適用順序を守ってオペレータを再配置する方法を提案する.

Abstract Applications to process a massive amount of data, so-called "big data analysis" , is one of the recent hot requirements, and a machine learning algorithm is highly expected to run much faster in scalable environment in order to fulfill the requirements. A machine learning algorithm often behaves quite differently from a data intensive application, which has been deeply investigated in high performance computing area. Therefore, a clear model of data access patterns, dependency analysis, and parallelism extraction on machine learning algorithms are indespensable so as to run machine learning algorithms faster in parallel and distributed computing environment such as the Cloud. This article reports task graphs generation for well-known machine learning algorithms, and the task graphs equip all the required information for parallel execution of machine learning algorithms.

近年、三次元形状データはさまざまな分野で活用され、多くの三次元データが保存されている。三次元形状データの増加に伴い、三次元形状データの検索へのニーズが高まっている。形状検索は大きく全体形状検索と部分形状検索の二つに分けられる。全体形状検索では、クエリーとして与えた形状データと完全一致する形状データを検索する。一方、部分形状検索では、クエリーとして与えた形状データを含む形状データを検索する。形状検索を実行する多くの場面において、検索したい形状と同一の形状データをクエリーとして持っていることはほとんどなく、クエリーとして用いられるのは多くの場合、部分形状データとなる。そのため、全体形状検索よりも部分形状検索へのニーズの方が高い。一方で、部分形状検索はクエリーと検索したい形状が同一形状でないため形状間の対応付けが難しく、チャレンジンクな課題として知られている。部分形状検索の手法としては、Bag-of-featuresを用いる方法や特徴点のマッチングを用いる方法が知られている。しかし、Bag-of-featuresを用いる方法では、Bag-of-featuresは全体形状データまたは部分形状データを事前にヒストクラム表現するため、事前にヒストグラム表現した形状とクエリーが類似していなければ適用することは難しい。特徴点のマッチングを用いる方法では、特徴点のマッチングの精度が検索の精度に影響する。特に、誤対応した特徴点のマッチングが精度の低下をもたらす。本論文の提案手法は、三点の特徴点からなる三角形を用いることでマッチング精度の向上を実現する。クエリーとして与えた形状データから特徴点を抽出し、三点の特徴点を一組の三角形とする。局所特徴量ベクトルの距離による対応付けに基づき、保存された形状データの特徴点からなる三角形を作成し、その三角形どうしを比較する。三点の特徴点を用いることで局所的な情報だけではなく特徴点間の位置関係も考慮され、三角形の対応関係をチェックすることで誤対応を取り除くことができ、マッチング精度を向上することができる。また、各特徴点の局所特徴量ベクトルをインデックス化し、インデックスと三角形間の対応関係チェックを組み合わせて用いることで、高速な検索を実現する。本論文における、私たちの貢献は以下の2つである。1.三角形特徴を用いることで、精度向上を実現している2.特徴点の局所特徴量ベクトルのインデックス化と三角形間の対応関係チェックを組み合わせることで高速な検索を実現している実験として、形状データ100データをインデックス化したデータベースを作成し、インデックス化したデータから無作為に選んだ20データについて、形状データ全体の30〜50%程度を切り出したデータをクエリーとする部分形状検索を行った。本実験において、特徴点を単独で用いた場合の正解率0.65に対して、提案手法は正解率0.85を示した。また、インデックス化するデータの数を増やして検索速度を測定し、本提案手法がインデックス化されたデータ数に対して頑健に検索できることを示した。

本稿では我々が取り組んでいる多メディアビッグデータの統合的解析による情報抽出の試みについて述べる.ソーシャルメディアの普及によって,様々な情報がリアルタイムにインターネット上にアップロードされるようになった.我々は,単一のソーシャルメディアだけでなく,複数の情報源を組み合わせた, 「多メディアデータ」 を解析することで,より有益な情報を抽出できると考えている.本稿では我々が取り組んでいる多メディア解析について述べる.また,大規模リアルタイムデータの解析をサポートするために開発している,並列分散処理フレームワーク QueueLinker についても述べる.

生徒の学習を支援する際に必要なプロセスとして,つまずきの検知が挙げられる.CAIのつまずき検出に関する研究では,採点結果や解答所要時間,センサーから取得した学習者の顔画像や脈拍などの生体情報,そして入力デバイスであるキーボードやマウスの操作履歴を利用して検知を行う研究が行われてきた.しかし現状の初等教育では筆記活動を中心とした環境であり,こうした環境におけるつまずき検出に関しては深い議論が行われてこなかった.本報告では生徒が利用するペンから得られる筆記情報を元に,つまずきを検出する手法について検討を行う.検出には時系列モデルであるARモデルを用いて学習者の手書き行動が変化する変化点を検出し,変化点間ごとに推定を行う.実施した試験評価において一定の検出性能が確認できた.

近年,タブレット端末や電子ペンに代表される手書き入力可能な端末が普及し始めたことにより,手書きドキュメントの電子化が進みつつある.端末上でのドキュメント探索,閲覧プロセスの過程において各ドキュメントの概要把握を目的とした閲覧時では,元ドキュメントを縮小したサムネイルや,要約テキストを出力するテキストスニペットが一覧表示のスニペットとしてしばし用いられる.しかし,手書きドキュメントに対して従来の単純に縮小したサムネイルを用いると,文字が要約されずに縮小されてしまうため記述内容が読み取れず,概要把握が困難となる問題がある.また,図などの文字以外の情報が含まれ,不完全な文字認識しか行えない手書きドキュメントを要約する研究は,我々の知る限り存在しない.そこで本稿では,下線や囲い込みに代表される筆記者の強調表記を利用して,手書きドキュメントを要約することにより概要の把握が容易となる検索スニペットを提案する.ユーザによる情報検索評価実験の結果,従来と比較して我々の提案するスニペットを利用することで検索速度が平均 42% 削減される結果が得られた.

近年,タブレット端末や電子ペンに代表される手書き入力可能な端末が普及し始めたことにより,手書きドキュメントの電子化が進みつつある.端末上でのドキュメント探索,閲覧プロセスの過程において各ドキュメントの概要把握を目的とした閲覧時では,元ドキュメントを縮小したサムネイルや,要約テキストを出力するテキストスニペットが一覧表示のスニペットとしてしばし用いられる.しかし,手書きドキュメントに対して従来の単純に縮小したサムネイルを用いると,文字が要約されずに縮小されてしまうため記述内容が読み取れず,概要把握が困難となる問題がある.また,図などの文字以外の情報が含まれ,不完全な文字認識しか行えない手書きドキュメントを要約する研究は,我々の知る限り存在しない.そこで本稿では,下線や囲い込みに代表される筆記者の強調表記を利用して,手書きドキュメントを要約することにより概要の把握が容易となる検索スニペットを提案する.ユーザによる情報検索評価実験の結果,従来と比較して我々の提案するスニペットを利用することで検索速度が平均 42% 削減される結果が得られた.

Recording eye-gaze data from many people in natural situations are valuable in Human Factors, Market Strategy and any other studies. The gaze tracking system equipped with webcams is suitable to record eye-gaze data. The resolutions of eye-images captured by webcams are low. Low-resolution eye-images tend to be distorted and cause errors in gaze estimations. We have developed the gaze tracking system with low-resoltion eye-images. In our past study, we extract contours of pupils, remove distorted areas in these contours, approximate pupil contours into an ellipse, and calculate gaze directi...

We propose a pseudo 3D thumbnail generation method to improve the recognizability of visual attention objects by decomposing an original image into visual attention objects and a background. Thumbnails created by scaling, used as general, are not suitable for mobile devices equipped a small display, because attention objects become too small to recognize. Furthermore, previous visual attention-based thumbnail generation methods cannot preserve recognizability of visual attention objects by burying them in the background image. To solve these problems, we propose a pseudo 3D thumbnail genera...

Recording eye-gaze data from many people in natural situations are valuable in Human Factors, Market Strategy and any other studies. The gaze tracking system equipped with webcams is suitable to record eye-gaze data. The resolutions of eye-images captured by webcams are low. Low-resolution eye-images tend to be distorted and cause errors in gaze estimations. We have developed the gaze tracking system with low-resoltion eye-images. In our past study, we extract contours of pupils, remove distorted areas in these contours, approximate pupil contours into an ellipse, and calculate gaze directi...

We propose a pseudo 3D thumbnail generation method to improve the recognizability of visual attention objects by decomposing an original image into visual attention objects and a background. Thumbnails created by scaling, used as general, are not suitable for mobile devices equipped a small display, because attention objects become too small to recognize. Furthermore, previous visual attention-based thumbnail generation methods cannot preserve recognizability of visual attention objects by burying them in the background image. To solve these problems, we propose a pseudo 3D thumbnail genera...

This paper proposes a new thumbnail generation method to improve the recognizability of visual attention objects on small displays. Previous methods such as simple scaling reduce the recognizability of original images because the visual attention objects become too small to recognize. When we view thumbnails on small displays such as those of mobile devices, recognizability is indispensable for handling many images simultaneously. To solve the problem of low recognizability of visual attention objects, we adopt GrabCut to extract visual attention objects from an original image and then divide the original image into visual attention objects and a background image. While the background image is reduced to fit the size of a thumbnail, the extracted visual attention objects are merged into the reduced background image to preserve their recognizability. In adopting GrabCut, we propose a two-stage GrabCut method to automate the extraction of attention objects; the extraction was performed by hand in previous methods. Our experimental results show that our proposed method is able to shorten the search time by 44% and improve the precision of the search by 19% in comparison with simple scaling.

近年,自然言語処理をはじめとする数多くの研究が,検索エンジンから得られる検索結果数,すなわちヒット数を利用している.しかしながら,検索エンジンが返すヒット数は検索するタイミングによって不自然に変化し,研究のベースとして用いるには無視できないほどの大きな誤差が生じることがある.そのため,ヒット数の信頼性を評価,向上させる手法を考えることは,大きな課題である考えられる.我々はこの課題に対して,信頼できるヒット数を得ることができる条件の特定を試みた研究や,実際に得られたヒット数の信頼性を定量的に評価できる手法の提案を行ってきた.本論文では,後者の研究に追加して,信頼性評価指標の妥当性検証実験を行ったので結果を報告する.

Recently, there exit numerous researches based on the number of search results, or hit count. However, hit counts returned by search engines can fluctuate unnaturally when observed on different days, and may cause too large errors to be used in researches. Therefore, it is important to discuss on how we can evaluate and improve the reliability of hit counts. We have performed several researches about this problem such as a research to specify the conditions in which search engines can return reliable hit counts, and a research to define the reliability evaluation metrics. In this paper, in ...

We investigate temporal factors in assessing the authoritativeness of web pages. We present three different metrics related to time: age, event, and trend. These metrics measure recentness, special event occurrence, and trend in revisions, respectively. An experimental dataset is created by crawling selected web pages for a period of several months. This data is used to compare page rankings by human users with rankings computed by the standard PageRank algorithm (which does not include temporal factors) and three algorithms that incorporate temporal factors, including the Time-Weighted PageRank (TWPR) algorithm introduced here. Analysis of the rankings shows that all three temporal-aware algorithms produce rankings more like those of human users than does the PageRank algorithm. Of these, the TWPR algorithm produces rankings most similar to human users', indicating that all three temporal factors are relevant in page ranking. In addition, analysis of parameter values used to weight the three temporal factors reveals that age factor has the most impact on page rankings, while trend and event factors have the second and the least impact. Proper weighting of the three factors in TWPR algorithm provides the best ranking results.

Streaming application, which requires to process data frequently arrives in chronological order, is now a center of interest. This paper proposes a methodology to parallelize, and dynamically allocate streaming applications over distributed environment such as cloud computing environment. The simulation results approved that practical streaming applications need to be processed in parallel in order to avoid loss of data for lack of processing time. However, the methodology proposed in this paper enables all the input data processed with 26% overhead of average execution time of each block o...

A mini blog service, including Twitter, is one of emerging media of note. Across-the-board analysis in posted blogs, and descriptions in related media, such as TV, newspapers, and other media, is indispensable for social analysis. Posts in mini blogs, however, often include names of particular movies, novels, and products, and many of which are compounders. A compounder is often divided into several words by word processors, and difficult to extract as one solid word. Here, if a hot compounder is extracted as it is supposed to be, the quality of morphological analysis is improved to contrib...

In this paper, we improve our previously proposed Resizable-LSH that enhances the range query on approximate similarity search faster. Nowadays, Locality-Sensitive Hashing (LSH) is drawing attention as an effective algorithm for approximate nearest neighbor search. LSH adopts hash functions that collide with high probability if two vectors are close, so that LSH finds approximate nearest neighbors quickly even if the dataset is high-dimensional. However, LSH uses fixed search range on generating hash tables, so resizing the search range costs expensive. As a solution, we've proposed the alg...

TF・IDF method is one of the methods to weight terms in the field of document retrieval. IDF value shows the degree of how a term is difficult to appear in the document set, and depends on the document set to be retrieved. Therefore, the problem is that, even if a term is difficult to appear in the same field of document set as query(which means the term is highly specific in the document), IDF value of term which appears easily in the document set to be retrieved is small. In this paper, we propose and study two step adjustment technique of term weight. In the first step, we get documents r...

The similar object detection from a large quantity of images helps us to be able to organize images by category and research market by using images on the Web. Template matching that can detect similarity object doesn't suit unknown images so that there is an assumption that target image contains same object. In this paper, we are aimed at decreasing false-positive rate due to the premise of template matching. We propose the method that considers the positional relationships of the feature regions with conventional template matching. Each feature region in template image matches target imag...

The gaze estimation without restraining users at home will be contributed to reformation of user interfaces. The commercial gaze estimation systems show high accuracy by using infrared, however, gaze estimation systems with web cameras are highly desired at homes because of their price. The problem using web cams is its low resolution for gaze estimation. Low resolution images are strongly influenced by noises. So the past studies do not estimate detailed direction of eyes. In this paper, we propose a new gaze estimation method which shows high accuracy using image processing and geometrica...

The gaze estimation without restraining users at home will be contributed to reformation of user interfaces. The commercial gaze estimation systems show high accuracy by using infrared, however, gaze estimation systems with web cameras are highly desired at homes because of their price. The problem using web cams is its low resolution for gaze estimation. Low resolution images are strongly influenced by noises. So the past studies do not estimate detailed direction of eyes. In this paper, we propose a new gaze estimation method which shows high accuracy using image processing and geometrica...

In this paper, we investigate the trustworthiness of search engines' hit counts, numbers returned as search result counts. Since many studies adopt search engines' hit counts to estimate the popularity of input queries, the reliability of hit counts is indispensable for archiving trustworthy studies. However, hit counts are unreliable because they change, when a user clicks the "Search" button more than once or clicks the "Next" button on the search results page, or when a user queries the same term on separate days. In this paper, we analyze the characteristics of hit count transition by gathering various types of hit counts over two months by using 10,000 queries. The results of our study show that the hit counts with the largest search offset just before search engines adjust their hit counts are the most reliable. Moreover, hit counts are the most reliable when they are consistent over approximately a week.

Twitter, a microblogging service, is now grabbing attention of people as a new channel. For deep understanding of this new service, this paper reports the characteristics of Twitter users in Japan, and the impact of media such as publications, and TV programs on Twitter community. To the best of our knowledge, this paper is the first to analyze mutual impact between Twitter, and other media quantitatively. In order for the analyses, we crawled user profiles whose language setting is Japanese, and conducted several analysis with well-known methodologies as conventional work did. We confirmed the characteristics of the collected user profiles. We observed the distributions of the number of friends, and the number of follows both follow power-law, and there exists the correlation between the number of friends, and the number of follows. Besides the collected user profiles, we also utilized closed caption data of TV programs in Japan, and other information on media picked up Twitter. We run a batch of matching these data outside Twitter with the collected user profiles, and concluded Twitter has been already widely spread among Japanese people, however, media have still huge impact on the growth of Twitter users. We also conjectured the impact is not one-sided, however, is mutual influence between Twitter, and other media. © 2010 ACM.

In this paper, we propose a lock-free variant of the GCLOCK page replacement algorithm, named Nb-GCLOCK. Concurrent access to the buffer management module is a major factor that prevents database scalability to processors. Therefore, we propose a non-blocking scheme for bufferfix operations that fix buffer frames for requested pages without locks by combining Nb-GCLOCK and a wait-free hash table. Our experimental results revealed that our scheme can obtain nearly linear scalability to processors up to 64 processors, although the existing locking-based schemes do not scale beyond 16 processors.

G-protein coupled receptors (GPCRs) are important pharmacological targets and to predict unknown interactions between GPCRs and ligands is one of the most interesting topics in the current computational biology. However, ligands of many GPCRs are experimentally not identified yet and it is difficult to predict unknown ligands of GPCRs because of insufficiency of training data set. We have developed a 2-way prediction method based on the support vector machine. In this method, the prediction is performed by using both information of ligands and GPCRs and one can apply this method to the case...

インターネット上にウェブページが爆発的に増加し，インターネットから得られる情報が重要になっている．しかし，ウェブページの爆発的な増加につれてスパム行為を行うページも同様に増加し，インターネットから得られる情報の価値を下げている．スパム行為には様々な手法があるが，本論文では自動的に文章を生成するワードサラダに着目し，ワードサラダ型のスパムを効率的に検出する手法を提案する．ワードサラダ型スパムを検出するため，n-gram と離散型共起表現を用いてカルバック・ライブラー情報量に基づく文章のスコアを計算し，計算したスコアに基づき判定を行う．提案手法の評価実験を行った結果，既存手法と比較して F 値で 0.18 の性能の向上を確認できた．Information on the Internet becomes important because of exploding Web page. However, Spam pages also have exploded and information from the Internet have become lower reliability. Though there are many Spamming methods, in this article we focus on "word salad" that creates text automatically, and we propose the effective method of word salad detection. We detect word salad by the score based on Kullback-Leibler divergence calculated with n-gram and interrupted collocation. As a result of experiment, our method improves 0.18 points in F-value from the existing method.

本稿では閾値を可変にした近似的な類似検索手法を提案する．近年，距離を用いた類似検索手法の 1 つとして，Locality-Sensitive Hashing （局所性鋭敏型ハッシング，LSH） による近似的な類似検索が注目されている．LSHは，「距離が近い入力同士は高い確率で衝突する」 特徴を持つハッシュ関数を用いたデータマッピング手法であり，高次元なデータに対しても高速に近傍検索を行うことができる．しかし LSH では，事前計算によって距離が近いデータ同士を同じハッシュ値にマッピングするため，検索時に類似度の閾値を変更することができない．閾値を変更するにはハッシュテーブルの再構築が必要になるため，ユーザが閾値を指定できるような類似検索は実現困難である．そこで本研究では，類似検索時に，クエリとハッシュ値が一致するデータに加え，ハッシュ値が近いデータも取得することで，ハッシュテーブルの再構築を行うことなく，閾値を指定できる類似検索を実現した．提案手法は，閾値に合わせてハッシュテーブルを逐次再構築する LSH と比較して，同程度の精度で，かつ 1,000 倍程度の高速化を達成できることを実験により確認した．We introduce an efficient algorithm named "Resizable-LSH" for approximate similarity search, which enables resizing the search range flexibly. Nowadays, Locality-Sensitive Hashing (LSH) is drawing attention as an efficient algorithm for approximate nearest neighbor search. LSH adopts hash functions that collide with high probability if two vectors are close, so that LSH finds approximate nearest neighbors quickly even if the dataset is high-dimensional. However, LSH should generate hash tables preliminarily, that results in resizing the search range costs expensive because hash table regeneration is required whenever we face the needs to resize search range. To solve the problem, our proposed Resizable-LSH retrieves not only the same hash value of query, but also near hash values. Then Resizable-LSH achieves resizable range-search. As it turns out, the result of the experiments shows Resizable-LSH works about 1,000 times faster than LSH with almost the same quality in comparison with LSH.

本稿では閾値を可変にした近似的な類似検索手法を提案する．近年，距離を用いた類似検索手法の 1 つとして，Locality-Sensitive Hashing （局所性鋭敏型ハッシング，LSH） による近似的な類似検索が注目されている．LSHは，「距離が近い入力同士は高い確率で衝突する」 特徴を持つハッシュ関数を用いたデータマッピング手法であり，高次元なデータに対しても高速に近傍検索を行うことができる．しかし LSH では，事前計算によって距離が近いデータ同士を同じハッシュ値にマッピングするため，検索時に類似度の閾値を変更することができない．閾値を変更するにはハッシュテーブルの再構築が必要になるため，ユーザが閾値を指定できるような類似検索は実現困難である．そこで本研究では，類似検索時に，クエリとハッシュ値が一致するデータに加え，ハッシュ値が近いデータも取得することで，ハッシュテーブルの再構築を行うことなく，閾値を指定できる類似検索を実現した．提案手法は，閾値に合わせてハッシュテーブルを逐次再構築する LSH と比較して，同程度の精度で，かつ 1,000 倍程度の高速化を達成できることを実験により確認した．We introduce an efficient algorithm named "Resizable-LSH" for approximate similarity search, which enables resizing the search range flexibly. Nowadays, Locality-Sensitive Hashing (LSH) is drawing attention as an efficient algorithm for approximate nearest neighbor search. LSH adopts hash functions that collide with high probability if two vectors are close, so that LSH finds approximate nearest neighbors quickly even if the dataset is high-dimensional. However, LSH should generate hash tables preliminarily, that results in resizing the search range costs expensive because hash table regeneration is required whenever we face the needs to resize search range. To solve the problem, our proposed Resizable-LSH retrieves not only the same hash value of query, but also near hash values. Then Resizable-LSH achieves resizable range-search. As it turns out, the result of the experiments shows Resizable-LSH works about 1,000 times faster than LSH with almost the same quality in comparison with LSH.

インターネット上にウェブページが爆発的に増加し，インターネットから得られる情報が重要になっている．しかし，ウェブページの爆発的な増加につれてスパム行為を行うページも同様に増加し，インターネットから得られる情報の価値を下げている．スパム行為には様々な手法があるが，本論文では自動的に文章を生成するワードサラダに着目し，ワードサラダ型のスパムを効率的に検出する手法を提案する．ワードサラダ型スパムを検出するため，n-gram と離散型共起表現を用いてカルバック・ライブラー情報量に基づく文章のスコアを計算し，計算したスコアに基づき判定を行う．提案手法の評価実験を行った結果，既存手法と比較して F 値で 0.18 の性能の向上を確認できた．Information on the Internet becomes important because of exploding Web page. However, Spam pages also have exploded and information from the Internet have become lower reliability. Though there are many Spamming methods, in this article we focus on "word salad" that creates text automatically, and we propose the effective method of word salad detection. We detect word salad by the score based on Kullback-Leibler divergence calculated with n-gram and interrupted collocation. As a result of experiment, our method improves 0.18 points in F-value from the existing method.

A number of studies have been using Search Engines' hit count. The goal of these studies is to build applications for translation support or natural language processing support. These studies assume that the hit count is reliable. To identify the reliability of Search Engines' hit count, we have challenged to verify. In the past, we verified hit count only using one keyword query. The contribution of this paper is to verify hit count using multi query keyword.

Recently, the ALT algorithm is proposed as a speed-up algorithm to compute shortest paths in general graph structures. The ALT algorithm offers a landmark based heuristic function to estimate distance in A* search Before computing shortest paths, the ALT algorithm computes distances between all nodes and landmarks, and stores them to prepared memory or storage space. However, as the number of landmarks increases, the required prepared space increases linearly. To solve this problem, in this paper, we propose a novel heuristic function for computing shortest paths in general graph structures...

Many-core CPUs require many parallel computation tasks to reach their full potential because CPU cores become idle if they do not have enough computation tasks. How best to utilize a number of cores in many-core CPUs should be examined. In this paper, we propose exploitation of idle cores for improving file access performance. Idle cores are used to extract file access patterns from access logs and the extracted patterns are used to improve file cache efficiency by reordering the LRU (Least Recently Used) list based on the extracted patterns. Data mining techniques are used to extract access patterns to reduce computation overhead. Our method was evaluated by simulation and also implemented on Linux kernel 2.6.26 as a prototype system. In the simulation experiment, our method improved the cache-hit ratio up to 1.09% on DBT-2 (TPC-C) trace logs. Our prototype implementation on Linux improves DBT-2 performance up to 5.24% on a real machine. Copyright 2009 ACM.

The total amount of information to process or analyze is jumping sharply with the quick spread of computers and networks. Our project, «Highly scalable monitoring architecture for information explosion», develops a monitoring system allows observing systems, merging the system logs, and discovering intelligence to share. More concretely, the project builds the total system to maintain, optimize, and protect autonomically. This paper reports the outcomes of the project after first-half of the development period.The rest of the paper is organized as follows. Section 2 describes the concept and details of the monitoring system on a single node, and Section 3 addresses the aggregation of the collected information in distributed environments. Section 4 and Section 5 introduce applications of the monitoring systems. Section 6 summarizes the project and mentions future plans. © 2009 IEEE.

Recently, with wide-spread of distributed systems, distributed monitoring systems are needed to mange such systems. However, since monitoring architecture of distributed system faces a huge amount of log data which come from local computing nodes, information aggregation is fundamental scheme for monitoring distributed system. In this paper, we preset a novel approach for extracting computing node-condition profiles by using sequential pattern mining, which is one of data mining techniques. Extracted computing node condition profiles represent node condition patterns which are occurred in many computing nodes frequently. Thus, extracted profiles enable summarized distributed system conditions to be small sized and easy-understandable information.

One of the most difficult problems in distributed systems is load-balancing. Even if we take care of load-balancing, heavily-loaded nodes often occur while there are still lightly-loaded nodes that have idle memory and idle CPU power. Our idea is to exploit this idle memory and idle CPU power to improve the storage performance of heavily-loaded nodes. Idle memory can be used for caching file data and idle CPU power can be used for extracting file access patterns from file access logs. File access patterns are valuable sources for optimizing a cache strategy. Our project goal is to improve the overall performance of distributed systems by improving storage access performance. This paper gives an overview of this project idea and reports the current status of the project. In addition, we show benchmark results from our prototype cache extension system, which is implemented in Linux Kernel 2.6. The DBT-3 (TPC-H) benchmark results show that our system can increase computer speed by a factor of 6.68.

Multiple sequence alignment (MSA) is a useful tool in bioinformatics. Although many MSA algorithms have been developed, there is still room for improvement in accuracy and speed. We have developed an MSA program PRIME, whose crucial feature is the use of a group-to-group sequence alignment algorithm with a piecewise linear gap cost. We have shown that PRIME is one of the most accurate MSA programs currently available. However, PRIME is slower than other leading MSA programs. To improve computational performance, we newly incorporate anchoring and grouping heuristics into PRIME. An anchoring method is to locate well-conserved regions in a given MSA as anchor points to reduce the region of DP matrix to be examined, while a grouping method detects conserved subfamily alignments specified by phylogenetic tree in a given MSA to reduce the number of iterative refinement steps. The results of BAliBASE 3.0 and PREFAB 4 benchmark tests indicated that these heuristics contributed to reduction in the computational time of PRIME by more than 60% while the average alignment accuracy measures decreased by at most 2%. Additionally, we evaluated the effectiveness of iterative refinement algorithm based on maximal expected accuracy (MEA). Our experiments revealed that when many sequences are aligned, the MEA-based algorithm significantly improves alignment accuracy compared with the standard version of PRIME at the expense of a considerable increase in computation time. © 2008 Information Processing Society of Japan.

Many-core CPU improves parallel performance but also raises problem of storage performance bottleneck. I/O optimization should be taken at operating system level because various applications are executed in parallel on many-core CPU environment and I/O optimization requires cross-cutting knowledge about applications. We propose a new method which uses disk access patterns for improving efficiency of disk cache replacement algorithm. Our method is now implemented at Linux 2.6.26 and extracts access patterns from file access logs of applications. The experimental results show our method impro...

To find information from a large collection of Web-pages, several methods for extracting Web communities are proposed. In the past studies, it succeeds in improving precision score by making a rule whether or not to include a certain Web page into a Web community strictly. However, recall score might worsen because the Web page that should be included in the Web community is not included. In this paper, we propose the Web community extraction method that can improve recall score without decreasing precision score. The method adds Web pages that have many links from/to the Web pages in a sam...

A number of studies have been using Search Engines' hit count. The goal of these studies is to build applications for translation support or natural language processing support. These studies assume that the hit count is reliable. However, none of the studies have been verifide the reliability of Search Engines' hit count. If the hit count is unreliable, studies using hit count become also unreliable. The purpose of this paper is to verify the reliability of Search Engines' hit count. In this experiment, we used Search APIs provided by Google, Yahoo! Japan and Live Search. Furthermore, we r...

Search engines are necessary to find information from the Internet. There is an investigation report that users recognize that information from search engines' results is as believable as information from television. That is, we can understand a part of the influence which a certain site gives to the society by examining search engine rankings. In this paper, to examine the influence of Wikipedia, that has become the pronoun of the encyclopedia in the Internet, we have conducted the experiments. We collected ranking positions of the articles in the Japanese version of Wikipedia by using search engines' APIs. Among all articles in the Japanese version of Wikipedia, about 90% of articles were ranked in top 10 by Yahoo! JAPAN and Google, and about 70% were ranked in top 10 by MSN. In the case of Yahoo! JAPAN and MSN, newly created articles in Wikipedia tend to appear in top 10 ranking at first, and keep their high rankings. The influence of Wikipedia toward search engine rankings was confirmed by our experiments.

近い将来，１つのチップに十数コアを搭載したメニーコア CPU が登場することは確実である．メニーコア環境下では，多くのアプリケーションが並列に動作するため，HDD が特に不得手とするランダムアクセスの頻度が増え，ストレージがますますボトルネックになると考えられる．そこで我々は，ストレージのボトルネックをソフトウェア的に軽減することを考えている．具体的には，アプリケーションのアクセスパターンを活用するディスクキャッシュ機構を Linux に実装し，実システムで評価することをひとつの目標にしている．ワークショップでは，これまでの研究概要と既存研究について述べると共に，最新の研究成果について述べ，今後の研究指針を示す．Many-core CPU which consists of some dozen cores in one package will definitely appear in the near future. In many-core environments, storage system will become bottlenecks since the random access to storage will increase because many applications will run in parallel. To meet this problem, we try to ease the storage bottlenecks by software method. Specifically, we try to implement a novel disk cache technique which exploits file access patterns of applications. The cache technique will be implemented on Linux Kernel and evaluated in real system. In this talk, we will show our research abstract and related works, and then show the latest results and the milestone of our research.

Search engines are necessary to find information from the Internet. There is an investigation report that users recognize that information from search engines' results is as believable as information from television. That is, we can understand a part of the influence which a certain site gives to the society by examining search engine rankings. In this paper, to examine the influence of Wikipedia, that has become the pronoun of the encyclopedia in the Internet, we have conducted the experiments. We collected ranking positions of the articles in the Japanese version of Wikipedia by using search engines' APIs. Among all articles in the Japanese version of Wikipedia, about 90% of articles were ranked in top 10 by Yahoo! JAPAN and Google, and about 70% were ranked in top 10 by MSN. In the case of Yahoo! JAPAN and MSN, newly created articles in Wikipedia tend to appear in top 10 ranking at first, and keep their high rankings. The influence of Wikipedia toward search engine rankings was confirmed by our experiments.

Clustering of internet news articles makes it possible to detect various useful information, for example, related articles, and latest topic words. From the TDT project down, this area is widely researched. Conventional clustering methods have difficulties to detect single article as a single cluster even though many single articles exists. In this paper, we propose a method to cluster news articles that exclude single articles in advance by using proper noun information, topographic information and other characteristics between single and non-single articles. In evaluation, we use half a year Japanese news articles. Compared to the Single-Link Method, which alone is difficult to judge articles single, our proposing method improves precision 10.2% and reduces the computation time to approximately a third.

According to our investigation result in Oct. 2005, the number of Web pages all over the world is estimated 53.7 billion. We have investigated TLD distribution and Language Distribution of Web pages based on 10.7 billion Web page dataset. In this paper, as one of our Web statics investigation series, we analyzed three kinds of distribution based on 10.7 billion Web page dataset, distribution of geographical location of Web server, the number of virtual hosts per one Web server, and the number of back links, i.e. the value of in-degree, per one Web server. Our results show (1) about 95.5% of Web servers are located in North America, Europe, and Asia regions, (2) hosts located in Latain America and East Europe have a large number of virtual hosts, and (3) the distribution between the value of in-degree and the number of Web servers follow the power low.

Free encyclopedia Wikipedia on the Internet contains 490,000 Japanese articles and its volume of information is huge and useful. However, the trustworthiness of the articles' contents becomes uncertain because anyone can edit them easily. In other words, since we cannot understand exactly who edits the contents, it results in difficulty of measuring trustworthiness of the articles' contents. To such a problem the method using the edit history is proposed for measuring the trustworthiness of the articles. However, it is inapposite compared with the article and the editor with a little frequency to be edited. Therefore, in this paper, we propose the method for measuring editors' trustworthiness without depending on the edit frequency. The proposed method is based on the ratio where the edit remains the latest version of contents. Our evaluation shows that our proposed method evaluate the editor with high reliability highly, and the editor with low reliability lowly without depending on the edit frequency.

According to our investigation result in Oct. 2005, the number of Web pages all over the world is estimated 53.7 billion. We have investigated TLD distribution and Language Distribution of Web pages based on 10.7 billion Web page dataset. In this paper, as one of our Web statics investigation series, we analyzed three kinds of distribution based on 10.7 billion Web page dataset, distribution of geographical location of Web server, the number of virtual hosts per one Web server, and the number of back links, i.e. the value of in-degree, per one Web server. Our results show (1) about 95.5% of...

近い将来，１つのチップに十数コアを搭載したメニーコア CPU が登場することは確実である．メニーコア環境下では，多くのアプリケーションが並列に動作するため，HDD が特に不得手とするランダムアクセスの頻度が増え，ストレージがますますボトルネックになると考えられる．そこで我々は，ストレージのボトルネックをソフトウェア的に軽減することを考えている．具体的には，アプリケーションのアクセスパターンを活用するディスクキャッシュ機構を Linux に実装し，実システムで評価することをひとつの目標にしている．ワークショップでは，これまでの研究概要と既存研究について述べると共に，最新の研究成果について述べ，今後の研究指針を示す．Many-core CPU which consists of some dozen cores in one package will definitely appear in the near future. In many-core environments, storage system will become bottlenecks since the random access to storage will increase because many applications will run in parallel. To meet this problem, we try to ease the storage bottlenecks by software method. Specifically, we try to implement a novel disk cache technique which exploits file access patterns of applications. The cache technique will be implemented on Linux Kernel and evaluated in real system. In this talk, we will show our research abstract and related works, and then show the latest results and the milestone of our research.

Clustering of internet news articles makes it possible to detect various useful information, for example, related articles, and latest topic words. From the TDT project down, this area is widely researched. Conventional clustering methods have difficulties to detect single article as a single cluster even though many single articles exists. In this paper, we propose a method to cluster news articles that exclude single articles in advance by using proper noun information, topographic information and other characteristics between single and non-single articles. In evaluation, we use half a y...

Search engines are necessary to find information from the Internet. There is an investigation report that users recognize that information from search engines' results is as believable as information from television. That is, we can understand a part of the influence which a certain site gives to the society by examining search engine rankings. In this paper, to examine the influence of Wikipedia, that has become the pronoun of the encyclopedia in the Internet, we have conducted the experiments. We collected ranking positions of the articles in the Japanese version of Wikipedia by using sea...

The number of Web pages distributed from Web servers is estimated about 53.7 billion as of Oct. 2005. We had gathered 14,456,201,906 Web pages from 5,548 Web servers during Jan. 2004 to July 2006. It had been conducted as part of e-Society project which is one of MEXT, Ministry of Education, Culture, Sports, Science and Technology, leading projects. Speedup of crawling Web pages conflicts with Web-site friendly crawling, however, both are indispensable for gathering Web pages. In the project, we have studied and proposed a dynamic delay adjustment scheme for accessing Web servers to prevent...

Free encyclopedia Wikipedia on the Internet contains 490,000 Japanese articles and its volume of information is huge and useful. However, the trustworthiness of the articles' contents becomes uncertain because anyone can edit them easily. In other words, since we cannot understand exactly who edits the contents, it results in difficulty of measuring trustworthiness of the articles' contents. To such a problem the method using the edit history is proposed for measuring the trustworthiness of the articles. However, it is inapposite compared with the article and the editor with a little freque...

Clustering of internet news articles makes it possible to detect various useful information, for example, related articles, and latest topic words. From the TDT project down, this area is widely researched. Conventional clustering methods have difficulties to detect single article as a single cluster even though many single articles exists. In this paper, we propose a method to cluster news articles that exclude single articles in advance by using proper noun information, topographic information and other characteristics between single and non-single articles. In evaluation, we use half a y...

Search engines are necessary to find information from the Internet. There is an investigation report that users recognize that information from search engines' results is as believable as information from television. That is, we can understand a part of the influence which a certain site gives to the society by examining search engine rankings. In this paper, to examine the influence of Wikipedia, that has become the pronoun of the encyclopedia in the Internet, we have conducted the experiments. We collected ranking positions of the articles in the Japanese version of Wikipedia by using sea...

Free encyclopedia Wikipedia on the Internet contains 490,000 Japanese articles and its volume of information is huge and useful. However, the trustworthiness of the articles' contents becomes uncertain because anyone can edit them easily. In other words, since we cannot understand exactly who edits the contents, it results in difficulty of measuring trustworthiness of the articles' contents. To such a problem the method using the edit history is proposed for measuring the trustworthiness of the articles. However, it is inapposite compared with the article and the editor with a little freque...

According to our investigation result in Oct. 2005, the number of Web pages all over the world is estimated 53.7 billion. We have investigated TLD distribution and Language Distribution of Web pages based on 10.7 billion Web page dataset. In this paper, as one of our Web statics investigation series, we analyzed three kinds of distribution based on 10.7 billion Web page dataset, distribution of geographical location of Web server, the number of virtual hosts per one Web server, and the number of back links, i.e. the value of in-degree, per one Web server. Our results show (1) about 95.5% of...

Many people use search engines every day to retrieve documents from the Web. Although the social influence of search engine rankings has become significant, ranking algorithms are not disclosed. In this paper we have investigated three major search engine rankings by analyzing two kinds of data. One is the weekly ranking snapshots of top 250. Web pages we collected for almost one year by submitting 1,000 pre-selected queries; the other comprises back-linked Web pages gathered by our own Web crawling. As a result, we have confirmed that (1) several top 10 rankings are mutually similar however the following ranked Web pages are almost different, (2) ranking transitions have their own characteristics, and (3) each search engine's ranking has its own correlation with the number of back-linked Web pages.

The estimated number of static web pages in Oct 2005 was over 20.3 billion, which was determined by multiplying the average number of pages per web server based on the results of three previous studies, 200 pages, by the estimated number of web servers on the Internet, 101.4 million. However, based on the analysis of 8.5 billion web pages that we crawled by Oct. 2005, we estimate the total number of web pages to be 53.7 billion. This is because the number of dynamic web pages has increased rapidly in recent years. We also analyzed the web structure using 3 billion of the 8.5 billion web pages that we have crawled. Our results indicate that the size of the "CORE," the central component of the bow tie structure, has increased in recent years, especially in the Chinese and Japanese web.

Critical database applications require 2-safe replication between at least two sites for disaster-tolerant services. At the same time, they must provide consistent and low-latency results to their clients in normal cases. In this paper, we propose Optimistic Transactional Active Replication (OTAR), which replicates the transaction logs with low latency and provides a consistent view to database applications. The latency of our replication is lower than Passive Replication, and guarantees the serializability of transaction isolation levels that cannot be supported by Active Replication. For our replication, each client sends a transaction request to all replicas and all of the replicas execute the request and optimistically return the result of the transaction to the client. Each replica generates a causality history of the transaction, sent to the client with the result. With the causality histories, the client can make sure that the requested transaction was executed in the same order at all of the replicas and eventually commit it. If the client cannot validate the order, then the client waits for the pessimistic result of the transaction from the replicas. This paper describes the algorithm and its properties. © 2008 ACM.

Multiple sequence alignments (MSAs) are useful tools in bioinformatics, and many MSA algorithms have been developed. We have developed an MSA program PRIME, which is one of the most accurate programs. However, PRIME is slower than other leading MSA programs. Therefore, we newly incorporate heuristics into PRIME. The benchmark results indicated that these heuristics contributed to significant reduction in the computational time with the slight accuracy decrease. Additionally, we evaluated the effectiveness of an algorithm based on maximal expected accuracy (MEA). Our experiments revealed tha...

Multiple sequence alignments (MSAs) are useful tools in bioinformatics, and many MSA algorithms have been developed. We have developed an MSA program PRIME, which is one of the most accurate programs. However, PRIME is slower than other leading MSA programs. Therefore, we newly incorporate heuristics into PRIME. The benchmark results indicated that these heuristics contributed to significant reduction in the computational time with the slight accuracy decrease. Additionally, we evaluated the effectiveness of an algorithm based on maximal expected accuracy (MEA). Our experiments revealed tha...

This paper proposes a new method for the automatic non-photorealistic rendering based on adding freehand borderlines to photographs. The proposed method enables various borderline expressions by extracting borderlines from an input image, and pouring various line patterns which are drawn with a pencil, a pen, a brush, and a crayon. That results in automatic generation of the picture which user hopes for. In order to extract natural borderlines from a picture, we propose a new method to extract a series of borderline, because conventional borderline extraction methods have problems such as d...

As hard disks tend to be bottleneck devices in the current computer architecture, enhancing hard disk access speed is one of the most efficient factors to improve the total performance of computers. However, hardware modification with or without software modification is costly. Accordingly, we propose a new acceleration method implemented at the OS kernel level, which has no requirement for modification of hardware or existing applications. Specifically, our method exploits remote memory to extend local disk cache. We have implemented our method on Linux Kernel 2.6. The PostgreSQL benchmark...

Recently, both the necessity for English and opportunities to write English have became higher and higher among non-native English speakers. But most of Japanese people tend to made many errors in English article usage when they write English. In this paper, we propose a method for detecting article errors in English by using search engines. Since search engines index great amounts of text data on web pages, search engine based methods are able to detect undetectable errors which conventional corpus based method cannot detect. Lapata et al. proposed a method for detecting article errors bas...

Most people use search engines in order to retrieve documents on the web. In this way, the social influence of search engines' ranking is large, however, the algorithms of deciding ranking are not declared. In this paper, we have investigated three major search engines' rankings with analyzing ranking data that we collected by submitting 1000 queries weekly. As a result, we have confirmed that (1) the several top tens rankings of famous search engines are similar mutually, (2) the ranking transitions are different each other, and (3) each engine's rankings have correlation with the number o...

Recently, both the necessity for English and opportunities to write English have became higher and higher among non-native English speakers. But most of Japanese people tend to made many errors in English article usage when they write English. In this paper, we propose a method for detecting article errors in English by using search engines. Since search engines index great amounts of text data on web pages, search engine based methods are able to detect undetectable errors which conventional corpus based method cannot detect. Lapata et al. proposed a method for detecting article errors bas...

Most people use search engines in order to retrieve documents on the web. In this way, the social influence of search engines' ranking is large, however, the algorithms of deciding ranking are not declared. In this paper, we have investigated three major search engines' rankings with analyzing ranking data that we collected by submitting 1000 queries weekly. As a result, we have confirmed that (1) the several top tens rankings of famous search engines are similar mutually, (2) the ranking transitions are different each other, and (3) each engine's rankings have correlation with the number o...

This paper presents pen-based mathematical expression input system named MathBox. On MathBox, a user inputs mathematical expressions as the iteration of writing one symbol in the "box". Boxes are automatically shown along user's writing. When a user writes alphanumeric, MathBox shows the boxes for power and index. When a user writes fraction line, MathBox shows the boxes for numerator and denominator. Those interactions enable MathBox to skip the recognition of the structure of mathematical expressions. Thus a user is capable of inputting mathematical expressions in practical accuracy. The ...

This paper proposes an image retrieval system whose images are labeled and search precision is improved while the system is used. Image retrieval is categorized into two major types: one type is Text-based Image Retrieval(TBIR) which uses keywords(texts) as queries; another type is Content-based Image Retrieval(CBIR) which uses images as queries. TBIR returns images related in linguistics and meaning, CBIR returns images related in look and feel. Moreover, TBIR takes extra effort for labeling images; CBIR does not need labeling, but it does not take into account effective information of key...

It takes four to ten times more time to get data from hard disk drive than from DRAM. In this paper, we present a speed up mechanisms using a prefetching thread on a multicore system to overcome this relative deterioration of hard disk drive performance. A Prefetching thread loads data from hard disk before main thread requires the particular data. When main thread requires the data, the data will be found on disk cache so it will take no time to get the data. We have confirmed that the prefetching thread reduces the execution time of gzip. The performance of gzip increased up to 39.2%.

The purpose of this study is to show the effectiveness of shell script execution on multi-core and/or SMT (Simultaneous Multi-Threading) processors. recently, multi-core processor and SMT technique have become popular even at home and in business. However, using programs or compilers without consideration of parallelism does not give us the benefits of multi-core and multi-thread. Programmers have to do parallel programming to receive the benefits. Therefore, automatic parallelizing technique has been studied actively. This paper proposes automatic parallelizing scheme for shell script programs on multi-core and/or SMT processors. As a result of the experiment, we have confirmed that the speed-up of automatic parallelized shell script program is 1.4 to 1.8 times in comparison with the original shell script program.

The purpose of this study is to show the effectiveness of shell script execution on multi-core and/or SMT (Simultaneous Multi-Threading) processors. recently, multi-core processor and SMT technique have become popular even at home and in business. However, using programs or compilers without consideration of parallelism does not give us the benefits of multi-core and multi-thread. Programmers have to do parallel programming to receive the benefits. Therefore, automatic parallelizing technique has been studied actively. This paper proposes automatic parallelizing scheme for shell script prog...

It takes four to ten times more time to get data from hard disk drive than from DRAM. In this paper, we present a speed up mechanisms using a prefetching thread on a multicore system to overcome this relative deterioration of hard disk drive performance. A Prefetching thread loads data from hard disk before main thread requires the particular data. When main thread requires the data, the data will be found on disk cache so it will take no time to get the data. We have confirmed that the prefetching thread reduces the execution time of gzip. The performance of gzip increased up to 39.2%.

Inputting mathematical expressions with a mouse and a keyboard is a troublesome task. Thus, a number of mathematical expression recognition systems capable of recognizing handwritten mathematical expressions to input them into computers have been proposed. Even with these systems, however, structure recognition of mathematical expressions is still difficult. This paper presents MathBox, a new pen-based interface for inputting mathematical expressions into computers. MathBox interactively shows "boxes" in which the user can write one symbol. The boxes are shown along with the user's writing. For example, when the user writes 'x,' the boxes for a power and an index of 'x' and for the next symbol are shown. When the user inputs a fraction line, boxes for the numerator, denominator, and the next symbol are shown. MathBox skips recognizing the structures of expressions, which enables users to write mathematical expressions with practical accuracy.

In this paper, we propose a new system extracting potentially copyright infringement texts from the Web, called EPCI. EPCI extracts them in the following way: (1) generating a set of queries based on a given copyright reserved seed-text, (2) putting every query to search engine API, (3) gathering the search result Web pages from high ranking until the similarity between the given seed-text and the search result pages becomes less than a given threshold value, and (4) merging all the gathered pages, then re-ranking them in the order of their similarity. Our experimental result using 40 seed-texts shows that EPCI is able to extract 132 potentially copyright infringement Web pages per a given copyright reserved seed-text with 94% precision in average.

Inputting mathematical expressions with a mouse and a keyboard is a troublesome task. Thus, a number of mathematical expression recognition systems capable of recognizing handwritten mathematical expressions to input them into computers have been proposed. Even with these systems, however, structure recognition of mathematical expressions is still difficult. This paper presents MathBox, a new pen-based interface for inputting mathematical expressions into computers. MathBox interactively shows "boxes" in which the user can write one symbol. The boxes are shown along with the user's writing. For example, when the user writes 'x,' the boxes for a power and an index of 'x' and for the next symbol are shown. When the user inputs a fraction line, boxes for the numerator, denominator, and the next symbol are shown. MathBox skips recognizing the structures of expressions, which enables users to write mathematical expressions with practical accuracy.

Estimating mutual interactions of genetic networks is mainly to infer the mutual control relationships from multiple genes from the gene expression data. Such correlations are typically expressible in the form of nonlinear simultaneous differential equations. However, most work to date has employed S-systems as an expression of such differential equations, allowing only rough approximations of mass actions, and as such it was difficult to determine the actual correlations between the genes. Instead, we formulate the mutual interactions as actual simultaneous partial differential equations, and automatically determine its structure and coefficients using genetic programming (GP) from a given data series. Parallel implementation of the scheme in a Grid environment using our Jojo Grid programming system for Java has resulted in precise determination of the equations in many cases within some reasonable time.

The domain linker prediction plays an important role in efficient protein structure analysis. Since previous domain linker prediction methods have employed sliding window, these methods do not explicitly consider the position dependence of amino acids within domain linkers In this paper, we propose a novel domain linker prediction method, focusing on both ends of the domain linker. Our method employs Support Vector Machines, which train on position dependence of amino acids extracted from the position-specific scoring matrix. As a result of the experiment using data set of coil regions dete...

We built a terabyte-scale web data collection, NW1000G-04, which was used in the NTCIR-5 WEB task. This report describes the process of building the collection and some statistics of it in detail.

Due to explosive increase of the number of web pages, the number of copyright violation web pages, such as lyrics or news citation pages without permission, has also been increased. To solve this problem, we propose a system for detecting copyright violation web pages. The proposed system consists of three steps. Firstly, the system generates search keywords on phrasal units, called "bunsetsu", which are included in the "seed page." Secondly, on search keywords generated by the first step, the system gathers candidate of web pages violating copyright by using Google or Yahoo! web service. F...

Due to recent widespread use of internet auction, a huge amount of users trade with each other. At the same time, damages from the fraud caused by abuse users have been become a serious problem of the internet auction system. In this paper, we developed abuse user detecting system referring to rating log data, which is a part of auction log data. Rating log data indicates assesment between seller and buyer. The system consists of two methods; extracting users who are rated as "Good" abusively, and extracting abuse users' community based on one abuse user. Our evaluation shows proposing syst...

Due to recent widespread use of internet, many people use internet auction system, and trade with each other. At the same time, damages from the fraud caused by abuse users have been become a serious problem of the internet auction system. In this paper, we developed abuse user detecting system referring to rating log data, which is a part of auction log data. Rating log data indicates assesment between seller and buyer. The system consists of two methods; extracting users who are rated as "Good" abusively, and extracting abuse users' community based on one abuse user. Our evaluation shows ...

Due to explosive increase of the number of web pages, the number of copyright violation web pages, such as lyrics or news citation pages without permission, has also been increased. To solve this problem, we propose a system for detecting copyright violation web pages. The proposed system consists of three steps. Firstly, the system generates search keywords on phrasal units, called "bunsetsu", which are included in the "seed page." Secondly, on search keywords generated by the first step, the system gathers candidate of web pages violating copyright by using Google or Yahoo! web service. F...

In Content-based image retrieval, the classifications is needed for better performances of (i)speeds of retrieval and (ii)semanticity of retrieval. Our system extracts the most attentional points by using a selective visual attention model which extracts feature vectors of attentional points in images. And our system classifies feature vectors by hierarchical clustering with residuals. An attentional point in an image is outlier in an image, or special outlier. We propose extension of selective attention model to extract temporal outlier with residual vectors, and the method of moving atten...

There exist many methods to reconstract the 3D model from the real object. However, they have some restrictions such as using expensive devices, using reference objects, or based on assumption that the target object is composed of one material. This paper proposes a new method that is based on shape from shading using multiple views.The proposed method treats the object composed of multiple materials. The proposed method preliminarily clusters the reflectances using the input images, and then analyze the 3D shape and the reflectance parameters.

There exist many methods to reconstract the 3D model from the real object. However, they have some restrictions such as using expensive devices, using reference objects, or based on assumption that the target object is composed of one material. This paper proposes a new method that is based on shape from shading using multiple views.The proposed method treats the object composed of multiple materials. The proposed method preliminarily clusters the reflectances using the input images, and then analyze the 3D shape and the reflectance parameters.

In Content-based image retrieval, the classifications is needed for better performances of (i) speeds of retrieval and (ii) semanticity of retrieval. Our system extracts the most attentional points by using a selective visual attention model which extracts feature vectors of attentional points in images. And our system classifies feature vectors by hierarchical clustering with residuals. An attentional point in an image is outlier in an image, or special outlier. We propose extension of selective attention model to extract temporal outlier with residual vectors, and the method of moving att...

The increase of the gap between processor speed and memory speed makes cache memory more important. However, wire delay in large cache grows that results from the process miniaturization. Therefore, cache memory access will become bottle neck. This paper proposes an optimization technique for cache memory considering wire delay. We implement this technique with SimpleScalar 3.0d and evaluate with SPEC95 CINT and SPEC2000 CINT. In the result, IPC grows at the average of 1.17 times.

The increase of the gap between processor speed and memory speed makes cache memory more important. However, wire delay in large cache grows that results from the process miniaturization. Therefore, cache memory access will become bottle neck. This paper proposes an optimization technique for cache memory considering wire delay. We implement this technique with SimpleScalar 3.0d and evaluate with SPEC95 CINT and SPEC2000 CINT. In the result, IPC grows at the average of 1.17 times.

Mathematical expression recognition systems which recognize mathematical expressions and translates them into digital data usable in computer is needed. However characters and symbols in mathematical expressions are sometimes similar and difficult to discriminate. This paper proposes a method to recognize similar character pairs with two types of SVM (Support Vector Machine). One is normal SVM which uses images of handwriting as input; the other is SVMGDTW which uses sequences of pen position. With the proposed method, "γ"and "r" are discriminated with a recognition rate of 86.7%, "ω" and "...

Content-based image retrievals (CBIR) have difficulty on concentrated information processing at the point which seems important. This is caused by difficulty on automated selection of "informative" points. As one part of studies of humans or primate brain, selective visual attention has been researched, which model processes for decision of the attentional point of an image before eye movements when the subject is presented an image. To use local information of an image, we propose a CBIR system with the feature vector at the most attentional point of the image. We introduce model of select...

Mathematical expression recognition systems which recognize mathematical expressions and translates them into digital data usable in computer is needed. However characters and symbols in mathematical expressions are sometimes similar and difficult to discriminate. This paper proposes a method to recognize similar character pairs with two types of SVM (Support Vector Machine). One is normal SVM which uses images of handwriting as input; the other is SVMGDTW which uses sequences of pen position. With the proposed method, "γ"and "r" are discriminated with a recognition rate of 86.7%,"ω" and "w...

Content-based image retrievals(CBIR) have difficulty on concentrated information processing at the point which seems important. This is caused by difficulty on automated selection of "informative" points. As one part of studies of humans or primate brain, selective visual attention has been researched, which model processes for decision of the attentional point of an image before eye movements when the subject is presented an image. To use local information of an image, we propose a CBIR system with the feature vector at the most attentional point of the image. We introduce model of selecti...

Sequential pattern mining can be used to extract frequent sequences maintaining their transaction order. As conventional sequential pattern mining methods do not consider transaction occurrence time intervals, it is impossible to predict the time intervals of any two transactions extracted as frequent sequences. Thus, from extracted sequential patterns, although users are able to predict what events will occur, they are not able to predict when the events will occur. Here, we propose a new sequential pattern mining method that considers time intervals. Using Japanese earthquake data, we confirmed that our method is able to extract new types of frequent sequences that are not extracted by conventional sequential pattern mining methods. © Springer-Verlag Berlin Heidelberg 2006.

Sequential pattern mining is an important data mining method with broad applications that can extract frequent sequences while maintaining their order. However, it is important to identify item intervals of sequential patterns extracted by sequential pattern mining. For example, a sequence &lt
A
B &gt
with a 1-day interval and a sequence &lt
A
B &gt
with a 1-year interval are completely different
the former sequence may have some association, while the latter may not. To adopt item intervals, two approaches have been proposed for integration of item intervals with sequential pattern mining
(1) constraint-based mining and (2) extended sequence-based mining. However, although constraint-based mining approach avoids the extraction of sequences with non-interest time intervals such as too long intervals it has setbacks in that it is difficult to specify optimal constraints related to item interval, and users must re-execute constraint-based algorithms with changing constraint values. On the other hand, extended sequence-based mining approach does not need to specify constraints and re-execute. Since extended sequence-based mining approach cannot adopt any constraints based on time intervals, it may extract meaningless patterns, such as sequences with too long item intervals. This means these two approaches have not only advantages but also disadvantages. To solve this problem, in this paper, we generalize sequential pattern mining with item interval. The generalization includes three points
(a) a capability to handle two kinds of item interval measurement, item gap and time interval, (b) a capability to handle extended sequences which are defined by inserting pseudo items based on the interval itemization function, and (c) adopting four item interval constraints. Generalized sequential pattern mining is able to substitute all types of conventional sequential pattern mining algorithms with item intervals. Using Japanese earthquake data, we have confirmed that our proposed algorithm is able to extract sequential patterns with item interval, defined in a flexible manner by the interval itemization function. © 2006 ACADEMY PUBLISHER.

Applying conventional sequential pattern mining methods to text data extracts many uninteresting patterns, which increases the time to interpret the extracted patterns. To solve this problem, we propose a new sequential pattern mining algorithm by adopting the following two constraints. One is to select sequences with regard to item intervals-The number of items between any two adjacent items in a sequence-And the other is to select sequences with regard to item attributes. Using Amazon customer reviews in the book category, we have confirmed that our method is able to extract patterns faster than the conventional method, and is better able to exclude uninteresting patterns while retaining the patterns of interest.

Background: Multiple sequence alignment (MSA) is a useful tool in bioinformatics. Although many MSA algorithms have been developed, there is still room for improvement in accuracy and speed. In the alignment of a family of protein sequences, global MSA algorithms perform better than local ones in many cases, while local ones perform better than global ones when some sequences have long insertions or deletions (indels) relative to others. Many recent leading MSA algorithms have incorporated pairwise alignment information obtained from a mixture of sources into their scoring system to improve accuracy of alignment containing long indels. Results: We propose a novel group-to-group sequence alignment algorithm that uses a piecewise linear gap cost. We developed a program called PRIME, which employs our proposed algorithm to optimize the well-defined sum-of-pairs score. PRIME stands for Profile-based Randomized Iteration MEthod. We evaluated PRIME and some recent MSA programs using BAliBASE version 3.0 and PREFAB version 4.0 benchmarks. The results of benchmark tests showed that PRIME can construct accurate alignments comparable to the most accurate programs currently available, including L-INS-i of MAFFT, ProbCons, and T-Coffee. Conclusion: PRIME enables users to construct accurate alignments without having to employ pairwise alignment information. PRIME is available at http://prime.cbrc.jp/. © 2006 Yamada et al
licensee BioMed Central Ltd.

Applying conventional sequential pattern mining methods to text data extracts many uninteresting patterns, which increases the time to interpret the extracted patterns. To solve this problem, we propose a new sequential pattern mining algorithm by adopting the following two constraints. One is to select sequences with regard to item intervals-The number of items between any two adjacent items in a sequence-And the other is to select sequences with regard to item attributes. Using Amazon customer reviews in the book category, we have confirmed that our method is able to extract patterns faster than the conventional method, and is better able to exclude uninteresting patterns while retaining the patterns of interest.

Sequential pattern mining can be used to extract frequent sequences maintaining their transaction order. As conventional sequential pattern mining methods do not consider transaction occurrence time intervals, it is impossible to predict the time intervals of any two transactions extracted as frequent sequences. Thus, from extracted sequential patterns, although users are able to predict what events will occur, they are not able to predict when the events will occur. Here, we propose a new sequential pattern mining method that considers time intervals. Using Japanese earthquake data, we confirmed that our method is able to extract new types of frequent sequences that are not extracted by conventional sequential pattern mining methods.

This paper proposes a technique for applying a suitable contour extraction method to a texture region and a non-texture region to improve the accuracy of the contour extraction after dividing an image into these two regions. The most basic idea to extract contours is edge detection by derivative filters, however, it is hard to say edges equal borderlines. Thus, a texture analysis is essential to get the accurate result. Most of the conventional studies apply either edge detection or texture analysis to the whole in an image. Against that, in this paper, we firstly extract a texture region a...

This paper proposes a sample collection system for online handwritten mathematical expressions based on digital pens. In the prior online handwriting character recognition systems, samples collected by pen tablets have been used. But data by pen tablets are (1) difficult to collect because users aren't familiar with pen tablets, (2) different from real handwriting because users have to look at their monitors to write characters. On the contrary digital pens, easy to use for the first time, are used and samples written by 74 examinees are collected. By recognition experiments following facts...

In data mining researches, sequential pattern mining extracts frequent sequences keeping their event occurrence orders. Since conventional sequential pattern mining methods have not consider event occurrence time intervals, it is impossible to understand time intervals of any two events which are included by result sequences. In this paper, we propose a new sequential pattern mining method which considers event occurrence time intervals. As a result of our evaluation in applying the earthquake data. We confirmed our new method can extract new kind of frequent sequences which couldn't extracted by conventional sequential pattern mining methods.

In data mining researches, sequential pattern mining extracts frequent sequences keeping their event occurrence orders. Since conventional sequential pattern mining methods have not consider event occurrence time intervals, it is impossible to understand time intervals of any two events which are included by result sequences. In this paper, we propose a new sequential pattern mining method which considers event occurrence time intervals. As a result of our evaluation in applying the earthquake data. We confirmed our new method can extract new kind of frequent sequences which couldn't extrac...

In data mining researches, sequential pattern mining extracts frequent sequences keeping their event occurrence orders. Since conventional sequential pattern mining methods have not consider event occurrence time intervals, it is impossible to understand time intervals of any two events which are included by result sequences. In this paper, we propose a new sequential pattern mining method which considers event occurrence time intervals. As a result of our evaluation in applying the earthquake data. We confirmed our new method can extract new kind of frequent sequences which couldn't extrac...

Conventional frequent itemset mining algorithms require some user-specified minimum support, and then mine frequent itemsets with support values that are higher than the minimum support. As it is difficult to predict how many frequent itemsets will be mined with a specified minimum support, the Top-κ mining concept has been proposed. The Top-κ Mining concept is based on an algorithm for mining frequent itemsets without a minimum support, but with the number of most κ frequent itemsets ordered according to their support values. However, the Top-κ mining concept still requires a threshold κ. Therefore, users must decide the value of κ before initiating mining. In this paper, we propose a new mining algorithm, called "TF^2P-growth, " which does not require any thresholds. This algorithm mines itemsets with the descending order of their support values without any thresholds and returns frequent itemsets to users sequentially with short response time.

In recent years, Buffer overflow Attacks are increasing. Buffer overflow is caused by inputting larger data than date space which prepared for various numbers. The most danger buffer overflow is stack overflow. When Stack Overflow occurs, return address is re-written and malicious code becomes executable. This paper proposes defense technique against buffer overflow by segmenting stack frame. We implement this technique Simplescalar tool set ver3.0d and evaluate with SPEC CINT95. Evaluation result shows that this technique causes 2.3% performance degradation.

In recent years, Buffer overflow Attacks are increasing. Buffer overflow is caused by inputting larger data than date space which prepared for various numbers. The most danger buffer overflow is stack overflow. When Stack Overflow occurs, return address is re-written and malicious code becomes executable. This paper proposes defense technique against buffer overflow by segmenting stack frame. We implement this technique Simplescalar tool set ver3.0d and evaluate with SPEC CINT95. Evaluation result shows that this technique causes 2.3% performance degradation.

In recent years, Buffer overflow Attacks are increasing. Buffer overflow is caused by inputting larger data than date space which prepared for various numbers. The most danger buffer overflow is stack overflow. When Stack Overflow occurs, return address is re-written and malicious code becomes executable. This paper proposes defense technique against buffer overflow by segmenting stack frame. We implement this technique Simplescalar tool set ver3.0d and evaluate with SPEC CINT95. Evaluation result shows that this technique causes 2.3% performance degradation.

In this paper, we improve the MPI Execution Time Estimator (MPIETE) to reduce the prediction error of communication time. MPIETE we have proposed is the execution time estimation tool for MPI programs. MPIETE's scheme divides a MPI program into the computation blocks and the communication blocks, and then predicts the total execution time by summing the execution time of each block. Since estimating the block execution time is fast, MPIETE enables to predict the total execution time faster than executing MPI program actually. However, MPIETE assumes no network contension. This results in some errors to predict the delay-time with network contentions. In this paper, by proposing the new estimation scheme for communication block including the delay-time, we improve the MPIETE. The proposed scheme enables to predict the performance decrement and to find out the number of the Processing Unit (PU) where the target platform marks the best performance. We have evaluated MPIETE2, that improves MPIETE with the proposed scheme, using EP, CG, FT, MG from NAS Parallel Benchmmarks 2.4. As the results for 2-128PU, the prediction error ranges are less than 14% and the execution time of the prediction is 1/4 times smaller than the actual execution time. Moreover, MPIETE2 predicts exactly the number of PU where the target platform marks the best performance.

The branch prediction is installed on the recent processor to avoid stalling pipeline. Branch prediction is a kind of speculative execution for control dependence. In the recent year, the deeper pipeline gets, the higher branch miss prediction penalty reaches. Thus, branch miss prediction rate must lower to rise processor performance. Recently, many various branch predictors have been proposed. Hybrid branch predictors composed of multiple pattern history tables (PHT) show the highest accuracy among them. The Bi-Mode branch predictor is the most famous of the hybrid branch predictors. On the Bi-Mode predictor, the Choice PHT judges the branch bias and selects the Direction PHT(Taken or NotTaken PHT). This paper focuses on the Weakly Branches which the Choice PHT judges Weakly Taken or NotTaken don't have the branch bias. In order to avoid the Weakly branch influence on the Direction PHTs, we propose "the Tri-Mode brach predictor" added the Weakly PHT predicting the Weakly branches. On the 12KB Tri-Mode predictor, the branch miss reduction rate from the Bi-Mode predictor shows average 2.78% in the SPECint95(ref inputs) benchmark simulation.

The branch prediction is installed on the recent processor to avoid stalling pipeline. Branch prediction is a kind of speculative execution for control dependence. In the recent year, the deeper pipeline gets, the higher branch miss prediction penalty reaches. Thus, branch miss prediction rate must lower to rise processor performance. Recently, many various branch predictors have been proposed. Hybrid branch predictors composed of multiple pattern history tables (PHT) show the highest accuracy among them. The Bi-Mode branch predictor is the most famous of the hybrid branch predictors. On th...

In this paper, we improve the MPI Execution Time Estimator (MPIETE) to reduce the prediction error of communication time. MPIETE we have proposed is the execution time estimation tool for MPI programs. MPIETE's scheme divides a MPI program into the computation blocks and the communication blocks, and then predicts the total execution time by summing the execution time of each block. Since estimating the block execution time is fast, MPIETE enables to predict the total execution time faster than executing MPI program actually. However, MPIETE assumes no network contension. This results in so...

This paper describes unsupervised selective attention system by using residual information of Predictive Coding. The imitation system of brain visual passway by Rao and Ballard, or Predictive Coding, uses learning rule to minimamize the residuals between the inputs and the internal predictions, which results to get linear coding of subimages by basis set. Residual-based selective attention model can select out "informative" subimages from a validation image because they have features which is rare to been seen in learning sample subimages. We experiment our system to have it learn some simi...

Recently, the gap between CPU processing speed and the data transmission speed from the main memory has lowered execution speed. Thus, data caching technique becomes more important. Particularly in pointer-based programs which have nonlinear access patterns, the cache miss rate is very high. To solve this problem, Pre-Execution has been proposed as a cache miss latency tolerance technique that makes one or more helper threads running in the spare CPU's resources ahead of the main computation. This paper proposes the synchronous technique between main thread and helper thread. Furthermore, t...

In recent years, as the pipeline's length gets deeper, and the instruction fetch width and the issue width become wider, more accurate branch predictors are needed. Branch predictors predict with the 2 bit saturating counters (predictor counters) whose state is changed by the execution result of the branch. As a result of analyzing the prediction accuracy in each state (Strongly Taken, Weakly Taken, Weakly Not-taken and Strongly Not-taken) of prediction counters, it turns out that the prediction accuracy in the Weak states of gshare predictor is especially low. We propose the predictor sele...

This paper proposes PlusDBG to improve both precision and pseudo-recall by extending the conventional Web community extraction scheme. Precision is defined as the percentage of relevant Web pages extracted as members of Web communities and pseudo-recall is defined as the sum of the number of relevant Web pages extracted as members of Web communities. The proposed scheme adopts the new distance parameter defined by the relevance between a Web page and a Web community, and extracts the Web community with higher precision and pseudo-recall. Moreover, we have implemented and evaluated the proposed scheme. Our results confirm that the proposed scheme is able to extract about 3.2-fold larger numbers of members of Web communities than the conventional scheme, while maintaining equivalent precision.

This paper proposes PlusDBG to improve both precision and pseudo-recall by extending the conventional Web community extraction scheme. Precision is defined as the percentage of relevant Web pages extracted as members of Web communities and pseudo-recall is defined as the sum of the number of relevant Web pages extracted as members of Web communities. The proposed scheme adopts the new distance parameter defined by the relevance between a Web page and a Web community, and extracts the Web community with higher precision and pseudo-recall. Moreover, we have implemented and evaluated the proposed scheme. Our results confirm that the proposed scheme is able to extract about 3.2-fold larger numbers of members of Web communities than the conventional scheme, while maintaining equivalent precision.

Recently, the gap between CPU processing speed and the data transmission speed from the main memory has greatly influenced execution speed. Thus data caching technique become more important However, in pointer-based programs which have a nonlinear access pattern a cache memory does not function effectively. To solve this problem, Pre-Execution is a cache miss latency tolerance technique that uses one or more helper threads running in spare CPU's 'resources ahead of the main computation. This paper proposes the synchronous technique of the Helper thread. Furthermore, this paper examines the ...

This paper proposes a new Japanese-to-English-translation support system using search engines. The system uses Google to address some of the problems that non-native speakers of English will often encounter when trying to write English sentences. Especially, appropriate choices of English nouns and prepositions are a challenge for Japanese. To solve these problems, we focus on the techniques presented in the book titled "Using Google to Improve Your Translation Skills" written by Susumu Ando, published by Maruzen in 2003. The proposed system is implemented by automatically constructing opti...

This paper proposes a new Japanese-to-English-translation support system using search engines. The system uses Google to address some of the problems that non-native speakers of English will often encounter when trying to write English sentences. Especially, appropriate choices of English nouns and prepositions are a challenge for Japanese. To solve these problems, we focus on the techniques presented in the book titled "Using Google to Improve Your Translation Skills" written by Susumu Ando, published by Maruzen in 2003. The proposed system is implemented by automatically constructing opti...

The amount of the information on the Web is huge and the number of Web page is estimated about 9. 25 billion in April 2004. Moreover, one billion Web pageswill be added to the Web repository every year, which is estimated by calculating its average increase in these two years. It is not too much to say that the huge Web repository has all kinds of information, knowledge, and know-how that can not be learned by a human even if he spent all the life time to learn them. In this paper, we introduce the major research projects that concern how to crawl the huge Web pages, how to keep them up-to-date, and how to make full use of them.

The amount of the information on the Web is huge and the number of Web page is estimated about 9. 25 billion in April 2004. Moreover, one billion Web pageswill be added to the Web repository every year, which is estimated by calculating its average increase in these two years. It is not too much to say that the huge Web repository has all kinds of information, knowledge, and know-how that can not be learned by a human even if he spent all the life time to learn them. In this paper, we introduce the major research projects that concern how to crawl the huge Web pages, how to keep them up-to-...

The loop parallelization scheme improves the program performance, dramatically. However, when the data dependence cannot be analyzed statically, the conventional parallelization scheme assumes that the data dependence exists. Thus the loop containing unanalyzed Loop Carried Dependence cannot be parallelizedthe thread level speculative execution scheme has been known to speedup such a loop. In this paper, we propose the scheme to apply the speculative execution alternatively only to the portion expected to be speeduped effectively, using the overhead parameter required for the book-keeping p...

In Reinforcement Learning, the agent learns by trial and error from a state without knowledge. Therefore, reinforcement learning has drawbacks that learning is slow. It is a serious problem how learns at high speed. In order to learn at high speed, some methods have been proposed. In the methods, the value function is divided. Then each divided value function is assigned to each processor, and updated in parallel. However, the method needs to exchange experiences frequently between the divided value function because of the character of reinforcement learning. It was a problem in the previou...

The loop parallelization scheme improves the program performance, dramatically. However, when the data dependence cannot be analyzed statically, the conventional parallelization scheme assumes that the data dependence exists. Thus the loop containing unanalyzed Loop Carried Dependence cannot be parallelizedthe thread level speculative execution scheme has been known to speedup such a loop. In this paper, we propose the scheme to apply the speculative execution alternatively only to the portion expected to be speeduped effectively, using the overhead parameter required for the book-keeping p...

In Reinforcement Learning, the agent learns by trial and error from a state without knowledge. Therefore, reinforcement learning has drawbacks that learning is slow. It is a serious problem how learns at high speed. In order to learn at high speed, some methods have been proposed. In the methods, the value function is divided. Then each divided value function is assigned to each processor, and updated in parallel. However, the method needs to exchange experiences frequently between the divided value function because of the character of reinforcement learning. It was a problem in the previou...

In this paper, we propose the MPI Execution Time Estimator (MPIETE), the execution time estimation tool for MPI programs, helping you to choose the best suited computing platform to execute a MPI program. Conventional execution time estimation schemes are not able to model a computing platform or a MPI program perfectly, which results in no reusable of any parameters of both the computing platform and the MPI program. On the contrary, the proposed scheme enables to reuse all the parameters of both the computing platform and the MPI program even for the estimation on another computing platfo...

The branch prediction is installed on the recent procesor to avoid stalling pipeline. Branch prediction is a kind of speculative execution for control dependence. In the recent year, the deeper pipeline gets, the higher branch miss prediction penalty reaches. Thus, branch miss prediction rate must lower to rise processor performance. The branch prediction predicts a branch direction and a branch target address. BTB (Branch Target Buffer) registers Taken branch. We found that the most branches, which do not have BTB entry are NotTaken branches. We propose the branch predictor reffering a BTB...

The branch prediction is installed on the recent processor to avoid stalling pipeline. Branch prediction is a kind of speculative execution for control dependence. In the recent year, the deeper pipeline gets, the higher branch miss prediction penalty reaches. Thus, branch miss prediction rate must lower to rise processor performance. The branch prediction predicts a branch direction and a branch target address. BTB (Branch Target Buffer) registers Taken branch. We found that the most branches, which do not have BTB entry are NotTaken branches. We propose the branch predictor reffering a BTB entry existence. The proposed predictor only undates the entry of the branch whose target address is registered in BTB, in order to allevilate aliasing. In SPECint95 (train), branch prediction miss rate lowers avarage 1.5% on 8 KB Gshare predictor and avarage 0.4% on 1.5 KB Bi-Mode predictor.

In recent years, as pipelines length deeper, more accurate branch direction predictors are needed. Most of the branch predictor tend to increase hardware budget for aliasing alleviation. This research proposes the means for miss prediction rate reduction in same hardware budget Hybrid Predictor. This predictor is called Hybrid Predictor Referenced Prediction Counter State(Hybrid-RPCS). Generally, low-predictability branches have high transition rate and no direction deviation. For low-predictability branches, prediction is turned the other way, based on a selector counter state and predicto...

In this paper, we show evaluation results of our execution-time prediction method which simply executes MPI program on 2PU. We predict the execution time of NAS Parallel Benchmarks ver.2.3 on 2-128PU. Execution time prediction is effective technique to determine the optimal number of PU for some target applications. The most existing methods are not only for predicting execution-time but for obtaining information of various overhead, and hence need the long simulation time. On the other hand, since our purpose is to obtain execution time only, our method can predict faster than actual execu...

Frequent patterns mining is one of the important problem in data mining research. The Apriori is a prominent algorithm followed by many variants. In 2000, the FP-growth, which is reported to be faster than the Apriori, was proposed. However, many parallel algorithms of frequent pattern mining are still based on the Apriori. In this paper, we propose a parallelized version of the FP-growth, which accesses disks in parallel and constructs local FP-trees on each local memory. As a result of the evaluation using 32 node PC cluster, our method is approximately 2 and 130 times faster than sequent...

Frequent patterns mining is one of the important problem in data mining research. The Apriori is a prominent algorithm followed by many variants. In 2000, the FP-growth, which is reported to be faster than the Apriori, was proposed. However, many parallel algorithms of frequent pattern mining are still based on the Apriori. In this paper, we propose a parallelized version of the FP-growth, which accesses disks in parallel and constructs local FP-trees on each local memory. As a result of the evaluation using 32 node PC cluster, our method is approximately 2 and 130 times faster than sequent...

In recent years, branch predictors with multiple prediction tables, which are called "Hybrid Predictor" in this paper, have been proposed. "Hybrid Predictor" is classfied into two categories. One is "Combining Predictor", the other is "De-Aliased Predictor". The difference between "Combining Predictor" and "De-Aliased Predictor" is a means to select a prediction table. "Combining Predictor" select a prediction table by confidence. "De-Aliased Predictor" select a prediction table by branch direction bias. Although the prediction accuracy in "Combining Predictor" is the highest, "Combining Pr...

In recent years, branch predictors with multiple PHTs(Pattern History Table) has been proposed. In this paper, branch predictors with multiple PHTs are classfied into two categories. One is "Hybrid Predictor", the other is "Multiple PHT Predictor" (.which is called in this paper). The difference between "Hybrid Predictor" and "Multiple PHT Predictor" is PHT selection confidence. In this paper, we compare "Hybrid Predictor" with "Multiple PHT Predictor". As the result, if "Hibrid Predictor" is the same size as "Multiple PHT Predictor"," Hybrid Predictor" predicts branch directions better tha...

In order to raise the processing speed of a processor, in today's processor, the technique of piplining is adapted to extract the instruction level parallelism. However, a pipeline stall occurs when a conditional branch exists. Various researches have been done, in order to raise the accuracy of prediction. In this paper, we propose a new branch prediction technique based on the transition rate, which is specifically the number of succession branch times for the same direction. The proposed scheme targets the branches that are classified into difficult prediction branch. We applied the prop...

The conventional search engines searches based on the pre-generated index. Thus, when some users search with the same query, the search engine returns same result, even if they want to obtain different results. In order to solve such a problem, in this paper, we propose the user modeling scheme based on the user's search pattern to speculate the user's intention. Consequently, we have classified the search interval to re-search into two patterns. Furthermore, we have classified 91% of a user's queries into nine patterns. Using these patterns, the search engines will be able to return the results that suite the user's intention.

The conventional search engines searches based on the pre-generated index. Thus, when some users search with the same query, the search engine returns same result, even if they want to obtain different results. In order to solve such a problem, in this paper, we propose the user modeling scheme based on the user's search pattern to speculate the user's intention. Consequently, we have classified the search interval to re-search into two patterns. Furthermore, we have classified 91% of a user's queries into nine patterns. Using these patterns, the search engines will be able to return the re...

In this paper, we propose an efficient speculative execution scheme for loops, and have confirmed the usefullness of the scheme using the compress program from SPECcpu95 benchmark. Generally, since the execution time of loops holds the large portion of the total execution time, the loop parallelization scheme improves the program performance, dramatically. However, when the data dependence cannot be analyzed statically, the conventional parallelization scheme assumes that the data dependence exists. For this reason, such a loop cannot be parallelized even if the loop carried dependence(LCD) occurs only once in 10,000 times, dynamically. However, the speculative execution scheme has been known to speedup such a loop. In this paper, we propose the scheme to apply the speculative execution alternatively only to the portion expected to be speeduped effectively, using the overhead parameter required for the book-keeping process when the speculation fails. Such overhead has not been considered on oonventional speculative execution schemes. The proposed scheme enables the alternative speculative execution using the overhead parameter for book-keeping, the LCD existence probability, and the timing of the speculative execution initiation. As a result, in the present stage, the execution speed is fell down to one third. To solve this problem, we also propose a new speculative execution.

In this paper, we propose an efficient speculative execution scheme for loops, and have confirmed the usefullness of the scheme using the compress program from SPECcpu95 benchmark. Generally, since the execution time of loops holds the large portion of the total execution time, the loop parallelization scheme improves the program performance, dramatically. However, when the data dependence cannot be analyzed statically, the conventional parallelization scheme assumes that the data dependence exists. For this reason, such a loop cannot be parallelized even if the loop carried dependence(LCD)...

Instruction level speculative execution schemes are classified into the branch prediction which alleviates control dependence, and the data prediction which alleviates data dependece. In this paper, we summarize 36 papers on the branch prediction and 27 papers on the data prediction in HPCA from 1996 to 2001, ISCA, MICRO, and ASPLOS from 1996 to 2000. As the general trends, until 1998, more than half of the researches on speculative execution are related to the branch prediction. However, since 1997, reseraches on data prediction have increased.

In this paper, we propose the scheme of estimating the execution time of MPI programs, and confirmed the usefulness of the scheme using NAS Parallel Benchmarks (NPB) ver 2.3. The scheme estimates the execution time of MPI program dividing into the computation part and the communication part. In estimating the execution time of the computation, we divide a MPI program into blocks that have loop structure, measure the execution time of every block, and estimate the total execution time. In estimating the communication time, we measure the communication time with the same message size which is...

Googleは，世界最大の情報を持つサーチエンジンとして有名である．Googleは，スタンフォード大学コンピュータサイエンス学科の研究プロジェクトとしてスタートした後，シリコンバレーの2大ベンチャーキャピタルから総額2 500万ドルの投資を受け，博士課程の学生であった当時25歳のLarry（Lawrence）Pageと Sergey Brinの2人が1998年9月に会社として起業した．

This paper discusses how to adopt the"Unlimited Speculative Execution"on loops. A task level speculative execution scheme, called the"Unlimited Speculative Execution", is adopted on the loops that are not able to be parallelized because of memory ambiguation or control dependences. In this paper, loops are classified into nine categories to make clear the applicable loops for the scheme. Moreover, we discusses the result after applying the scheme to SPEC95int compress program.

The authors are investigating the possibility of Java Virtual Accelerator, a run-time parallelizing interpreter/JIT compiler system which speeds up Java execution through parallelizing emulation. To realize parallelizing emulation, automatic extraction of the parallelism from sequential binary programs is important. We developed the "speculative control-data dependence graph" model to relieve the control and data dependence constraints inherent in the sequential programs. Speculative control-data dependence graph is constructed by measuring the prediction rate for both control and data values during the test run, and replacing highly predictable arcs with predict-confirm nodes. Java Jog-time Analyzer is developed for the experiment of the model described above. JJA analyzes control and data dependences statically while class files are loaded, and the intermediate code interpreter of JJA invokes data and branch prediction modules and gathers run-time statistics everytime basic block boundary is crossed. Run-time statistics such as the block execution counts, the prediction rates, the critical path execution time and the average parallelism, as well as the plot of the dependence graphs, are shown at the end of the execution. In this paper, several experiment results with JJA are shown.

The authors are investigating the possibility of Java Virtual Accelerator, a run-time parallelizing interpreter/JIT compiler system which speeds up Java execution through parallelizing emulation. To realize parallelizing emulation, automatic extraction of the parallelism from sequential binary programs is important. We developed the "speculative control-data dependence graph" model to relieve the control and data dependence constraints inherent in the sequential programs. Speculative control-data dependence graph is constructed by measuring the prediction rate for both control and data valu...

In this paper, we discuss efficient parallel execution of a dense-matrix problem considering trade-offs between fine-grain and coarse-grain communication in distributed memory machines. The solution of the triangular system of equations involves data dependencies between consecutive iterations in the outer-loop. The dependencies can be naturally solved and processed in parallel by wavefront computation. Two ways of parallelizing are presented; the element-wise fine-grain approach and the coarse-grain approach. We implemented these algorithms on both EM-X and AP 1000+. Fine-grain support mechanisms of the EM-X had a great effect on the performance of the element-wise method for relatively small problem size, while employed RISC processors of the AP1000+ brought high performance of the coarse-grain method for larger size.

In this paper, the design of the intermediate code interpreter, which executes a sequential program in parallel using speculative method, is discussed. Software techniques which enable an efficient parallel speculative execution without hardware support, such as the check point execution mechanism with which an appropriate parallel execution granularity is established, and the efficient implementation of the speculative memory operations which minimize the overhead of searching, recording and the mutual exclusion, are proposed. Experiment results to see the basic performance of these techniques are also presented. From the experiment, we confirmed that we can implement a speculative intermediate code interpreter which can result in speedup, if we adopt the soft ware techniques described in this paper.

A WWW search engine called fast speculative search engine that uses speculative execution of multiprocessor systems to shorten the total time to retrieve information from the WWW is presented. This engine predicts the user's next queries and initiates the searches with the predicted queries before receiving them to accelerate narrowing the search space. This fast speculative search engine is implemented using the data speculation on the EM-X, a highly parallel computer which can tolerate communication latency by using low latency communication and multithreading.

This paper discusses the effectiveness of the unlimited speculative execution and how to adopt the scheme on multigrain parallelizing compilers.The multigrain parallelizing compilers exploit parallelism among coarse-grain taks like loops, medium-grain tasks such as loop iterations, and near-fine-grain tasks such as statements.When we adopt the unlimited speculative execution scheme on multigrain parallelizing compilers, the codes, that are not parallelized because of memory ambiguation or control dependences, are able to be parallelized.In this paper, loops are classified into nine categori...

1997年1月時点で,世界の約83万組織,約1600万台のコンピュータがインターネットに接続し,学術論文から趣味にいたるまで,1億ページを越える情報がWWWサーバから発信されている.この膨大な情報を有効に利用するためには,必要とする情報の掲載されたページを瞬時に,かつ,的確にみつけ出すことが必須となる.このような機能を提供するWWW情報検索サービスは,1994年頃から登場し始め,現在,その数は100を越える.本稿では,WWW情報検索サービスの現状とその問題点を解説する.

EM-X is a highly parallel computer with a distributed memory. It supports fine-grain communication, whose size is two-word fixed, on an instruction execution pipeline. It achieves high communication throughput by overlapping remote memory access with thread execution, and tolerates communication latency by rapid switching of threads. We developed an 80 processor system of EM-X, and are evaluating its architectural features on the system. In this paper, we execute radix sort programs to evaluate the parallel performance of EM-X and compare the results with other parallel computers. The results show that fine grain communication achieves very good scalability, while coarse grain message passing decrease the performance on a large number of processors because of contentions on a network.

In this paper, we describe the parallelization of a sparse matrix computation, CG (Conjugate Gradient method) kernel taken from NAS parallel benchmark suite, for the EM-X multiprocessor. Dataflow mechanism of EM-X supports fine-grain communication very efficiently, which provides low latency communication, and flexible message-passing facility. We compare the performance of sparse matrix vector multiplications by the complete exchange communication, by element-wise remote update and by the element-wise remote read with multithreading. The measurements taken on the EM-X indicates effectiveness of the fine-grain communication which enables element-wise access efficiently. Fine-grain communcation is effective when problem size per PE becomes small in large scale multiprocessor systems. The complete complete exchange version incurs the negative impact due to the limitation of its bandwidth, and the performance of the element-wise remote read version is degraded by the overhead of context-switching for multithreading.

EM-X is a highly parallel computer with a distributed memory. It supports fine-grain communication, whose size is two-word fixed, on an instruction execution pipeline. It achieves high communication throughput by overlapping remote memory access with thread execution, and tolerates communication latency by rapid switching of threads. We developed an 80 processor system of EM-X, and are evaluating its architectural features on the system. In this paper, we execute radix sort programs to evaluate the parallel performance of EM-X and compare the results with other parallel computers. The resul...

In this paper, we describe the parallelization of a sparse matrix computation, CG (Conjugate Gradient method) kernel taken from NAS parallel benchmark suite, for the EM-X multiprocessor. Dataflow mechanism of EM-X supports fine-grain communication very efficiently, which provides low latency communication, and flexible message-passing facility. We compare the performance of sparse matrix vector multiplications by the complete exchange communication, by element-wise remote update and by the element-wise remote read with multithreading. The measurements taken on the EM-X indicates effectivene...

This paper explains how to use the Unlimited Speculative Execution scheme to accelerate the information retrieval on the World Wide Web. The Unlimited Speculative Execution scheme utilizes low loaded processors to speculate the tasks which are not decided to be initiated. The goal of this research is to present a fast WWW information retrieval system by using the Unlimited Speculative Execution scheme. We use the EM-X parallel computer which consists of 80 processors for the platform.

Sparse matrix problems require a communication paradigm different from those used in conventional distributed-memory multiprocessors. We present in this gaper how fine-grain communication can help obtain high performance in the experimental distributed-memory multiprocessor, EM-X, developed at ETL, which can handle fine-grain communication very efficiently. The sparse matrix: kernel, Conjugate Gradient, is selected for the experiments. Among the steps in CG is the sparse matrix vector multiplications we focus on in the study. Some communication methods are developed for performance comparison, including coarse-grain and fine-grain implementations, Fine-grain communication allows exact data access in an unstructured problem to reduce the amount of communication. While CG presents bottlenecks in terms of a large number of fine-grain remote reads, the multi-thraded principles of execution is so designed to tolerate such latency. Experimental results indicate that the performance of fine-grain read implementation is comparable to that of coarse-grain implementation on 64 processors. The results demonstrate that fine-grain communication can be a viable and efficient approach to unstructured sparse matrix problems on large-scale distributed-memory multiprocessors.

Multithreading aims to tolerate latency by overlapping communication with computation. This report explicates the multithreading capabilities of the EM-X distributed-memory multiprocessor through empirical studies. The EM-X provides hardware supports for fine-grain multithreading, including a by-passing mechanism for direct remote reads and writes, hardware FIFO thread scheduling, and dedicated instructions for generating fixed-sized communication packets. Bitonic sorting and Fast Fourier Transform are selected for experiments. Parameters that characterize the performance of multithreading are investigated, including the number of threads, the number of thread switches, the run length, and the number of remote reads. Experimental results indicate that the best communication performance occurs when the number of threads is two to four. FFT yielded over 95% overlapping due to a large amount of computation and communication parallelism across threads. Even in the absence of thread computation parallelism, multithreading helps overlap over 35% of the communication time for bitonic sorting.

Communication latency is central to multiprocessor design. This study presents the design principles of the EM-X distributed-memory multiprocessor towards tolerating communication latency. The EM-X overlaps computation with communication for latency tolerance by multithreading. In particular, we present two types of hardware support for remote memory access: (1) priority-based packet scheduling for thread invocation, and (2) direct remote memory access. The prioritybased scheduling policy extends a FIFO ordered thread invocation policy to adopt to different computational needs. The direct remote memory access is designed to overlap remote memory operations with thread execution. The 80-processor prototype of EM-X is developed and is operational since December 1995. We execute several programs on the machine and evaluate how the EM-X effectively overlaps computation with communication toward tolerating communication latency for high performance parallel computing.

In this paper, we discuss an implementation of the LINPACK benchmark parallelized on the EM-X multiprocessor and evaluate its performance focusing the floating point operations in which a regular repetitive pattern occurs. It is important to overlap the communication and calculation as much as relationship between the broadcast algorithms and load balancing. Exploiting the potential of a reduction of the number or memory accesses and adopting the multi-column simultaneous elimination technique, we also further accelerated the most innerloop code we had already reported for optimization on a...

Communication latency is central to multiprocessor design. This study presents the design principles of the EM-X distributed-memory multiprocessor towards tolerating communication latency. The EM-X overlaps computation with communication for latency tolerance by multithreading. In particular, we present two types of hardware support for remote memory access: (1) priority-based packet scheduling for thread invocation, and (2) direct remote memory access. The priority-based scheduling policy extends a FIFO ordered thread invocation policy to adopt to different computational needs. The direct remote memory access is designed to overlap remote memory operations with thread execution. The 80-processor prototype of EM-X is developed and is operational since December 1995. We execute several programs on the machine and evaluate how the EM-X effectively overlaps computation with communication toward tolerating communication latency for high performance parallel computing.

投機的実行(Speculative Execution)に関して,94年〜95年7月のサーベイを報告すると共に,我々が提案しているタスク間投機的実行の有効性を示す.なお,94年までの調査については,文献[2]を参照していただきたい.調査対象とした論文を表1に示し,近年の投機的実行に関する論文数の推移を図1に示す.図1に示すように,VLIWやSuperscalarが出始めた91年頃から投機的実行に関する論文が急増している.これらの研究は,(1)プログラムに内在する命令レベルの並列性調査,(2)Superscalar/VLIWでの投機的実行,(3)並列計算機での投機的実行に分類される.90年代前半は(1)に関する論文が多かったが,その後,(2)に関する論文が急増し,94-95年の論文はその中でも,分岐予測(branch prediction)と条件付実行(predicated execution)に関するものが全体の7割を占め,89-93年に多かったアーキテクチャ上の実現方法に関する論文が激減した.本報告では,現在最もホットな話題となっている分岐予測と条件付実行を中心に説明する.

This paper discusses how to decrease the control overhead of tasks with Speculation on multiprocessors. Firstly, we have implemented the unlimited speculative execution on the EM-4 multiprocessor. Secondly, the overhead is classified into its several sources. After measuring each classified overhead, it has been confirmed that both the broadcast latency and the overhead initiating tasks are not major factors. Insted, the overhead of receiving and manipulating broadcasted control data is major factor. When the factor is decreased by 1/4, the speedup ratio increases up to 3 and we will have 1...

In this paper, we describe the parallelization of a sparse matrix computation, CG (Conjugate Gradient method) kernel taken from NAS parallel benchmark suite, for the EM-X multiprocessor. EM-X is a distributed-memory multiprocessor. Dataflow mechanism of EM-X supports fine-grain communication very efficiently, which provides low latency communication, and flexible message-passing with direct remote memory access. We compare the performance of sparse matrix vector multiplications by the complete exchange communication and by the element-wise remote memory access with multithreading. The measu...

The purpose of this paper is to propose a new fast control scheme of macrotasks with speculation. A macrotask is a coarse grain task which is a unit of speculation. Previous works have reported that the speedup ratio is 12 to 630 times in comparison with conventional execution schems without speculation when both the speculation depth and the computational resource are infinite, that is called oracle model. The control overhead,however, prevents the speedup from attaining the theoretical speedup ratio. Thus, the control scheme with small overhead is desired. The distributed control scheme a...

The purpose of this paper is to propose a new fast execution scheme of FORTRAN programs. The proposed scheme enables the fast initiation of macrotask when its data dependences are satisfied even if the control flow has not been reached. The previous schemes to parallelize a program including conditional branches have a number of problems - 1) Though the theoretical speedup ratio is up to N when N conditional branches are jumped on either a VLIW or a superscalar machine, the number of N is restricted up to the number of ALU's on a chip, 2) Since conventional control schemes use a few processors to control macrotasks, the overhead to control them is large. The proposed scheme solves these problems - 1) The proposed scheme enables speculative execution between coarse grain tasks, i.e., macrotasks, on multiprocessors by jumping many conditional branches, 2) A distributed control scheme is proposed and implemented on the EM-4 multiprocessor to decrease the control overhead of macrotasks. Preliminary evaluations show that the control overhead of the proposed scheme is smaller than that of the other control schemes. Moreover, it is confirmed that the distributed control can be implemented by using software when the average macrotask execution time is larger than 14.4 (Is on the EM-4 multiprocessor.

This paper considers the high-speed execution of FORTRAN programs on parallel processing systems and proposes the parallelizing scheme of the program and execution based on the speculative execution over multiple conditional branches. Several techniques have been proposed that parallelize the program including conditional branches.
A method which does not use the speculative execution is: (1) the method called earliest execution condition determination. As the methods which use the speculative execution are: (2) speculative evaluation scheme for a single conditional branch for the superscalar processor or VLIW computer; and (3) multiple speculative execution scheme assuming particular loops.
There are the following problems: (1) sufficient parallelism is not extracted only by determining the earliest execution condition; (2) the speed improvement that can be realized by the speculative execution of a single conditional branch is at most twofold; and (3) the scheme can be applied only to particular loops.
This paper divides the program into macrotasks, and defines the multiple stage speculative execution scheme between macrotasks on the general parallel processing system. Then, the macrotask execution control for the individual macro-task is proposed, using the execution start condition, the control establishment condition and the execution stop condition.

Latency tolerance is essential in achieving high performance on parallel computers for remote function calls and fine-grained remote memory accesses. EM-X supports interprocessor communication on an execution pipeline with small and simple packets. It can create a packet in one cycle, and receive a packet from the network in the on-chip buffer without interruption. EM-X invokes threads on packet arrival, minimizing the overhead of thread switching. It can tolerate communication latency by using efficient multi-threading and optimizing packet flow of fine grain communication. EM-X also supports the synchronization of two operands, direct remote memory read/write operations and flexible packet scheduling with priority. This paper describes distinctive features of the EM-X architecture and reports the performance of small synthetic programs and larger more realistic programs.

Latency tolerance is essential in achieving high performance on parallel computers for remote function calls and fine-grained remote memory accesses. EM-X supports interprocessor communication on an execution pipeline with small and simple packets. It can create a packet in one cycle, and receive a packet from the network in the on-chip buffer without interruption. EM-X invokes threads on packet arrival, minimizing the overhead of thread switching. It can tolerate communication latency by using efficient multi-threading and optimizing packet flow of fine grain communication. EM-X also supports the synchronization of two operands, direct remote memory read/write operations and flexible packet scheduling with priority. This paper describes distinctive features of the EM-X architecture and reports the performance of small synthetic programs and larger more realistic programs.

従来, Doall型以外のループを並列計算機上で実行する方式としてDoacross[Cytr86]やPipelining[PaKL80]が提案されている. しかし, これらの方式は, 元々, 密結合型の並列計算機を対象としたものであり, メッセージ通信によりプロセッサ間のデータ交換を行う祖結合型の並列計算機では, 十分な処理性能を引き出すことができない. これは, 以下に述べる問題によるものである. ここで, ループの繰り返し回数をNとする. ・ Doacrossでは, プロセッサ間の通信ディレイが(N-l)回分, 全体の実行時間に加算されるため, が十分に小さくないと処理速度の向上が得られない. ・ Pipeliningでは, 各文の実行時問Tsが(N-l)回分, 全体の来行時間に加算されるため, Tsが十分に小さくないと処理速度の向上が得られない. 祖結合型の並列計算機では, メッゼージ通信によりプロセッサ間のデータ交換を行うため,を小さくすることが困難である. また, Tsには, 他のプロセッサ間でのデータの入出力時間が含まれるため, Tsを小さくすることも困難である. これに対して, 本報告で提案するループ間Doacrossは, プロセッサ問の通信ディレイが全体の実行時間に与える影響, 及び, 各文の実行時問Tsが全体の実行時間に与える影響を小さくする方式である. 本...

This paper discusses some of the design parameters for the network interface of a single chip processor EMC-Y to achieve high throughput and high performance. We are currently designing the EMC-Y, a processing element of a parallel computer EM-X. The design parameters include the arbitration method in the network switch, memory access priority and the size of internal FIFOs. To optimize parallel execution performance, we have examined the parameters of the network interface by using a register transfer level simulator of the EM-X.

The purpose of this paper is to evaluate a new fast execution scheme of a program with speculative execution on the EM-4 multiprocessor. Conventional Schemes to parallelize programs including conditional branches have some problems. The multi-stage specurative execution scheme enables -(1) solving the side-efects problem, (2) decreaseing the number of processors to execute the specurative execution scheme, (3) jumping multi-stage conditional branches, (4) suiting to general multiprocessor systems. An experimental evaluation shows that the measured speedup ratio is 50% of the theoretical rat...

疎行列を対象としたBLAS-3(Basic Linear Algebra Subrou-tine Leve13)を並列化し、富士通の分散メモリ型並列計算機AP1000上に実装した。BLAS-3は、次のサブルーチンで構成されている。・行列の積(GEMM,SYMM)・対称行列に対する階数kと2kの更新(SYRK,SYRK)・三角行列との積(TRMM)・右辺が複数列で、三角行列を係数に持つ連立一次方程式(TRSM)このうちTRSM以外の5つは、行列同士の積が主演算である。そのため、実装にあたって疎行列の積の並列化方法が重要になる。密行列の積の並列化と比較して、疎行列の積の並列化においては、次の点が問題になる。1.疎行列の積C⇽C+ABの計算においては、疎行列が圧縮されて格納されているためCの書き換えに時間がかかる。2.後巡する方法で行列をセルヘ分割した時、各セル(PE)の持つ部分行列の大きさに偏りがあるために、その格納に必要なメモリと通信量に偏りが生じる。そこで、本稿では1点を解決するための計算の実行順序について提案し、その計算順序で実行した場合における2の点を解決するための通信方法について提案する。さらに、提案した方法に基づいて実装したGEMM(非対称行列同士の積)ルーチンを用いて評価する。なお、疎行列は以下の条件で格納されているものとする。汎用的なプログラムとするた...

本報告では,DOACRCSS型ループの実行時間を最小にするデータ通信順序を求める.DOACROSS型ループ実行に関する従来の研究は,プロセッサの処理能力を表すパラメータとして演算命令の実行時間(以下,演算時間),及び,データ通信の遅延時間以下,通信遅延時間)を用いてきた.しかし,演算と通信を並列に処理できるマルチプロセッサ上で,DOACROSS型ループを実行する場合,これらのパラメータ以外に,通信ピッチを考慮いなくてはならない.通信ピッチは,プロセッサと相互結合網間のデータ入出力時間間隔である.通信ピッチがデータ通信の発生する時間間隔より大きい場合,通信が全体の実行時間の隘路となる.これは、データ通信が通信ピッチ以下の時間間隔で開始(以下,発行)できず,通信発行に遅延が生じるためである.この時,実際の実行時間は,従来の理論的な値よりも大きくなる.以下では,このような場合,データを定義順で他のプロセッサへ送らず,通信順序を変更することにより,実行智間を短縮できることを示す.

従来提案しているマクロタスク間先行評価方式におけるマクロタスク構成方法について報告する.先行評価方式とは,プログラム中の条件分岐文を越えて実行を進める方式である.マクロタスク生成の目的は,(1)変数の2重定義に件う副作用間題の回避,及び(2)仮実行(投棄的実行)に必要なプロセッサ数の削減の2点である.先行評価によって生じる副作用は,先行評価中に,同一データに対する2重定義が行われることによって生じる,本稿では,2重定義を回避するために,各マクロタスクヘのデータ依存間係が制御によらず一意になるようにマクロタスクを構成する.次に,実行時のプロセッサ数を削減するため,マクロタスク生成においては,データ依存と制御依存の間係を用いて,マクロタスクを融合した場合も,先行評価の効果を失わない部分を1つのマクロタスクとする.これは,従来のマクロタスク生成手法が制御依存のみを考えていたのに対し,データ依存を考えた生成手法として新規性を持つ.

This paper modifies a flow‐executing scheme of the color‐reuse type, using multiple initial loop control packets, and then proves that the flow‐executing scheme is best suited for executing DOACROSS loops on dynamic dataflow machines. Flow‐executing schemes can be divided into four categories: (1) those using a single initial loop control packet
(2) those using multiple initial loop packets
(a) the color overflow type
and (b) the color reuse type. Then the flow‐executing scheme can be classified into Classes (1‐a), (1b), (2‐a), and (2‐b) through the combination of Categories (1), (2), (a), and (b). This paper suggests that Class (2‐b) is best suited for executing DOACROSS loops, as it extracts full parallelism from DOACROSS loops, no sychronization overhead exists, and no memory access overhead exists after the synchronization. Copyright © 1993 Wiley Periodicals, Inc., A Wiley Company

はれだすは超並列化マルチアーキテクチャコンパイラの開発を目的とした開発環境である。本稿では、はれだすの内部表現とその上での先行評価表現方法について述べる。超並列化のための1つのアプローチとして、先行評価により既存言語中に陰に含まれる並列性を抽出する方法がある。先行評価とはプログラム中の制御依存関係を変更することにより、データ依存関係以外の先行制約関係を排除する高速化手法である。しかし、従来の先行評価では、命令レベルスケジューリングにおける並列性不足の補助手段としてしか実現されていない。はれだすでは、内部表現レベルで汎用的に先行評価を扱うことができるため、先行評価により引き出し得る並列性を有効に利用することが可能となる。本稿では、この内部表現による先行評価の表現方法について述べる。まず第2節においてはれだすの構成を述べる。続く第3節で、内部表現の構成と特徴について説明したのち、第4節で先行評価の表現方法とその操作方法について詳説する。

本稿では、マルチアーキテクチャコンパイラ開発環境-はれだす-におけるループ間依存関係の記述方法とその適用例について述べる。従来、プログラム中におけるデータ依存関係を特徴付ける方法して依存ベクトルが用いられている。しかし、この依存ベクトルは、同一ループ内あるいはループ外におけるデータ依存関係を記述するものであり、ループ間のデータ依存関係を特徴付けるための一般的な記述方法は定義されていなかった。これに対して本稿では、ループ間依存ベクトルを定義し、ループ間のデータ依存関係を記述する方法について述べる。また、ループ間依存ベクトルを用いることにより、ループ融合可能判定が従来手法に比べて容易に行えることを示し、さらに、各ループの並列性を失うことなくループを融合するためのループ間依存ベクトルの適用法について述べる。

本報告では、先行評価を用いたマクロタスクの多段仮実行方式におけるマクロタスクの効果的な制御手法として、マクロタスクの分散制御手法を提案する。多段仮実行方式は、プログラム中のデータ依存と制御依存の内、データ依存を保証した段階でマクロタスクと呼ぶタスクの実行を開始し、後で制御依存に基づいて制御確定したマクロタスクを選択する手法である。本方式を実際のマルチプロセッサ上で実現するにあたっての問題点は、実行時に発生する各種オーバヘッドの削減である。実行時のオーバヘッドには、制御が確定しない段階で実行を開始することにより発生する(1)メモリバンド幅の増大に起因するオーバヘッド、(2)多数のマクロタスクを制御するために発生する制御オーバヘッドがある。本稿では、これら2つのオーバヘッドの内、(2)のオーバヘッドを削減するための手法として、プロセッサにマクロタスク制御専用のハードウェアを付加し、集中制御を廃したマクロタスクの制御手法を提案する。(1)の問題は、マクロタスクのスケジューリング問題であり、今後の課題である。

本稿では、多重ループの最適なベクトル化を実現するために、(1)内側ループからのタイト化、(2)積極的なループ分割、という2つの解析方針に基づくベクトル化手法を提案する。従来の多重ループのベクトル化手法では、(1)外側ループからタイト化するためループ分割が十分できない、(2)ループ分割による損得の評価が不完全である、という問題があり、最適なベクトル化ができない。そこで、本稿ではこれらの問題を解決するための解析手法を提案するとともに、実機(富士通のVP220O)において本手法を定量的に評価する。

本稿では,マルチプロセツサシステムにおける,タスク一段の先行評価の制御(一段先行評価制御)と,タスク多段に渡る先行評価の制御(多段先行評価制御)との違いについて述べる.我々は,一投先行評価制御,及び,多段先行評価制御を具体的なマルチプロセッサシステム(並列処理システム-晴-)に沿って提案してきた.本稿では,一段先行評価制御,及び,多段先行評価制御を時相論理で表現し一般化する.その後,この時相論理を用いて,制御の違いを推論する,また,この推論によって,我々が提案してきた具体的なマルチプロセッサシステムに沿った一段先行評価制御,及び,多段先行評価制御の正当性を述べる.

本報告では,FORTRANプログラムをマルチプロセッサ上で高速に実行するための方式として,先行評価を用いたプログラムの並列化手法と実行方式を提案する.従来,条件分岐を含むプログラムを並列化する手法として,タスクの最速実行条件を求める手法や制御依存を越えた実行方式が提案されている.しかし,(1)最速実行条件を求めるだけでは十分な並列性が得られない,(2)対象プログラムが限定され,かつ,実行方式の提案がないといった問題を持つ.これらの問題に対して我々は,フローグラフ展開を用いた仮実行方式,データ駆動を用いた条件分岐のn段先行評価制御方式を提案している.本稿では,これらの手法を一般化すると共に,理論的な速度向上について論じる.

The purpose of this paper is to propose and evaluate a new scheme, called the Preceding Activation Scheme with Graph Unfolding, which translates a FORTRAN program into a dataflow graph and executes it efficiency. The problems in restructuring a FORTRAN program into a dataflow graph is that a FORTRAN program has an explicit control flow, which results in little parallelism because many gate-operations, such as T/F gates, are introduced in the dataflow graph to synchronize the data mevement. Thus, discarding these gate-operations is the key to expose parallelism from a FORTRAN program, which is the main purpose of the proposed scheme. In the software simulation, it is shown that the execution speed with the proposed scheme for flow graphs without backward branches is about 1.5 times as fast as that of the pure dataflow computer. Moreover, the execution speed is 2.7 times as fast as that of the pure dataflow computer if a flow graph including backward branches is unfolded by the proposed scheme.

本報告では,プログラム内の条件分岐を並列処理することによるプログラム実行時間の短縮について述べ,我々の提案している並列処理システム-晴-上での条件分岐並列処理手法の性能予測を示す.プログラム中の条件分岐を並列処理しようという試みは,VLIW型計算機を中心にこれまでに数多く行われている.しかし,これらの方式は,大規模な並列処理計算機を対象とした方式ではないため,条件分岐の先行評価段数が小さく,得られる並列性も小さい.これに対して,-晴-は1000台規模の要素プロセッサを持つため,先行評価段数を大きくし,十分な並列性をプログラムから抽出する.先行評価段数を大きくする手法として,我々はこれまでにフローグラフ展開を提案している.フローグラフ展開とは,条件分岐点における同期をとらず,条件の成立・不成立によって分かれる全ての制御フローについて演算を同時に実行し,後で制御に基づいて有効となったフローを選択する手法である.これまでの評価では,フローグラフ展開の対象となる部分について,1.5倍-5.2倍の処理速度の向上を確認している.本稿では,まず,(1)条件分岐の並列処理による処理速度向上をいくつかの科学技術計算プログラムのシミュレーション結果を用いて示し,次に(2)フローグラフ展開による処理速度の向上が,プログラム全体として考えた時に,どの程度期待できるかについて評価した結果を示す.

本報告では、並列処理システム-晴-における仮実行時の要素プロセッサ(PE)内の制御方法について述べる。仮実行方式とは、プログラムの並列実行を妨げる原因の一つである制御依存を超えてeagar evaluationを行う方式である。従来のパイプラインプロセッサ等のeagar evaluationは、単一プロセッサ内で行われていたためその範囲が小規模であった。-晴-では、仮実行を複数プロセッサを用い、多段にわたってeagar evaluationを行う。ここで問題となるのは分岐が決定した際の、複数PE間にわたるPEの制御方法である。制御を一箇所で集中的に行うと1000台規模のプロセッサではオーバヘッドが無視できない。そこで、我々は実行制御をPE毎に分散して行う方式を提案している。本報告では、まず仮実行の単位としてActivation Setという制御単位を定義する。次に、Activation Setを用いた仮実行時のPE毎に独立した制御方法について、その概要を述べる。さらに、PE内での具体的な処理手順を示す。

This paper considers the dataflow program development environment for the system programmer who develops the compiler and proposes a method to improve the debugging efficiency. The conventional debugging methods are either: (1) to monitor the packet in the dataflow ring, or (2) to specify the function containing a bug. The former contains unsolved problems such as the determination of start timing for the data monitoring and the presentation of a large amount of information to the user. The latter contains a problem in that the debugging is impossible at the dataflow level. This paper aims at the solution of those problems, and the detailed debugging is executed on the software, not on the real machine. The information presentation on a dataflow graph is considered for systematic presentation of the debugging information. As the development environment, the parallel processing system Harray proposed by the authors is considered. In the proposed system, a two‐stage process is employed in which the first step is to specify the macro‐block (which is a task unit in Harray) containing the bug, and the second step is the detailed debugging of the specified macro‐block. The debugging within the macroblock is executed on the software, and the debugging efficiency is improved by: (1) diagram representation for easier visual recognition, and (2) backward tracing function. Copyright © 1991 Wiley Periodicals, Inc., A Wiley Company

The parallel processing system -Harray- for scientific computations is introduced. The special features of the -Harray- system described are (1) the Controlled Dataflow (CD flow) mechanism, (2) the preceding activation scheme with graph unfolding, and (3) the visual environment for dataflow program development. The CD flow mechanism, controlling the sequence of execution in two levels-dataflow execution in each processor and control flow execution between processors-is adapted in the -Harray- system. Though dataflow computers are expected to extract parallelism fully from a program, they have many problems, such as the difficulty of controlling the sequence of execution. To solve these problems, the CD flow mechanism is adopted. The preceding activation scheme makes it possible to bypass control dependencies in a program, such as IF-GOTO statements which decrease the parallelism in a program. The flow graph of a program is unfolded to decrease the control dependency and to increase the parallelism. The visual environment helps programmers in the writing and debugging of a dataflow program. The environment consists of a graphical editor of a dataflow graph, and a debugger. These special features of the -Harray- system and its execution mechanism are described. © 1990.

本稿では、並列処理システム-晴-[1]におけるカラー管理方式の一提案を行なう。-晴-では、マクロブロック[1]という処理単位内で動的データ駆動方式を採用している。動的データ駆動方式ではループの処理にカラーを用いる。しかし、カラーは有限であるため、カラーの資源管理が必要となる。カラーの資源管理、即ち、カラーの回収・再割当に関して従来の方式では、「カラーのオーバフロー時に新しいループを生成する方法」が提案されている[2]。しかしながら、ループ生成のオーバヘッドが大きいという問題を持つ。また、計算機資源は有限であるから、計算機資源以上のカラーを用いても、処理速度向上は望めない。即ち、計算機資源に見合ったカラーを使用すれば良い。これらの点をふまえて、本稿では、必要以上のカラーを使用せず、カラーの回収・再割当のオーバヘッドを削減したループ処理方式を提案する。以下では、まず、ループ本体に対しデータフロー解析を行ない、カラーの必要個数(Lで表わす)を求める。そして、カラーのオーバフローを回避し、Lで制限されたカラーを回収・再割当するループ処理方式を示す。なお、今回はLが計算機資源以下の場合について報告する。

我々は,科学技術計算用並列処理システム-晴-(-HARRAY-:IIybrid ARRAY)を提案している).-晴-は,科学技術計算用にF0RTRANで記述されたプログラムを高速に実行することを目的とし,要素プロセッサを1024個持つ並列処理システムである.-晴-の実行方式は,プログラムをコンパイル時にマクロブロックという単位に分割し,マクロブロック間をコントロールフロー,マクロブロック内をデータフローで処理を行うCDフロー方式である.データフローのプログラムでは,後述するゲート後置を行うと,計算機資源が無限にあると仮定したとき,実行速度が約3倍向上することを確認している.しかし,計算機資源は有限であるため,-晴-では,プログラムの並列度が計算機資源よりも小さい部分でゲート後置を行い,この部分の実行速度を向上させる.しかし,制御ゲートが実行時エラーを回避させるために設けられているとき,ゲート後置を行うと,その先行評価部分で,ゲート後置が原因の実行時エラーが発生する場合がある.この実行時エラーは,ユーザのプログラムの誤りが原因でないため,ユーザに報告することはできない.したがって,ゲート後置が原因となりえる実行時エラーが発生したとき,その発生原因がゲー置であるのかプログラムの誤りであるのかを判断する必要がある.本稿では,ゲート後置が原因となりえる実行時エラーが発生したとき,その...

本稿では,並列処理システム-晴-〔1〕における構造体処理方式〔2〕の実現方法について述べる.-晴-では,実行方式にCDフロー(Controlled Dataflow)方式〔3〕を採用している.CDフロー方式では,マクロブロックと呼ぶ処理単位間でコントロールフロー制御をおこない,マクロブロック内でデータフロー実行をおこなう.データフロー実行には記憶の概念が存在しないが,実際に計算機を構成するにあたっては,大規模な構造体を格納するための構造体記憶が必要不可欠である.従来,構造体処理に関してI-ストラクチャ〔4〕等が提案されている.しかし,これらの方式はデータフロー方式の持つ単一代入則を厳密に実現したものであって,参照は複数回できるが,定義は1回のみという制限を持つ.したがって,二重定義時には,構造体をコピーしなければならず,オーバヘッドが発生する.-晴-では,構造体記憶(以下大域記憶と呼ぶ)に対して複数回の定義及び参照を可能とし,二重定義時のコピーオーバヘッドを無くした構造体処理方式を提案している〔2〕.本方式では,アクセス順序の保証を複数マクロブロックに及ぶ定義・参照に対しておこない,マクロブロック内に閉じた定義・参照は対象としない.これは,マクロブロック内で定義されたデータを同一マクロブロック内で使用する場合には,定義されたデータをらである.本稿では,まず-晴-の大域記憶及び...

The purpose of this work is to propose and evaluate the preceding activation scheme with graph unfolding, which translate a Fortran program into a dataflow graph and executes it efficiently. The problems in restructuring a Fortran program into a dataflow graph are that a Fortran program is not written in a single assignment rule and it has an explicit control flow. These problems result in little parallelism because many gate operations, such as T/F gates, are introduced in the dataflow graph to synchronize the data movement. Therefore, discarding these gate operations is the key to exposing parallelism in a Fortran program. The preceding activation scheme with graph unfolding is proposed to discard these gate operations. The result of the performance evaluation by the 'Harray' software simulator is presented. It is shown that the execution speed with the proposed scheme for flow graphs without backward branches is about 1.5 times as fast as that with the extended activation scheme which initiates the execution only after it is confirmed that a basic block will be selected at a conditional branch. Moreover, the execution speed is 2.7 times as fast as that with the extended activation scheme if a flow graph including backward branches is unfolded by the proposed scheme.

我々は、主に科学技術計算を目的とした並列処理システム-晴-を提案している。-晴-では、プログラムに内在する並列性を十分に引き出す為にデータフロー実行を取り入れている。データフロー実行では、ノードの発火制御を司る待ち合わせ記憶(WM:Waiting Memory)の高速化がシステム全体の高速化において重要なポイントとなる。本稿では、-晴-の試作機で用いる待ち合わせ記憶WMの構成について述べると共に、ソフトウェアシミュレータによる簡単な評価を行う。

我々が提案している科学技術計算処理用データフロー・マルチプロセッサシステム-晴-では、各プロセッサエレメントへ割り当てるタスクの分割にマクロブロックという概念を用いている。マクロブロックとはプログラムをある基準に従って図1のように分割したもので、-晴-ではマクロブロックを単位としてプロセッサエレメントにタスクを割り当てる。マクロブロック内部ではデータ駆動制御で計算を進めて自然に並列性を抽出し、さらにマクロブロック間にコントロールフロー制御を導入し階層的な制御構造をとる。このような方法により、制御命令の増加などのデータ駆動制御の欠点を補うことができる。しかし、マクロブロックを単位としてタスクを割当てる際に種々の問題が生じる。マクロブロックの終了検出を高速に行なう必要があることもその一つである。そこで、本稿ではマクロブロックの終了検出を高速に行なう手法について述べ、簡単な評価を行なう。

Parallel processing with an ordinary sequential language is important from a point of a view of its simplicity and the effective utilization of existing software. This paper reports an experience gained by using Parafrase, a restructuring compiler developed by University of Illinois.