Top-k文書列挙問題 - DO++いろいろとありまして去年読んだ論文で面白かったものランキングとか書けなかったのが残念ですが、もしあげるとしたら次の論文は入れると思います（知ったのは年明けだったけど）。 "Space-Efficient Framework for Top-k String Retrieval Problems", FOCS 2009, Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter (pdf) 扱っているのは次のような問題です（説明のため本来のと言い換えています） n個の葉からなる木が入力として与えられ，各葉には色（1以上d以下の整数とします）が与えられています． この時、木中の任意の節点と正整数kがクエリとして与えられたときに、その節点の子孫の中で出現回数が大きい色を順にk個答えよという問題です。 簡単に思いつくのは，各節点に適当な個数(d)の答えをあ
