« 旅 | Main | LZ法再び »

2008.09.27

旅まとめ

ESA2008 と NLP week(言語処理若手の会、言語処理研究会)に行ってきました。
随時学会の内容をアップする予定でしたが、旅中はなんとなく更新しませんでした。

記憶も曖昧になっているので箇条書きで

ESA2008 @ カールスルーエ
カールスルーエはドイツの南西にある比較的小さな街だが、街並みはきれいで街中を走るトラムが便利だった。ビールはコンスタントに飲んでました。発表内容自体は、ちょっと違う分野になるとついていくのが大変

自分の発表 "An Online Space-Efficient Algorithm for Searching the Longest Match String" (予稿: pdf 発表資料: ppt pdf)はスライドが化けたが、まぁ発表して、詳しい人からとその後ちょっと議論できた.

気になった発表は(論文はタイトルで検索すると大抵でてきます)
"Better and simpler approximation algorithms for the stable marriage problem" ベストペーパー。安定結婚問題の最大マッチング近似を簡単なアルゴリズムで改善した
"More Robust Hashing: Cuckoo Hashing with a Stash" Cuckooで逃げ場所(Stash)をほんの少し用意しておくだけで作り直す確率はものすごく小さくなる.解析が激しい
"Bloomier Filters: A second look" Bloom Filterでキーがあるかどうかだけではなく,関数もサポートするようなもののより簡単な解析 途中から数論っぽい議論がでてきて、違う世界にとんでいった
"Succinct Representations of Arbitrary Graphs" グラフの簡潔表現の(ほぼ)決定版? 今までは平面グラフとか分割が簡単なグラフに対する簡潔表現が提案されていたが、この研究では、全てのグラフに対する簡潔表現を提案.実用的なところへの工夫はまだか。グラフの冗長性とかはまだ残されている
"A Practical Quicksort Algorithm for Graphics Processors" GPS上でQuick Sort.現時点で大部分のデータに対して一番最速
"Randomized Competitive Analysis for Two-Server Problems" 乱拓アルゴリズムを使って最悪値を大分減らせるという話.その後いろいろTwo-Server問題について詳しく聞かせてもらったがディスクのデフラグとかがまさにこの問題にあたるらしい.
"Flexible Path Planning Using Corridor Maps" 招待講演。ゲームの研究で(ゲームの研究はヨーロッパとかではかなり真面目にやられているらしい)、CGがリアルになるにつれ、より自然な振る舞いが重要になってきている。で、特に大量のキャラクターを自然に動かすのが大変。これは、A地点からB地点まで障害物や人を避けて外乱に対してロバストに自然に動くことを現実的な計算量で求めたい.これは、あらかじめCorridor Mapというのを作っておくと非常に効率的に求まる.発表者が発表中に手品をしていた.

アルゴリズム系の学会は、発表のスタイルが自然言語処理とか機械学習と違って面白いですね。下限をまず示して、上限は実際にアルゴリズムを構成して調べるとか。問題をどんどん拡張して作っていくところとか。

NLP若手の会 @ 熱海
オーバーブッキングのためドイツからの帰国が遅れ家についたのが日曜の夜になり、次の日からNLP week.ポスターやら発表資料を作り(確信犯的に)寝坊した.
自分は今まで作ってきたtxやらbepやらollを学会とかで発表したことないなぁということで、広告っぽく宣伝してきました.pdf(poster).みんなでかいデータを扱うのに困っている人が多くて、実際に使ってるという声も頂いてうれしかったです
他の方の発表もツールやらコーパスやら、ちょっと論文にするには難しいけど、実際の場面では重要なものを多く発表されていたような気がします。こういう場所は重要だと思います。

NL研 @熱海
若手の会に続いてNL研.自分の発表は4年ぶり.
私は、"全ての部分文字列を考慮した文書分類" (予稿 pdf 発表資料 ppt pdf)というタイトルで発表.接尾辞配列、L1正則化、Graftingなどの合わせ技になっております.


こういう学会やらシンポジウムでは重要度としては、発表したり発表内容を聞くのが1/3ぐらいで、2/3がいろいろな人と出会い交流を持つことにあるとおもいます。今回もいろいろな人と出会いより交流を深めることができました。
しばらく肝臓を休ませます。

|

« 旅 | Main | LZ法再び »

Comments

ドイツに行くほど色々研究できて楽しそうですね。

ずっと前ためしに作った並列ハッシュテーブルですが、Interlocked使うとバスをロックしてしまい、ランダムアクセスで、キャッシュも余り聞かないのであまり効果が無いのが残念でした。
最近単純な配列をスレッドに分けて読み込み、書き込み先ハッシュテーブルもスレッドに分けて書き込む仕組みを作ってみました。スーパリニアリティが働くので前のよりはスケーラブルでした。

ということで最近の興味はスーパリニアリティとSetThreadAffinityMaskなんかを使って1次、2次、3次キャッシュの共有具合に応じて利用するcpuをアルゴリズムとデータ構造に合うように使い分けることで性能を発揮できないかと考えています。そういう研究ってないでしょうか?

Posted by: | 2008.09.30 at 09:57 PM

こんにちは。お久しぶりです。
そこまでの粒度でcpuを使いわけるのってあまりきいたことないですねぇ。

こういう感じでアクセス速度が全く違う記憶媒体をフルに使いこなす話ではCache-oblivious algorithm(検索するとwikipediaとかで出てきます)とかが最近はやってますかねぇ。どれくらい実用的なのかはまだ分からないですが。これはあらかじめキャッシュサイズとかその間のバンド幅を知らなくても、最適なリソース分配ができるようなアルゴリズム群です。今後はやるかも

Posted by: oka | 2008.10.22 at 01:06 AM

キャッシュサイズなんかはアプリ起動時に計測してパラメータとして求め、それをアルゴリズムのパラメータとして使う…というのも広義にはcache obliviousになるんでしょうか。
そういうのも求めなくてもできるならすごいですよね。
僕はVirtualAllocで確保できる仮想メモリの割り当てもディスク領域を物理メモリに「キャッシュ」すると考えると、これってプリフェッチみたいに最適化できるみたいですよ。VirtualLockでページアウトを防げるんですが、cpuキャッシュのプリフェッチ命令みたいですよね。明示的バッファリングと比較しましたら仮想メモリのほうが早かったです。
仮想メモリもある程度プログラマーからのヒントを与えやすくなると明示的バッファリングに比べてさらに高速に出来ると思います。

Posted by: 和 | 2008.10.23 at 12:05 AM

続き

このテクニックをokaさんの扱う大規模なデータ構造に応用すればシンプルかつ高速に出来るかもしれません。
欠点は仮想メモリで扱える範囲に限定されてしまうこととページ単位で扱えるようにデータ構造を変更しなければならないことですね。
仮想メモリは連続して確保できることは余り期待しないほうがいいですし。

Posted by: 和 | 2008.10.23 at 12:08 AM

My brothr recommended I would possibly like this web site. He was totally right. Thiss posdt actually made myy day. You cann't imagine simply how so much time I had spent for this info! Thank you!

Posted by: coffee tables | 2013.10.08 at 12:44 AM

This is really interesting, You're a very skilled blogger. I have joined your feed and look forward to seeking more of your magnificent post. Also, I have shared your web site in my social networks!

Posted by: how to get pregnant with a girl | 2014.02.22 at 04:44 PM

First off I want to say superb blog! I had a quick question that I'd like to ask if you don't mind. I was interested to know how you center yourself and clear your head before writing. I have had a hard time clearing my thoughts in getting my thoughts out there. I do enjoy writing however it just seems like the first 10 to 15 minutes tend to be lost simply just trying to figure out how to begin. Any ideas or hints? Thanks!

Posted by: Delhi Escort | 2014.12.21 at 04:34 AM

magnificent issues altogether, you just gained a new reader. What might you recommend in regards to your submit that you made some days ago? Any positive?

Posted by: delhi escort | 2015.04.17 at 05:59 AM

Exceptional post but I was wondering if you could write a litte more on this subject? I'd be very grateful if you could elaborate a little bit more. Many thanks!

Posted by: delhi escort services | 2015.06.06 at 07:40 PM

We absolutely love your blog and find almost all of your post's to be just what I'm looking for. Would you offer guest writers to write content for you? I wouldn't mind publishing a post or elaborating on a lot of the subjects you write with regards to here. Again, awesome site!

Posted by: free porn | 2015.06.08 at 10:25 AM

This website was... how do I say it? Relevant!! Finally I have found something that helped me. Appreciate it!

Posted by: delhi escort | 2015.06.28 at 08:54 PM

Hi there to all, the contents existing at this website are actually awesome for people experience, well, keep up the nice work fellows.

Posted by: delhi escort | 2015.10.07 at 05:48 PM

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/3041/42605783

Listed below are links to weblogs that reference 旅まとめ:

« 旅 | Main | LZ法再び »