文献

J-GLOBAL ID：201402264810712308   整理番号：14A0647750

部分領域の全対経路索引を用いた経路スカイライン問合せ処理法の提案

Route Skyline Query Processing using Regional All-Pairs Path Indices

著者 (4件)： 蒲原智也 (関西大 先端科学技術推進機構) ,  小池実 (関西大 大学院総合情報研究科) ,  壷内貴弘 (関西大 総合情報) ,  上島紳一 (関西大 大学院総合情報研究科)
資料名： 日本データベース学会論文誌  (Journal of the DBSJ)
巻： 12  号： 3  ページ： 13-18  発行年： 2014年02月28日 
JST資料番号： L5754A  ISSN： 1883-1060  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,多次元コストグラフに対する経路スカイラインの問合せ処理法について議論する。経路スカイライン問合せは,利用者の選好を表すコスト関数に対するパレート最適な経路集合を予め抽出する操作であり,経路計画,散策計画,施設配置,工程管理,グラフ航行等の様々な分野での応用が期待できる。経路スカイライン問合せは,多次元データ集合に対するスカイライン間合せと異なり,グラフ探査処理を必要とする。ここでは,経路スカイラインの任意の部分経路がスカイラインであることに着目し,グラフ分割で得られた部分領域の全対経路索引を生成して,グラフ探査における展開途中の経路の刈込み処理を行う2段階のアルゴリズムを提案する。事前処理では,グラフ分割により得られた部分領域に対する経路索引として全ノード対に対して経路スカイラインを求め,探査実行処理では経路索引を用いて経路スカイラインを構成的に計算する。提案手法を評価するため,国土地理院発行の数値地図を用いてシミュレーションを行い,事前処理時間,探査実行時間,属性数などの影響等について提案手法,ナイーブな探査法,距離索引を用いた探査手法と定量的に比較する。(著者抄録)

シソーラス用語： *経路選定 ,  シミュレーション ,  グラフ ,  *質問処理 ,  *経路探索 ,  *通信操作
準シソーラス用語： *経路スカイライン問合せ ,  多次元コストグラフ

分類 (2件)： 人工知能  (JE08000Z) ,  ネットワーク法  (KA03040X)

引用文献 (19件)：

• S. Börzsönyil, D. Kossmann, K. Stocker, The Skyline Operator, IEEE ICDE, pp.421-430 (2001)
• D. Kossmann, F. Ramsak, S. Rost, Shooting stars in the sky: An online algorithm for skyline queries, VLDB, pp.275-286 (2002)
• P. Wu, C. Zhang, Y. Feng, B. Y. Zhao, D. Agrawal, A. E. Abbadi, Parallelizing Skyline Queries for Scalable Distribution, EDBT, pp.112-130 (2006)
• S. Wang, B. C. Ooi, A. K. H. Tung, L. Xu, Efficient Skyline Query Processing on Peer-to-Peer Networks, IEEE ICDE, pp.1126-1135 (2007)
• A. Vlachou, C. Doulkeridis, Y. Kotidis, Angle-based Space Partitioning for Efficient Parallel Skyline Computation, ACM SIGMOD, pp.227-238 (2008)

タイトルに関連する用語 (5件)： 経路 ,  索引 ,  スカイライン ,  問合せ処理 ,  提案