Point of Interest (POI) recommendation systems exploit information in location-based social networks to predict locations that users may be interested in. POI recommendations have been widely adopted in many applications, which are helpful for daily life. POI recommendation services receive a huge volume of visit history data generated by users' daily lives with mobile devices. However, POI recommendation systems require long time to build a model from such a huge volume of check-in data and recommend suitable POIs to users. Thus, it is indispensable to shorten the execution time in a big data era. In this study, we propose a clustering-based method to divide the data into multiple subsets to accelerate the POI recommendation's execution while maintaining accuracy. Our proposed method can be adapted to any general POI recommendation algorithm. We divide the whole data, that is, users and POIs, into subsets with a tree structure to balance the size of subsets according to both geographical information and user check-in distribution. Evaluation results show that we successfully accelerate the base algorithms over 17 to 39 times faster while keeping the accuracy almost the same.

Various algorithms and models have been proposed to address text classification tasks; however, they rarely consider incorporating the additional knowledge hidden in class labels. We argue that hidden information in class labels leads to better classification accuracy. In this study, instead of encoding the labels into numerical values, we incorporated the knowledge in the labels into the original model without changing the model architecture. We combined the output of an original classification model with the relatedness calculated based on the embeddings of a sequence and a keyword set. A keyword set is a word set to represent knowledge in the labels. Usually, it is generated from the classes while it could also be customized by the users. The experimental results show that our proposed method achieved statistically significant improvements in text classification tasks. The source code and experimental details of this study can be found on Github(1).

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.

The realization of edge-based cyber-physical systems (CPS) poses important challenges in terms of performance, robustness, security, etc. This paper examines a novel approach to providing a user-centric adaptive route planning service over a network of Road Side Units (RSUs) in smart cities. The key idea is to adaptively select routing task parameters such as privacy-cloaked area sizes and number of retained intersections to balance processing time, privacy protection level, and route accuracy for privacy-augmented distributed route search while also handling per-query user preferences. This is formulated as an optimization problem with a set of parameters giving the best result for a set of queries given system constraints. Processing Throughput, Privacy Protection, and Travel Time Accuracy were developed as the objective functions to be balanced. A Multi-Objective Genetic Algorithm based technique (NSGA-II) is applied to recover a feasible solution. The performance of this approach was then evaluated using traffic data from Osaka, Japan. Results show good performance of the approach in balancing the aforementioned objectives based on user preferences.

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.

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).

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).

医薬品や遺伝子などの機密性の高いデータに対する各種処理をクラウドなどの第三者のサーバ上で行う場合，第三者のサーバからの機密情報漏洩が懸念される．解決策として，機密情報そのものではなく匿名化したデータを第三者のサーバに保存し各種処理を行う方法が考えられるが，医療分野など，処理の正確性が求められる分野では匿名化を採用することが困難である．この問題を解決するため，本稿では，完全準同型暗号（FHE: Fully Homomorphic Encryption）を用いてデータを秘匿した状態で各種処理を行うことを考える．そして，各種処理の対象として頻出パターンマイニングを取り上げる．FHEを用いた各種処理を行ううえでの問題は，膨大な時間・空間計算量を要する点である．FHEの頻出パターンマイニング手法への適用例としては，Aprioriアルゴリズムを対象としたLiuらのP3CCがあるが，やはり膨大な時間・空間計算量を要する．これに対して本稿では，1) 暗号文パッキングによる暗号文数の削減，および2) 暗号文キャッシングによるサポート値計算の高速化によって，時間・空間計算量を削減する手法を提案する．実験評価では，10,000トランザクションのデータセットにおいて，P3CCの430倍の高速化と94.7%のメモリ使用量削減を達成した．Private information disclosure from a third-party is concerned as a security risk, while processing highly confidential data such as medicines and genes on the third-party as a cloud server. Although there is a solution that stores and processes the data anonymized from private information on the third-party's server, it is difficult to apply anonymizing techniques to application fields such as a medical field which requires accurate processing. To address this issue, we will perform the processing with concealed data by Fully Homomorphic Encryption (FHE). In addition, we will adopt frequent pattern mining as a processing object. The problem of the processing with FHE is both huge time complexity and space complexity. P3CC by Liu et al. is the first proposed application of FHE for frequent pattern mining, which targets Apriori algorithm and has these particular problems. In this paper, we propose an Apriori based mining method with smaller time and space complexities than P3CC, by adopting two techniques: 1) ciphertext packing that reduces the number of ciphertexts, and 2) ciphertext caching that enables to speed up the support-counting. 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.

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.

世界でビッグデータ関連の研究への投資が加速している．本稿では，2012年から始まった米国のビッグデータイニシアティブと，2014年から始まったEUのHorizon 2020でのビッグデータ関連研究開発について，コンテンツ処理技術に関わる基盤的なプログラムを中心に紹介する．米国の研究事例としては，UCBのAMPプログラム，28組織により実施されているXDATAプログラムを紹介する．EUでの研究事例としては，中小企業のオープンデータ利活用を促進するインキュベーションの役割を担うODINEや，柔軟なデータ保存・忘却の制御を可能とするForgetItを紹介する．

Twitter, as one of the popular social network services, is now widely used to query public opinions. In this paper, tweets, along with the reviews collected from review websites are used to carry out sentimental analysis, so as to figure out the language-based and location-based effects on user evaluations for six global restaurants. The language expansion is carried out that 34 languages are taken into account. By using a range of new and standard features, a series of classifiers are trained and applied in the later steps of sentiment analysis. Our experimental results show that the location and language effects on user evaluations for restaurants actually exist.

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.

紙に印刷されたドキュメント上にペンで情報を書き込む手書きアノテーションは，情報付加や強調を目的に広く用いられている．一方，コンピュータ上での電子ドキュメントに対して手書きアノテーションを行う際には，アノテーション情報を活用した検索や共有といった可用性の向上が課題となる．この課題を解決するうえで，アノテーション対象として選択されたドキュメント中の箇所の推定が求められるが，従来提案されている経験的な推定手法では手書きアノテーションにおける人間特有の傾向が考慮されないため，十分な認識精度を得られない．そこで本研究では人間の手書きアノテーション傾向に基づいた範囲選択手書きアノテーションを認識するモデルを提案する．本提案モデルでは下線や囲い込み，縦線といった一般的な範囲選択アノテーションの検出に加え，筆記者の意図する選択範囲抽出を実現する．認識精度評価の結果，文字単位での選択では平均85%，行単位での選択では平均91%の精度を達成可能であることを確認した．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クローラは，クローリング済みURLの検出やWebサーバに対する連続アクセス防止といった処理を実行しながらデータ収集を行う必要がある．Web空間に存在する大量のURLに対して高速な収集を実現するために並列分散クローリングが求められるが，省資源でのクローリングを行うためにも，処理の時間計算量と空間計算量の削減に加え，計算機間の負荷分散も必要である．本論文で提案するWebクローラは，クローリング処理をProducer-Consumer型のモジュール群で実行することにより，これまでの被クロールWebサイト単位での負荷分散でなく，Webクローラを構成するモジュール単位での負荷分散を実現する．つまり，Webクローラを構成する各モジュールが必要とする計算機資源に応じた分散処理が可能になり，計算機間での計算負荷やメモリ使用量の偏りを改善することができる．また，ホスト名やURLを管理するモジュールは時間計算量と空間計算量に優れたデータ構造を利用して構成されており，大規模なクローリングが省資源で可能になる．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.

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.

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.

近年のウェブサーチエンジンは,その検索結果ページに様々な情報ソースからの検索結果を統合して表示する。統合される情報ソースは,ウェブページだけではなく,ニュース記事,ブログ記事,画像,動画,Twitterなどのリアルタイム情報などである。しかし,こうした様々な情報ソースからの検索結果は常に表示されるわけではない。ウェブサーチエンジンは,どのクエリに対して,どの情報ソースを対象に検索し,どの検索結果を統合すべきかを判断している。本稿では,こうしたウェブサーチエンジンにおける統合検索で用いられている技術とその評価手法を紹介すると共に,統合検索の今後について述べる。

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.

データベースの幅広い普及により,更新トランザクションを多用するアプリケーションが増えている.更新トランザクションは,高価な高可用サーバで処理する必要があるため,スケールアップが求められる.そのためには,複数のトランザクションを一つのトランザクションとして処理するグループコミットが有効である.しかし,グループコミットを利用するには,アプリケーションの修正が必要で,既存のアプリケーションに適用することができなかった.本論文では,トランザクション処理内容の事前知識や,アプリケーションの修正を必要とせず,ミドルウェア内でグループコミットを行う手法を提案する.アプリケーションの修正を行わない場合,グループコミットの対象とするトランザクション集を特定し,バッチ更新をスケジュールする必要がある.本手法では,トランザクションの実行履歴をもとに,トランザクション中の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.

GCLOCKに基づくロックフリーなページ置換アルゴリズムNb-GCLOCKを提案する.バッファ管理モジュールへの並行アクセスは,CPUのプロセッサ数に対するデータベースのスケーラビリティを阻害する主要な要因である.本論文では,Nb-GCLOCKと無待機ハッシュ表の組合せにより,要求されたページをバッファフレームに固定するbufferfix処理をノンブロッキングに行う手法を提案する.実験結果により,既存のロックに基づくバッファ管理手法が16プロセッサ以上,プロセッサ数に対するスケーラビリティを示さないのに対して,我々の手法が64プロセッサまでほぼ線形のスケーラビリティを示すことを明らかにし,提案手法の有効性を示す.

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.

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.

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/.

データマイニング分野での頻出アイテムセット抽出手法は, 最小サポート値を与えて, 最小サポート値以上のサポート値を持つアイテムセットを抽出する手法である.与えられる最小サポート値から抽出される頻出アイテムセット数を予測することは困難であることから, 最小サポート値を必要とせず, 頻出上位数κを指定して, サポート値降順にκアイテムセットを抽出するTop-κ Miningコンセプトが近年提案されている.しかし, Top-κ Miningコンセプトも閾値としてκを指定する必要があり, ユーザはマイニングプロセス開始時に, 解析に必要なアイテムセット数を予測しなければならない.本稿では, 最小サポート値や閾値をユーザが指定する必要のない頻出アイテムセット抽出法としてTF^2P-growthアルゴリズムを提案する.TF^2P-growthは, 短時間でサポート値降順にアイテムセットを抽出しユーザに返すアルゴリズムである.

命令間の制御依存によってパイプライン処理を滞らせないために,近年のプロセッサでは,分岐予測が採用されている.分岐予測によって未解決の分岐命令を投機的実行することが可能となる.しかし,近年,命令パイプライン長の深化により,分岐予測ミスペナルティが増大している.そのため,分岐予測ミス率の低減は,プロセッサの性能向上のために不可避な課題となっている.分岐予測は,分岐条件の成立・不成立の予測と分岐先アドレスの予測で構成される.分岐先アドレス予測に利用される分岐先アドレスバッファ(BTB: Branch Target Buffer)は,分岐条件が成立する(Taken)分岐をエントリに登録する.BTBのエントリに存在しない分岐の分岐条件成立・不成立状況を解析した結果,BTBにエントリを持たない分岐のほとんどが,分岐条件が成立しない(NotTaken)分岐であることが好かった.そこで,BTBにエントリを持たない分岐をNotTakenと予測する分岐予測手法を提案する.提案手法では,さらに,分波方向予測器のエントリ数削減により,競合を緩和するために,BTBにエントリのない分岐は,分岐方向予測器を更新しない.SimpleScalar 3.0c/PISA sim-bpredシミュレータで実験したところ,SPECint95 (train)では,8KB Gshare予測器で平均1.5%,1.5KB B...

今や検索エンジンは,インターネットを利用する上でなくてはならない存在となっている。しかし,そのアーキテクチャは明らかにされていない部分が多い。本稿では,世界最大の検索エンジンであるGoogleを例にとり,検索エンジンのアーキテクチャについて, Web情報の収集,インデックス化,検索の3つに焦点をあてて紹介する。また,大量の検索クエリーをどのように処理するかや,運用にはどの程度のコストがかかるのかなどの運用に関わる問題についても取り上げる。

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

本論文では,投機並列実行を行なうことにより逐次プログラムの自動的な並列実行を行なう中間コードインタプリ夕を構成する方法についての検討を行なう.次に,並列処理粒度を適切に制御するチェックポイント実行機能,検索/登録/排他制御のオーバヘッドを最小にして投機的メモリ操作を効率的に実現する手法など,効率的な投機並列実行を特別なハードウェアを用いずに実現するためのソフトウェア上の手法を提案する.そして,これらの方法を用いることによってどの程度の基本性能が得られるかを評価するために行なった実験の結果を示す.実験結果から,チェックポイント実行によって処理粒度を適切に設定すること,および,投機的メモリ操作の効率的な実現をはじめとする様々なソフトウェア上の工夫をほどこすことにより,特別なハードウェアを用いなくても,並列処理による速度向上効果の得られる,投機並列実行中間コードインクプリ夕を構成することが可能であることが確認された.

本論文では, 分散メモリ型並列計算機において, 同期・通信の支援機構が行列問題の並列処理性能に与える影響について議論し, それらが有効となる条件・要因を, モデルと実験によって定量的に明らかにする. LU分解法の代入部に現れる三角方程式の求解では, 互いに依存性のない計算要素がイテレーション間にまたがっており, その並列性はウェーブフロント状に抽出できる. この問題を, 並列性を自然に利用する細粒度アルゴリズムと, ブロック化による粗粒度アルゴリズムで表し, 並列計算機EM-XとAP1000+に実装した. 最初に予備実験によって, これらの計算機が持つ同期・通信機構の特徴をパラメータによって表した. 次に, アルゴリズムの性質をモデル化し, 通信オーバヘッドに起因する性能上限と, 並列度の制限による有効PE台数を理論的に示した. 問題サイズが小さい場合, あるいは十分なPE台数が利用できる場合は, 高い並列度が得られる細粒度アルゴリズムが有望である. ただし細粒度アルゴリズムで高い性能を得るには, 通信起動のオーバヘッドが十分小さいことが必要であり, EM-Xがこの要件を満たす. 逆に, 問題サイズが十分大きいか, 比較的少ないPE台数しか与えられない場合は粗粒度アルゴリズムの方が良い. この場合は通信性能より逐次演算性能が重要となり, AP1000+が優位性を示す.

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...

本論文では,マクロタスクと呼ぶタスクレベルでの投機的実行を並列計算機上で行うマクロタスク間投機的実行の効果的な制御手法として分散制御方式を提案する.一般に,投機的実行における理想的なモデル(Oracle Model)を仮定すると,投機的実行を行わない場合に比較して12〜630倍の速度向上が得られる.しかし,実際には,投機的実行時に発生する制御オーバヘッドのために,上記の理論性能に近づくのは難しく,制御オーバヘッドの小さい制御手法が必要とされる.本論文で提案する分散制御方式は,各マクロタスクが(1)自分の後続のマクロタスクを動的に生成すると共に,(2)システム全体に放送される制御情報を随時監視し各マクロタスク自身が次の状態を決定することにより実現される.これにより,マクロタスクの制御を並列化できると共に,マクロタスク制御オーバーヘッドがマクロタスク数に依存しなくなり,高速な投機的実行が可能となる.本方式を並列計算機EM-4上にインプリメントし,Boolean Recur

近年の分散共有メモリ型並列計算機は,プロセッサの処理と独立に非同期でデータ転送を行う機構を備え,プロセッサがデータ転送に忙殺されるのを防いでいる.また,プロセッサの高速化と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.