SketchSortとは全ペアー類似度検索(与えられたデータセットからすべての類似するデータペアーを発見する問題)を高速に解くためのソフトウェアーで、以前に論文とソフトウェアーを公開しました。 論文: Yasuo Tabei, Takeaki Uno, Masashi Sugiyama, Koji Tsu…
Githubからダウンロードできます。https://github.com/tb-yasu/pachaPACHAは、2つの化合物を入力として、それらの間のアライメント出力します。アルゴリズムは去年のISMB'15のプロシーディングスにて発表した内容です。Yoshihiro Yamanishi*, Yasuo Tabei*, …
8月13日から17日にサンフランシスコで開催されたKDD'16に参加しました。 よくも悪くもTutorialの日とWorkshopの日が分かれて2日になりました。 Research Trackはオーラル+ポスターとポスターのみの採択に分かれていて、採択数はそれぞれ70と72で採択率18%(=1…
8月9日と10日に国立情報学研究所で開催されたERATO感謝祭SeasonIIIで発表してきました。 感謝祭のURLは、https://bigdata.nii.ac.jp/eratokansyasai3/ です。ERATO感謝祭は様々なコンピュータサイエンス分野の有名国際会議に今年採択された論文の講演からな…
データマイニング分野のトップの国際会議KDD’16に以下の論文が採択されました.Y.Tabei, H.Saigo, Y.Yamanishi, S.J.Puglisi: Scalable partial least squares regression on grammar-compressed data matrices, accepted to KDD’16内容は, PLS回帰モデルの入…
文法圧縮上でのaccess、rank、select操作に関する論文が、アルゴリズム分野のトップ会議ESA2015に採択されました。Djamal Belazzougui, Patrick Cording, Simon J. Puglisi, Yasuo Tabei: Access, rank, and select in grammar-compressed strings, 23rd Eur…
様々な操作を高速にサポートするデータ圧縮法に関する論文を公開しました。本論文はデータ圧縮に関する国際会議 Data Compression Conference (DCC2015)に採択された論文でarXivから入手出来ます。Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski, Ju…
文法圧縮されたテキスト上でのrank/select/accessに関する論文を公開しました。ヘルシンキ大のDjamal BelazzouguiさんとSimon J. Puglisiさんとの共著論文です。arXivからダウンロードできます。Djamal Belazzougui, Simon J. Puglisi, Yasuo Tabei: Rank, s…
今年の実験的アルゴリズムに関する国際会議SEA2014に採択された論文をarxivにて公開しました。内容は文法圧縮の索引化に基づく高速クエリー検索です。Yoshimasa Takabatake, Yasuo Tabei, Hiroshi Sakamoto: Improved ESP-index: a practical self-index for…
東大で開催されたNIPS2013読み会で発表させていただきました. http://connpass.com/event/4728/参加者60人と大盛況で, 機械学習の人気の高さを再確認しました. 僕は, Scalable graph kernels for continuous attributesというタイトルの論文を発表しました. …
年が明けて2014年の1月ももう半分まで来てしまいましたが、調度良い時期ですので, 2013年の振り返り記事の代わりに2013年の文法圧縮の進展を振り返ってみたいと思います。はじめに文法圧縮を簡単におさらいすると, 文法圧縮とは入力となるテキストのみを表…
暑い日々が続きますが、いかがお過ごしでしょうか? 早いもので2013年もう8月ということでだいぶ遅いですが2013年の前半の成果を振り返ってみたいと思います。幸いにも2013年の前半に4本論文を出す事ができました。内分けは、データマイニング・機械学習1本…
以前のブログで紹介した簡潔マルチビット木のc++による実装 (Succinct Multibit Tree (SMBT)) を公開致しました。ソフトウェアーはgoogle codeからダウンロードすることができます。 http://code.google.com/p/smbt/SMBTは去年のWABIで発表した内容にもとづ…
SPIRE2012で発表したメモリー効率の良い文法圧縮のための可変長コードに関する論文を公開しました。 Y.Takabatake, Y.Tabei, H.Sakamoto: Variable-Length Codes for Space-Efficient Grammar-Based Compression, Symposium on String Processing and Inform…
大規模グラフ類似度検索のためのソフトウェアーgwtの内部で使われているwavelet木の実装をwavelet行列に変更しました。下のサイトからgwt-wm-3.0.0.tar.bz2をダウンロードできます。 http://code.google.com/p/gwt/gwtに関する説明は以前のブログ記事を参照…
8月6日,7日に北海道大学で開催された、機械学習とバイオインフォマティクスのワークショップMLAB2012にて研究発表を行いました。 http://www.cris.hokudai.ac.jp/takigawa/mlab2012/発表内容は大規模化合物フィンガープリントデータベースのための新しい簡潔…
2012-02-04の記事 http://d.hatena.ne.jp/tb_yasu/20120204 のESPによる文法圧縮の実装に関して問い合わせが数件ありましたのでソースコードを公開しました。今後のアップデートのしやすさを考慮してgithubにアップロードしました。 https://github.com/tb-y…
ALSIPの時に聴いて気になっていた文法圧縮法Edit Sensitive Parsing (ESP)を実装しました。文法圧縮とは、与えられた文章から曖昧でない文脈自由文法*1をもとめることにより圧縮する手法です。文脈自由文法のサイズは、導出規則の右辺の終端記号と非終端記号…
人工知能学会誌の私のブックマークに簡潔データ構造という題で記事を書きました。私のブックマークは研究者が自らの研究をする中で普段使っているWeb上のリソースを公開するための記事です。今までいろいろな研究者が記事を書かれています。 http://www.ai-g…
MinHashを用いたSketchSortの論文がMolecular Informaticsに採択されました。 論文は下のサイトからダウンロードすることができます。Yasuo Tabei and Koji Tsuda: SketchSort: Fast All Pairs Similarity Search for Large Databases of Molecular Fingerpr…
5月24日から27日に中国深センで開催されたPAKDD2011で、以前のブログで紹介した線形グラフのマイニングアルゴリズム(LGM: Linear Graph Miner)について発表しました。下はexcursionの写真.発表スライドをアップしました。 Lgm pakdd2011 public View mo…
昨日のブログで紹介した大規模グラフの類似度検索のC++による実装(gWT:graph-indexing wavelet tree*1 )を公開しました。googlecodeよりダウンロードすることができます。初めに、gWTはgwt-buildによりグラフデータベースの索引付けを行います。以下にサンプ…
4月28日から4月30日に開催されたデーターマイニングの国際会議 SIAM Conference on Data Mining (SDM2011)にてwavelet木を用いた大規模グラフデータベースの高速類似度検索手法について発表してきました。Yasuo Tabei and Koji Tsuda: Kernel-based Similari…
データマイニングの国際会議 PAKDD2011に線形グラフのマイニングアルゴリズムに関する論文がアクセプトされました。本研究は、PFIの岡野原さん(@hillbig)、産総研の廣瀬さん、津田さん(@kojitsuda)との共同研究です。 論文をarxiv.orgにアップしました。LGM:…
FM-indexのC++による実装 FM-index++を公開しました。http://code.google.com/p/fmindex-plus-plus/FM-index[1〜4]とは、圧縮全文索引の一種でO(n)時間とO(nlgσ)メモリー(n:テキスト長、σ:文字種類数)で構築することができます。最近では、テキスト処理ばか…
もぐりででている授業で紹介されていたカーネル法の本(OSじゃなくて)が出版されていたので読んでみました。カーネル法の本はいろいろ出版されていますが、この本独自の章は8章「平均による確率分布の特徴づけ」と9章「正定値カーネルによる依存性・独立性」…
東京工業大学の杉山研究室でSketchSort法に関する講演をさせていただきました。杉山研はいろいろな国からの留学生が多くゼミでの公用語は英語だそうです。企業と同様に大学の研究室単位でもグローバル化しているようです。ツッコミも激しかった。杉山研での…
お茶の水女子大学にてSketchSort法に関する講演をさせていただきました。 スライドをアップしました。英語で講演したので英語のスライドになっています。Sketch sort ochadai20101015-publicView more presentations from tbyasu.下はお昼に頂いた仕出しハン…
SketchSort(スケッチソート)法の論文が ACML2010にアクセプトされました。今年も採択率30%の難関でした。http://sugiyama-www.cs.titech.ac.jp/ACML2010/ Yasuo Tabei, Takeaki Uno, Masashi Sugiyama, Koji Tsuda: Single Versus Multiple Sorting in All P…
Locality Sensitive Hashing(LSH)とは、ベクトルとして表現されたデーターの集合を入力として、それらの2点間の距離を保存したまま、ハミング距離に基づく文字列の集合に射影する技術です。コサイン距離[1]、ユーグリッド距離[2]に基づくものや、機械学習法…