3 0 0 0 OA 単一始点最短路問題(SSSP)線形時間アルゴリズムの実際的評価
- 著者
- 浅野 泰仁 今井 浩
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL)
- 巻号頁・発行日
- vol.1998, no.41(1998-AL-062), pp.1-8, 1998-05-20
単一始点最短路問題(SSSP)を解くためのアルゴリズムとしては、Dijkstraのアルゴリズムが有名である。過去、Dijkstraのアルゴリズムを高速化する研究が多く行われてきたが、ソート問題に相当するボトルネックのため、線形時間を達成することはできなかった1997年、M.Thorupが整数枝重み無向グラフでのSSSPを線形時間で解くアルゴリズムを発表した。しかしこのアルゴリズムで使用されている複雑なデータ構造のいくつかは理論通りには実装できない。本研究では、Thorupのアルゴリズムを現在の計算機上で実装するための変更を提案した上で、実際にThorupのアルゴリズムの実装をおこなった。さらに、既存のアルゴリズムとの比較実験および各部分の実行時間計測をおこなった。
3 0 0 0 単一始点最短路問題(SSSP)線形時間アルゴリズムの実際的評価
- 著者
- 浅野 泰仁 今井 浩
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
- 巻号頁・発行日
- vol.1998, no.41, pp.1-8, 1998-05-20
- 参考文献数
- 6
単一始点最短路問題(SSSP)を解くためのアルゴリズムとしては、Dijkstraのアルゴリズムが有名である。過去、Dijkstraのアルゴリズムを高速化する研究が多く行われてきたが、ソート問題に相当するボトルネックのため、線形時間を達成することはできなかった1997年、M.Thorupが整数枝重み無向グラフでのSSSPを線形時間で解くアルゴリズムを発表した。しかしこのアルゴリズムで使用されている複雑なデータ構造のいくつかは理論通りには実装できない。本研究では、Thorupのアルゴリズムを現在の計算機上で実装するための変更を提案した上で、実際にThorupのアルゴリズムの実装をおこなった。さらに、既存のアルゴリズムとの比較実験および各部分の実行時間計測をおこなった。SSSP is one of the well known classic problems in graph theory and Dijkstra's algorithm for SSSP is also quite popular. Several improvements of Dijkstra's algorithm have been studied, however, they could not accomplish a linear-time owing to its sorting bottleneck. In 1997, M.Thorup proposed a linear-time algorithm for the SSSP on undirected and integer edge weight graph. However, we can not implement this algorithm naively on computers today since the data structures used in the algorithm need a word of huge length. We propose modifications to implement Thorup's algorithm and implement this algorithm. Moreover, compare execution times of the implementation and famous algorithms.
1 0 0 0 OA 集合知とウェブ知識の有機的循環化技術の開発
本研究では,集合知をさらなる発展段階に導くための基盤技術として,(1) 集合知の情報構造を利用してウェブから集合知を補完する手法と,(2) 得られた知識を整理して提示する手法を構築することを目指した.成果は,(1)としては,Wikipediaに不足しているテキスト情報をウェブから取得する手法,Wikipediaに不足している画像情報、特にエンティティ間の関係を説明するものをウェブから取得する方法,などの提案であり,(2)としてはウェブから取得した、エンティティ間の関係を説明するような画像をWikipediaの知識と合わせて提示する方法などの提案である.
1 0 0 0 OA ソーシャルコンテンツの発展過程の分析と応用
1 0 0 0 OA 時間グラフパターンを用いたWeb解析
- 著者
- 押野 泰平 浅野 泰仁 吉川 正俊
- 雑誌
- 研究報告データベースシステム(DBS)
- 巻号頁・発行日
- vol.2010-DBS-151, no.27, pp.1-8, 2010-11-05
Web の構造的特徴に基づくグラフパターンは,web 解析や情報検索に重要な役割を果たしている.我々は web の構造情報だけでなく時間情報をも用いた新たなグラフパターンとして,時間グラフパターンというものを提案し研究を行ってきた.これまでの研究では,頻出グラフパターンを列挙することによってサンプルグラフ集合から時間グラフパターンをマイニングする手法を提案した.本稿ではマイニングされたパターンを用いた web 解析として,web サイトを話題の盛り上がり時における三つの役割として一次情報源,盛り上げ役,まとめ役に分類することを試みる.新たなグラフマイニング手法を用いることで,これまで達成できなかった三つの分類が可能になったことを示す.