« SODA2010 ALENEX2010@テキサス | Main | fujimap: 簡潔な連想配列 »

2010.02.19

Top-k文書列挙問題

いろいろとありまして去年読んだ論文で面白かったものランキングとか書けなかったのが残念ですが、もしあげるとしたら次の論文は入れると思います(知ったのは年明けだったけど)。

"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)の答えをあらかじめ前計算したものを持っておくというアプローチですが、この場合保存に必要なスペースは
節点数がO(n)のため、O(nd)bitsとなる上、d < kの場合は途端に計算量が爆発します.

この問題は全文検索と非常に強い関係があります.検索対象D個の文書に対し接尾辞木や接尾辞配列で索引を作る場合、それらをつなげた長さnの入力文を作成します。
次に、それに対する接尾辞木(一般接尾辞木)を構築します。検索のときは普通の接尾辞木のよう検索を行い、ヒット位置集合を求めた後に、それらの位置が元々どの文書に所属していたかを求めます.
ヒット件数を求めるのはO(|q|)と高速に行うことができるのに対し、ヒット文書集合、ヒット文書数を求めるのはヒット位置数がoccの時、O(occ log D)時間かかってしまいます。
各位置に対してそれがもともとどの文書に対応していたかを調べるにはO(log D)時間かかるため。
ヒット位置数が数億などで、それらの中からクエリに特に関係する数十程度の文書を求めるのに非常に大きな時間がかかってしまいます。

これに対する解法はいくつか提案されていますが補助データ構造のサイズが非常に大きいなどの問題がありました

論文では、この問題をO(k log k + dep)時間で正確な結果を求めることができ、O(n log n)bitsで保存可能なデータ構造を提案しています。depは節点の深さです。
これはかなりまじめにやった場合で、ヒット位置数が大きい場合節点に対して保存することにより、データ構造のサイズはいくらでも小さくなりえて、結構現実的です。

まず、木中の節点(葉も子の数が0の節点とする)に対し行きがけ順(preorder)で番号をつけておきます。これは深さ優先探索をして、辿った順です。
この番号のつけ方だと、ある節点以下の部分木は全て連番になっているという特徴があります。

次に、各節点において(親へのポインタ:p 色:c)エントリの配列からなるN-structureというデータ構造を考えます。
まず、各葉では、自分の色からなるエントリのみをN-structureに保存します。
次に各内部節点では、二つ以上の子が色cの葉を子孫として持つ場合、色cのエントリを持つとします。そして色cのエントリ中のpは、同じ色cのエントリを保持する最も近い祖先の節点番号とします。
もし、そのような親が無い場合は-1をpとして記録しておきます。

先ほどの定義より、ある節点において、同じ親へのポインタを含むエントリを複数持つ場合はあります、が同じ文書番号を含むエントリは高々一つしか存在しません。

図では葉に色(a,b,cの文字ですが)がacbaaccbcとつけられている場合の例を示します
図中の青色の箱がN-structureの例です。例えば番号2の節点(-1, a), (1, c), (-1, b)の三つのエントリからなるN-structureが保存されています。番号3の節点のように一つもエントリが無い節点も存在します。

Tree_3

このとき全エントリの総数は高々2n個です。なぜなら、それぞれ葉の数がn個で子二つが持っている場合のみ内部節点にはエントリが存在するからです。

次に、N-structureの逆向きのI-structureというのを考えます。これは(子へのポインタ:p 色:c 頻度:f)を保存した配列です。例えば節点tにおいて(p, c)というエントリがN-structureに存在する場合、
節点pに(t, c, f)というエントリが存在します。fは節点tの子孫中の色cの個数です。
I-structure中では、エントリは子へのポインタの番号順にソートしておくことにします。頻度:fは対応する子でその色が何回出現しているかを記録したものです。
図のオレンジ色の箱がI-structureの例です。

このI-structureのエントリの総数もN-structureと一対一対応があるので高々2n個です。
検索時に保存するのはI-structureのみです。

では、これを利用して先ほどの問題を解いてみましょう。

クエリとして節点tと正整数kが与えられ、t以下の色で頻度が高い順にk個報告するのが目標です。

まず、t以下の節点、葉は行きがけ順で番号をつけたことから連続する番号がつけられています。これを[t, t']としましょう(t'はt中の最右の葉)

次にtの親から根方向に向かう各節点のI-structureにおいて、[t, t']内の値を子へのポインタとして持っている範囲を見つけます(*)。I-structureはポインタの番号順にソートされているので、この範囲は連続した区間に存在し
二分探索でその範囲を求めることができます。例えば、図の例でクエリで節点3が与えられた時 [t, t']=(3, 6)なので、節点2においては(4:a 1) (5:c 1) (6:b 1)が該当する範囲であり、節点1, -1ではこの範囲に該当するエントリは
ありません。

この範囲の集合に対し次の事実があります。

事実:tを根とする部分木中に出現している各色に関するエントリはこれらの範囲の集合内ではちょうど1回出現し、それの頻度fはt中の色cの出現頻度と一致する。

これは、ある部分木内に色cが出現している場合、この部分木から外に飛び出すポインタで色cに関するものはちょうど1個しかないこと、またそのポインタの子孫にのみ色cの葉が含まれていることからいえます。

さて、この事実を使えば、これらの範囲集合内で頻度が大きいものをk個とってくればいいだけになります。同じ文書番号を重複して数えてしまうとか、足さないといけないとか考える必要はありません。

それぞれの範囲内でRange Max Query (RMQ)を走らせ、各範囲内で最大値のものをk個ヒープに登録します。
そして、ヒープから一個ずつ一番高い値を取り出し、取り出した値に関する範囲を二個の部分範囲に分割し、それぞれの中からRMQを適用してまた最大値二個登録し、ヒープから最小の値を一個除きます。これを繰り返せば上位k個を取り出すことができます。
この時間はRMQはO(1)時間、O(n)bitsで実行でき、ヒープの操作時間合計はO(k log k)です。

(*)を求める時間は二分探索であることからO(log n)時間、predecessor用のデータ構造を使うとO(log logn)時間でとけますが、もうちょっと補助データ構造を使うと一つの節点あたりO(1)時間でとくことができます。

計算時間はクエリ節点から根への範囲の個数は高々dep個なので、まとめるとO(dep + k log k)時間でとけます。

さて、この話は頻度情報以外も扱えます。例えば文書にページランクのような固有のスコアが与えられている場合、fの代わりにそのスコアをいれておけば、同じように動きます。

アイディアは単純ですがとてもきれいな話だと思います。
この著者の人と昨年夏にあったとき、すごいのを思いついているのだが言えないといってたのが分かります。

|

« SODA2010 ALENEX2010@テキサス | Main | fujimap: 簡潔な連想配列 »

Comments

☆☆☆☆☆☆☆☆☆☆☆☆☆☆

Posted by: nushio | 2010.02.20 at 09:29 AM

uggのムートンブーツ 中古品店、アンティーク ショップが見つかりますおよびファッション店をすべてを道路。デザインとスタイル財布のある必要がありますイベントを保つことを選んだ心の目。すべきないになる、違い大きい.今まで ! ugg ブーツ サイズ

Posted by: uggのムートンブーツ | 2013.11.25 at 08:29 PM

Pretty nice post. I just stumbled upon your weblog and wished to say that I have really enjoyed surfing around your blog posts. After all I'll be subscribing to your rss feed and I hope you write again very soon!

Posted by: youtube.com video immune boosters | 2013.12.06 at 11:19 AM

I was suggesred this web site by my cousin. I'm not sure whether this post is written by him as no one else know such detailed about my difficulty. Yoou are incredible! Thanks!

Posted by: attic average mold removal costs | 2014.08.25 at 11:24 PM

Veгy good information. Luсky me I ran across your bloǥ by chance (stumbleupon). I Һave saved it for later!

Posted by: san francisco kitchen hotels weather things to do in nashua new | 2014.08.27 at 09:14 AM

WOW just what I was looking for. Came here by searching for erectile dysfunction symptoms

Posted by: Teodoro | 2014.08.27 at 09:39 PM

Pretty! This was an extremely wonderful post. Many thanks for providing these details.

Posted by: massage therapy gold coast australia | 2014.08.31 at 01:08 PM

Excellent way of describing, and good paragraph to get facts concerning my presentation subject matter, which i am going to convey in college.

Posted by: gold coast massages | 2014.09.01 at 03:36 PM

I've been exploring for a little bit for any high quality articles or weblog posts in this sort of area . Exploring in Yahoo I at last stumbled upon this web site. Reading this info So i am satisfied to show that I've an incredibly just right uncanny feeling I found out exactly what I needed. I such a lot certainly will make certain to do not overlook this website and give it a glance on a constant basis.

Posted by: melatonin | 2014.10.25 at 10:11 PM

ELD Standards Draft Approach - Extra site for that alignment of the Language Language Progress criteria that are revised to english language Disciplines. The effective filter is definitely an essential part of second language learning.

Posted by: internationalprayercenter.org | 2015.01.14 at 08:48 AM

Understanding online can be calm which ofcourse is likely to be beneficial to your understanding. Several online program present extra support and present you since it lets you connect to other people who are understanding Japan language use of online learning communities which raise your learning potential. Online programs range from health and humanities, arts and medication, business, research and technology, computers, social sciences, training and coaching, trades and jobs, and so many more. Together with many selections of programs, additionally, there are a broad selection of online universities accessible. Total, online knowledge is a lot less costly than going to a traditional university because you conserve occasion, on travel, and the classes themselves cost less. A lot of some time you're able to get your stage significantly quicker sufficient reason for a whole lot more convenience in a online plan than at a standard school. Receive online and acquire forward!

Posted by: day tieng nhat ban | 2015.01.16 at 02:18 PM

Howdy! I just would like to offer you a big thumbs up for your excellent information you have here on this post. I will be coming back to your website for more soon.

Posted by: match.com | 2015.04.06 at 11:21 AM

Post a comment



(Not displayed with comment.)




TrackBack

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

Listed below are links to weblogs that reference Top-k文書列挙問題:

« SODA2010 ALENEX2010@テキサス | Main | fujimap: 簡潔な連想配列 »