[4C]近傍問合せ

10:00 〜 10:25

[4C-01] mCK検索における独立性と被覆性のある最適な代表解集合の計算

*塙 雪耶¹、大森 匡¹、新谷 隆彦¹、藤田 秀之¹ (1. 電気通信大学大学院　情報理工学研究科)

発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：あり

キーワード：

問合せ最適化、空間Webマイニング、mCK検索、独立性・被覆性

緯度経度情報つきのWebデータを用いた情報抽出問題にm-最近接キーワード検索(mCK検索)がある．mCK検索とは，Flickrのように個々の写真データ(オブジェクト)が場所と写真内容に関するタグ複数を持っている状況で，問い合わせとしてキーワードm個の入力Qを与え，Qを満たす高々m個のオブジェクト集合Oのうち，その要素の相互近接度(直径の小ささ)が最も高い集合Ooptを求める問題である．mCK検索では，オブジェクトの組み合わせを答えとするため，直径が小さい順にk個の答えを列挙すると地図上の数ヶ所に答えが集まり，解の多様性が低下する．本稿ではその解決方法として，直径長ε以下のmCK解全解を対象にDrosouのr-DisC diversityを適用し，独立性・被覆性のある代表解の最適集合を求める方法を述べる．