講演情報
[7D-01]重み付きインターバルデータに対するTop-k範囲探索
*Lee Jimin1、天方 大地2、原 隆浩2 (1. 大阪大学工学部電子情報工学科原研究室、2. 大阪大学大学院情報科学研究科)
発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：なし
論文種別：ロングペーパー
インタラクティブ発表：なし
キーワード：
重み付きインターバル、範囲クエリ、Top-k
本稿では，クエリインターバルに重なるインターバルの集合において，最も重みの大きいk個のインターバルを返すTop-k範囲クエリに注目する．これは，イベント追跡やスケジューリング等において，与えられた範囲内で最も有意味な情報を取り出したい場合に有用である．既存アルゴリズムでは，クエリインターバルに重なる全てのインターバルを計算し，それらの中から重みが最も大きいk個のものを取り出す必要があるため，非効率的である．本稿では，この非効率性を解消するための2つのアルゴリズム，WIT（Weighted Interval Tree）およびSAIT（Segmented AIT）を提案する．実データを用いた実験により，提案アルゴリズムが既存アルゴリズムよりも高速であることを示す．