ユーザの移動を考慮したキーワード付き空間データに対するTop-k問合せのためのストリーミングアルゴリズム

西尾 俊哉  天方 大地  原 隆浩  

誌名
電子情報通信学会論文誌 D   Vol.J102-D   No.1   pp.1-12
発行日: 2019/01/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2018JDP7013
論文種別: 論文
専門分野: データ工学,Web情報システム
キーワード: 
Pub/Sub,  Top-kクエリ,  ムービングクエリ,  キーワード付き空間データ,  

本文: PDF(1.1MB)
>>論文を購入


あらまし: 
近年,多くのアプリケーションでは,パブリッシュ/サブスクライブ(Pub/Sub)モデルに基づいてデータが配信されており,ユーザは生成されたデータの中から自身が興味をもつもののみを取得する.また,スマートフォンやタブレットの普及により,ユーザが移動しながらアプリケーションを利用し,現在地に近いデータを受信するムービングクエリへの関心が高まっている.本研究では,Pub/Subモデルで生成されたデータの中から,ユーザが移動しながら自身の興味に合う上位k個のデータ(Top-kデータ)をモニタリングする問題に取り組む.ユーザが移動するたび,そのユーザのTop-kデータを再評価し,また,データが発生するたび,全てのクエリのTop-kデータを再評価する方法は非効率的であり,多くのユーザが存在する環境に対応できない.この問題を解決するため,ユーザの移動やデータの発生によりTop-kデータが変化する可能性のあるクエリに対してのみ,Top-kデータを再評価するアルゴリズムを提案する.実データを用いた実験により,提案アルゴリズムの有効性を示す.