« July 2009 | Main | September 2009 »

2009.08.31

SPIRE2009

フィンランドのサーリセルカという場所で開催されたSPIRE2009で発表してきました。

サーリセルカは北極圏で、百夜ではなかったですが夜暗くなったのは4時間ぐらいでした。天候が悪く残念ながらオーロラはみれませんでした。トナカイを見て、トナカイを食べてきました。
エクスカーションでイナリというところにいき、またワークショップの後に山にハイキングに行きました(ハイキングといっても6時間ぐらい歩く結構本格的なもの)。誰も声を出さないと耳がおかしくなるくらいの無音になるとにかく静かなところでした。冬に行くとクロスカントリーとかが楽しいらしい。

聞いたメモ

- "Novel and Generalized Sort-based Transform for Lossless Data Compression", Kazumasa Inagaki, Yoshihiro Tomizawa, and Hidetoshi Yokoo
Burrows Wheeler変換が文脈長∞でソートしているものだと考えた場合,文脈長を適当なパラメータで打ち切ったもの(szipにおけるST)や,文脈を一定間隔で変えた場合に対応する変換も考えられる.こうした一般化した変換を定義し,その逆変換はどうすればいいかや性質などを述べている.

- "Directly Addressable Variable-Length Codes", Nieves R. Brisaboa, Susana Ladra, and Gonzalo Navarro
可変長符号で直接アクセスが可能なものの現実的な実装手法.Navarroのグループでこの実装をいろいろなものに適用しているといっていた.私が昔提案したVertical Codeというように似ているが,こっちの方が効率がよさそう.

正の整数集合を符号化する際に,あらかじめ決めておいたb bitで符号化し、もしだめなら後続ブロックに残りを記録する.それぞれのブロックの前に後続ブロックがあるかどうかのフラグを0, 1で記録.
次に,全ての整数についての1つめのブロックをまとめて記録し,そのフラグもまとめて記録.次に2ブロック目があるものだについてもそれらのブロックまとめて記録し,そのフラグをまとめて記録.フラグにおけるrankでどの位置の整数情報にも直接アクセス可能

" Range Quantile Queries: Another Virtue of Wavelet Trees", Travis Gagie, Simon Puglisi, and Andrew Turpin.

整数列 x[1...n], x[i]∈[1...σ]と,その中での範囲[i, j]が与えられた時,x[i..j]中の最小要素を返すのがRange Minimum Query(RMQ).RMQは今やたくさんの問題で使われているが,これの拡張でx[i..j]中のk番目に小さい要素を返す問題を考える.
x[1...n]でwavelet treeを構築する.まず,根についているbit配列での[i..j]中での0と1の数をrankで数え,その中で0の数がk個より大きいなら0側の枝を辿り,そうでないなら1側の枝を辿り,探索を繰り返す.
workshopではこれの変種で文書列挙問題を考えていた.現実的で使えそう(未発表なので中身書けません)

- "Constant Factor Approximation of Edit Distance of Bounded Height Unordered Tree", Daiji Fukagawa, Tatsuya Akutsu, and Atsuhiro Takasu.
節点の挿入・削除、ラベルの置換などの編集操作を許した状況で木と木の編集距離を考えた場合,その編集距離の近似手法を提案。まず木を、その木に含まれる完全部分木の回数を並べた特徴ベクトルで表わす。そして、二つの木に対する特徴ベクトルのL1距離が、編集距離を木の高さ分ぐらいの近似度で近似できることを示した。いろいろつかえそう

- " k2-trees for Compact Web Graph Representation", Nieves R. Brisaboa, Susana Ladra, and Gonzalo Navarro.
疎なグラフの表現方法の提案.まずグラフを隣接行列で表し,次に隣接行列を再帰的に正方形のブロックに分ける.ブロック内に1が一つもなかったらそこで終了で、あったら再帰して分割する.再帰をするかどうかの情報は0, 1のビット配列で表し、rank/select操作でアクセスする.サイズは既存手法で一番よいものと匹敵.実装が簡単そう

- Compressed Suffix Arrays for Massive Data, "Jouni Sirén
接尾辞配列が二つ与えられたとき、それをマージする方法は知られているが,それを圧縮接尾辞配列の場合に適用し、これを使って大量の文書(wikepediaの履歴だったと思われる)に対する圧縮接尾辞配列を構築することを提案.
履歴情報など非常に圧縮できる場合は、圧縮全文索引が有効であることが確認された。圧縮率は1/20ぐらいだった。

- On Entropy-Compressed Text Indexing in External Memory, "Wing Kai Hon, Rahul Shah, Sharma V. Thankachan, and Jeffrey Scott Vitter
HDDなどの外部記憶領域でブロックI/O回数を最小にするような問題でエントロピーに圧縮した全文索引を提案.この論文で引用されているsparse suffix treeとかはフォローしてなかったのでちゃんとみておかないと
ちなみに発表者のインドの方とは夕食でいつも一緒に食べてていろいろ話した。インドでは「スズキ」の乗り物がも
のすごい評判がいいらしい

- "Fast Single-Pass Construction of a Half-inverted Index", Marjan Celikik and Hannah Bast
まずこの論文が構築する、最近提案された半転置ファイル(pdf)というのは、termリストを辞書式順序で並べて、適当なブロックにわける。そして、出現位置を記録するときは対応するブロックに単語番号付きで記録する。
このような索引をデータを一回走査するだけで構築する手法を提案。

| | Comments (564) | TrackBack (0)

2009.08.23

近況・宣伝など

8月後半から9月にかけて発表を予定しているものがいろいろありますので宣伝

- SPIRE 2009 (8/25~8/28 Finland)
-- "A Linear-Time Burrows-Wheeler Transform using Induced Sorting"
- 前にも話したBWTをSuffix Arraysを経ないで直接線形時間で構築

- The Fourth Workshop on Compression, Text, and Algorithms(8/29 Finland)
-- "Engineering a Direct Burrows-Wheeler Transform Algorithm"
-- SPIRE 2009併催.上記のBWTアルゴリズムの実装や実験の話をします.

- 第3回SBM勉強会(9/13@ 東工大)
-- "SBMの推薦アルゴリズム"
-- レコメンドアルゴリズムの結構濃い話をするつもり

- ACM SIGMOD日本支部第42回支部大会(9/15@東工大)
-- "大規模検索エンジンとレコメンドシステムを支える仕組み"
-- こちらは疎行列上での計算とか,SSDとか、LSHなどの近似計算手法とかの話をする予定

- NLP若手の会(9/30-10/1@京大)
-- "ベイズ全域木モデルによる文書クラスタリング"
-- 文書集合の生成モデルに全域木を使って、ベイズ推定.とにかく大量の文書で(数百万文書ぐらい)で実験を進めている

他に、CompView 秋の学校(9/17~9/19)で勉強させていただきます.講師陣が豪華.
あとは大きめの原稿を書いています.

あとは、この夏あったこと

- 最近、8年住んでいたところから東京の北の方に引っ越しました.なかなか快適です.夏の引っ越しは暑かった

- 京大のoxyさんのところに行って共同研究してきました.(oxyさん側の反応).時間制限があって追い詰められるとなんかアイディアは出るものですね.oxyさんの解析能力とその情熱が素晴らしい.近くの中華料理屋も素晴らしい

- 開発合宿を久々にやりました.成果は出ましたが,もう若くないのか,体がその後しばらくダメでした.

- 会社でインターンの方々を受け入れて既に1ヵ月が経ちました.みんなぴちぴち、能力もすごい

- 博士の中間発表終わり.あと半年ラストスパート.修士論文終わった時は奥田民生の「厳しいので有る」を聞いて後3年はこんな思いをしなくて済むと思っていたが,とうとうやってきた.

- 日経BPオンラインのtwitter特集で私のインタビュー記事が載りました(link).はじめからtwitterの話から脱線して,会社Preferred Infrastructureの経緯や私がこれまで見てきた海外エンジニアの話とかになってます.

| | Comments (2) | TrackBack (0)

« July 2009 | Main | September 2009 »