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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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