でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

Provenance-based Indexing Support in Micro-blog Platformsを読んだ

ICDE2012勉強会に向けてpart2

Provenance-based Indexing Support in Micro-blog Platformsを読んだのでメモ

Provenanceってのは、起源とか出所っていう意味。
この論文では、あるトピックに関連するツイートのまとまりがあった時に、ツイートの伝搬のソースとなるようなツイート(起源)はどれか、また、どのように伝搬していったかを表すんだそうな。

モチベーション
  • ツイートは一つだけ見ても、短すぎて内容を俯瞰できない。
    • 現行の検索システムはツイート単体を検索するようになっているが、あるトピックに関連するツイートのまとまりを検索したほうが内容を俯瞰しやすいんじゃね!?
  • トピック的、時間的に近いツイートの集まり(bundle)を一つの単位としてインデックスする方法を提案
    • bundleはツイートの集まりで、bundle内のツイートは内容的時間的類似度によってつながっていて、木構造をなしている
問題
  • ツイートはものすごく多いので、素直にインデックスするとめちゃくちゃコストがかかる
  • 効率的なインデックス手法を提案
インデックス手法
  • 到着したツイートをBundleを言う単位に割り振る
    • 既にインデックスされているbundleのうち、一番似ているものに到着したツイートを割り当てる
    • 似ているbundleがない場合、新しくbundleを作る
  • ツイートとbundleの類似度は、hashtagやURL、含まれる単語などによって算出する
  • メモリ上には、hashtagやURL、単語などをキーとしたbundleのインデックスを張っておく
    • 到着したツイートに含まれるhashtag,URL,単語を用いて、すでに存在するbundleを高速に取り出すことができる
  • 到着したツイートをあるbundleに割り当てた後、bundle内に存在するツイートのな家から一番似ているものにつなげる(木構造
    • RTやmentionなどでつながっているわけではない、あくまで素性の類似度(タイムスタンプも考慮している)
    • これによって、あるトピックに関連するツイートがどのように増えていったかが分かる
インデックスメンテナンス
  • bundleは、ツイートの到着によってどんどん増え続けていくため、メモリをバカ食いしてしまう
    • そのため、古くなって、もう新しいツイートが割り振られることはないであろうbundleをディスクに格納してメモリから消す
      • メモリ上のbundleの個数が予め設定した個数を超えたらこの操作を行う
    • 大きさがしきい値に達していないかつ時間的に古いbundleはディスクに格納せず削除する
実験
  • Twitterのデータで実験
    • APIを使って集めたツイートのうち、二ヶ月分(約7万ツイート)を用いる
  • インデックスメンテナンスによってメモリ容量が削減できるか
    • できてる
  • インデックスメンテナンスをした場合としなかった場合で、bundle作成結果にどのような影響が出るか
    • しない場合をground truthとみなして、した場合にそれをどれだけ保存できているかを見る
    • メモリ内に保存することを許すbundleの個数が大きければ、インデックスメンテナンスをしても、しない場合の結果を保存している。
  • (実際に作成されたbundleが本当にトピックごとにまとまっているか、bundle内に構築された木構造が妥当なものであるかなどは実験されていない)


読んでみた感想としては、どのへんが新しいんだろうという感じだった。インデックスメンテナンス? ツイートをトピックごとにまとめてインデックスして検索するっていう話は他にもあったと思うけど、あまり技術的貢献がみられないなと思いました。RTやmentionによる構造をもっと積極的に取り入れたほうがより内容を追いやすいbundleになるんじゃないかな・・・?