Cache-oblivious priority queue and graph algorithm applications

Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, and J. Ian Munro. 2002. Cache-oblivious priority queue and graph algorithm applications. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (STOC '02). ACM, New York, NY, USA, 268-276. DOI=10.1145/509907.509950 http://doi.acm.org/10.1145/509907.509950

• 貢献
  • cache-oblivious な priority queue を作った!!
    • 各操作 O(1/B log_{M/B} N/B) amortized IO (optimal)
    • cache-oblivious では search tree を使うと sort が optimal にはできないことが知られている (普通だと optimal になるやん)
    • この priority queue はこれを使うと sort が optimal になる
  • それを利用して cache-oblivious なグラフアルゴリズムを大量に開発した!!
    • list ranking / tree algorithms / directed BFS&DFS / undirected BFS / MST
• priority queue
• graph algorithm
  • list ranking
    • ほぼ今までの external memory モデルでの IO-efficient なアルゴリズムそのまま
    • 3-coloring → independent set → cache-oblivious sort等 (めんどくさ!!)
    • どこで彼らのアイディアが入ってくるのか…と思ったら 3-coloring するところでさりげなく priority queue 使っているらしい
  • 他
    • だいたい既存のアルゴリズムで，list ranking が cache-oblivious になった事によってなんとかなったりしているようだ

感想

論文のかかれ方が参考になりそうな感じだった．こういう重要性がある，とか，こういう技術的なチャレンジングなところがある，とか，このアイディアは汎用性が高い，とか，主張しまくっている．

中身は複雑すぎる感じで，セオリー的にはブレイクスルーなのかもしれないが，プラクティカルさをあまり感じなかった．残念．

プラクティカルで optimal じゃないがそれに近く実際高速な cache-oblivious なプライオリティキューには quickheap があるね．

グラフアルゴリズムは実際ランダムアクセスの塊でどーすんだという感じできになっていたが，ウーン．

http://algo2.iti.kit.edu/dementiev/files/ebfs.pdf

↑プラクティカル寄りだとこの external memory BFS の論文が気になるね．こういうのでも SODA 通るんだなあ．