ALSIP2011に参加して簡潔データ構造の話を聴いて来ました
香川県高松市にて開催されたALSIP2011(Second Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery)に参加してきた。
簡潔データ構造で有名なRajeev Raman先生、NIIの定兼先生、PFIの岡野原さんが招待講演をして下さるということで以前から注目していた。
招待講演に加えて興味深い10本の発表がありとても楽しめた。私の勉強不足もあって初めて知ることが非常に多く勉強になった。簡単に内容をメモしておく(理解不足のため間違ったことを書いていたらすみません)。
今回の会議で最も興味深かったのがgrammer-based compressionというもので、これは例えばX=ababという文字列があったときにX1=a,X2=b,X3=X1X2,X=X3X3という感じで生成文法的なルールの形式で文字列を持たせることでデータを圧縮しようというもの。このgrammer-based compressionされたデータはDAG(directed acyclic graph)で持つことができるので、じゃあDAGの簡潔構造を考えようという話になる。
↑も含めて木構造ではないけど何らかの制約が入ってるようなtree-likeなグラフの簡潔構造を考えようというあたりが最近の簡潔構造的トレンドらしい。
なお招待講演の資料は3本とも公開済み。どれも資料価値の高い発表だったのでとてもうれしい。
以下、簡単にメモを残しておく。
一日目(12/1)
Fast q-gram Mining on SLP Compressed Strings
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda
SLP(Straight Line Program)というgrammer based compressされたデータに対してn-gram(q-gramはn-gramと同じと思ってよい感じ)を効率的に計算するよという話。興味深い話だったけれどSLPの構築が重そうな印象がある(定兼先生もそんな感じの質問をされていたような)
High-throughput Data Stream Classification on Trees
Mahito Sugiyama, Tadashi Yoshioka and Akihiro Yamamoto
ラベル無しデータをラベル有りデータとの類似度を計算することで分類するというkNN的な話。データをbinary encoding(0/1の列で表す)して、ラベル有りデータで作ったtrie的な木を検索することでラベルなしデータとの類似度を効率的に計算するよ、というような話だった。
Task Summarization for User Behavior Clustering
Ryohei Saito, Tetsuji Kuboyama, Yuta Yamakawa, and Hiroshi Yasuda
ユーザがアプリを使った履歴を観測データ、ユーザ意図(behavior?)を非観測データとしてHMMで学習する話。データ構造の話が多い中、機械学習それも生成モデル系の話がでてきてちょっとびっくり。
Space-efficient representations of complex objects
Rajeev Raman (University of Leicester, UK)
Raman先生(http://www.cs.le.ac.uk/people/rraman/)。上でちょっと書いたtree-likeなデータ構造の簡潔構造化について。正直知らないことが多すぎてあまりついていけなかったのだが、めちゃくちゃ面白そうという雰囲気は伝わってきた。公開資料でもう一度勉強したい。
Succinct Trees: Theory and Practice
Kunihiko Sadakane (National Institute of Informatics)
資料(http://researchmap.jp/sada/succinct/)が公開済み。簡潔構造の基本と木構造(LOUDS,BP,DFUDS)についてよくまとまったすばらしい資料になっている。BP、DFUDSは私はさわりの部分しか知らなかったのでとても勉強になった。
二日目(12/2)
Fast Similarity Search for Large-scale Graph Databases with Wavelet Trees
Yasuo Tabei and Koji Tsuda
6月くらいのIBISMLで話された内容とだいたい同じ？ウェーブレット木を使って高速類似度計算する話。
On Computing Tractable Variations of Unordered Tree Edit Distance with Network Algorithms
Yoshiyuki Yamamoto, Kouichi Hirata and Tetsuji Kuboyama
木構造の編集距離の話その1。最大フローとかのネットワークのアルゴリズムを使ってあれこれという話だった。面白そうなんだけど苦手な分野なのでアリ本で勉強しないと・・・
An A* Algorithm for Computing Edit Distance between Rooted Labeled Ordered Trees
Shoichi Higuchi, Tomohiro Kan, Yoshiyuki Yamamoto and Kouichi Hirata
木構造の編集距離の話その2。こちらはA*アルゴリズムを使うそうな。こっちも面白そう。
Succinct Data Structures for Analyzing Document Collections
Daisuke Okanohara (Preferred Infrastructure)
定兼先生が木構造の話をされていたのに対して、こちらは簡潔構造のもうひとつの実用化されている分野である文字列についての簡潔構造。またそれを用いた文書解析とか。これも大変資料価値が高い。余談だけれどこの発表ではじめてwat-arrayの仕組みを知った(コード読むのさぼってた)
Engineering Parallel String Sorting Algorithms
Takuya Akiba, Kentaro Imajo and Daisuke Okanohara
Radix sortなど、ソートを並列にやる話。並列の話は興味あるんだけどなかなか手を出す時間ががが。面白そうなんだけどなー。
Mining Closed Weighted Itemsets for Numerical Transaction Databases
Yuichi Kameda and Akihiro Yamamoto
DB系の話。ちょっと専門外でよくわからなかった。あとで調べる・・・時間あるかな・・・。
Grammar-Based Compression for Frequent Pattern Mining
Masaya Nakahara, Shirou Maruyama, Tetsuji Kuboyama and Hiroshi Sakamoto
話題のgrammer-based compression。こちらはapproximate searchで頻出パターンマイニングな感じの話。
Preserving Privacy with Dummy Data in Set Operations on Itemsets
Keisuke Otaki and Akihiro Yamamoto
プライバシーを保ってデータマイニングだ！な話。あまり詳しく無いですすいません。。。
以上。こうして書きだしてみて２日目にいかに集中力が落ちていたかがわかった。もっと精進しなければ・・・。
この会議に参加するまで木構造、文字列の簡潔構造が実用的で・・・という認識だったのだが、それに加えてtree-likeなやつがアツいということがわかったのが大きな収穫。もっとがんばっていきたい。
あと招待講演は3本ともすごくいい資料で(くどい)、Raman先生がtree-like、定兼先生が木構造、岡野原さんが文字列、と主だった部分が3つの資料でカバーされてるのでこれらを読めばどのあたりを勉強すればいいのかすぐわかる。はやく3つとも公開されるといいですね。
なんかまとまりがない文章だがこのへんで。。。
