m-最近接空間キーワード検索における探索優先順制御とタイトな下界値を用いた高速化手法の提案

邱 原  大森 匡  新谷 隆彦  藤田 秀之  

誌名
電子情報通信学会論文誌 D   Vol.J99-D   No.7   pp.638-651
発行日: 2016/07/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2015JDP7098
論文種別: 論文
専門分野: データ工学,Web情報システム
キーワード: 
空間データ,  mCK検索,  Top-Down方式,  

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




あらまし: 
近年,テキストと位置の情報をもつ空間的なWebデータを対象に,キーワード入力による空間的な情報の抽出・検索を行う空間キーワード検索が注目されている.その一つにm-最近接キーワード検索(以下,mCK検索) [1]がある.mCK検索とは,高々m個の空間的なWebデータ(オブジェクト)の組み合わせを考え,そのうち,ユーザが与えたm個のキーワード全てをコンテンツに含み,かつ,空間的に相互距離が一番小さい組みを探す問題である.mCK検索の解法として,R-木や階層的なGrid分割を使ってデータを格納し,木のノードの組み合わせを探索空間として,根から順にTop-Downに枝刈り探索する方法が提案されている.しかし,このTop-Down方式では,データの分布に依存して探索効率が劣化する問題点がある.本論文では,Top-Down方式において,探索順番の優先順をより適切に制御し,かつ,従来よりもタイト(tight)な下界値を使って探索枝刈りを向上させた探索方式R-DCCを提案し,多様なデータ分布の下でも効率劣化を抑え,探索を高速化できることを示す.