時々刻々と成長するグラフのための直径モニタリング
スポンサーリンク
概要
- 論文の詳細を見る
本論文では時々刻々と成長するグラフの直径を検出し続ける問題を対象とする.グラフの直径とはグラフにおいて最も長いノード間の距離である.この問題はP2Pネットワークにおいて検索性能を向上させるなど,様々なアプリケーションに応用することができる.提案手法は時々刻々と成長するグラフの直径を効率的かつ正確に検出し続けることができる.提案手法は,(1)直径を構成しえないノードを枝刈りするアイデアと,(2)新たにグラフに追加されたノードからの距離を用いて直径を構成するノードのペアを更新するアイデアから構成される.本論文では理論解析によって提案手法が正確に直径を検出し続けることができることを示す.また大規模なグラフを用いた実験により提案手法が従来用いられている手法より大幅に高速な検出が可能であることを示す.
- 2013-12-27
著者
-
喜連川 優
東京大学生産技術研究所
-
喜連川 優
東京大学
-
喜連川 優
東大
-
Kitsuregawa Masaru
Univ. Tokyo
-
Kitsuregawa M
Univ. Tokyo Tokyo Jpn
-
藤原 靖宏
NTTソフトウェアイノベーションセンタ
-
鬼塚 真
NTTソフトウェアイノベーションセンタ
-
喜連川 優
東京大学|国立情報学研究所
関連論文
- 多周期的更新アクセスに適した二次記憶管理技法 : 連続的Webクローリングへの適用(ファイル編成,情報爆発論文)
- 編集にあたって(平成21年度長尾真記念特別賞紹介)
- グリーンレプリケーション : 二次系ディスクストレージの省電力化(ストレージ 並列分散データベース,データ工学論文)
- 編集にあたって(平成21年度論文賞の受賞論文紹介)
- 大規模ウェブテキストからの片仮名用言の自動獲得(テキストマイニング,データ工学論文)
- ATM結合PCクラスタにおける動的リモートメモリ利用方式を用いた並列データマイニングの実行
- 並列DBMSに於ける動的負荷分散機構の実装
- 一般化相関ルールマイニングの並列処理方式における統計情報を用いた候補分割負荷分散手法の評価
- 大規模PCクラスタにおける並列相関ルールマイニング処理方式の評価
- ATM結合PCクラスタにおける並列データマイニングの実装とTCP再送機構の性能解析
- トレンドを考慮した検索クエリの分類手法の一検討
- 2.50年後の情報社会を支えるIT基盤(情報処理技術の未来地図,50周年記念特集号)
- 情報爆発時代における情報大航海プロジェクト
- 情報大航海
- ウェブコミュニティチャートとウェブディレクトリの比較に関する一考察
- IFIP-情報処理国際連合-近況報告(委員会から)
- ボーンデジタル時代におけるウェブアーカイブとその活用基盤としてのSocio-Sense(Webアーカイビングの現状と課題)
- IFIP-情報処理国際連合-近況報告
- iSCSIネットワークストレージにおけるファイルアクセス性能に関する考察(ストレージ2, 夏のデータベースワークショップDBWS2005)
- iSCSIネットワークストレージにおけるファイルアクセス性能に関する考察(ストレージ2, 夏のデータベースワークショップ2005)
- SAN結合PCクラスタにおけるストレージ仮想化機構を用いた動的負荷分散並びに動的資源調整の提案とその評価(データベース)
- ITの進展と法制度の非想定領域 : 著作権法一部改正,47-6,47-7による検索エンジンの合法化について(研究開発における情報利用と著作権)
- 情報爆発時代における情報管理・融合・活用基盤(情報爆発時代に向けた新しいIT基盤技術の研究)
- 情報爆発時代に向けた新しいIT基盤技術の研究(情報爆発時代に向けた新しいIT基盤技術の研究)
- コンテンツの生産・活用に関する研究 : 科研「情報学」プロジェクトのコンテンツ研究を振り返って(「情報学を創る」-科研プロジェクトがめざしたもの)
- 大規模Webアーカイブ更新クローラにおけるスケジューリング手法の評価(Web検索・Webアーカイブ,データ工学論文)
- 50周年記念全国大会を振り返って : 7,150人もの多のくの方々にご参加いただきお礼申し上げます(記念大会が示した情報処理の未来-情報処理学会創立50周年記念(第72回)全国大会報告-)
- 1.SlothLib/EaRDB : マイサーチエンジン開発環境支援(パートII:情報分野研究者のためのオンリーワン共有イノベーションプラットフォーム,情報爆発時代におけるわくわくするITの創出を目指して)
- グリーンレプリケーション : 二次系ディスクストレージの省電力化
- 最近の二次記憶装置 : ディスクアレイ (<連載講座> 計算機の記憶システム 7)
- 多周期的更新アクセスに適した二次記憶管理技法 : 連続的 Web クローリングへの適用
- コラボラティブグリーンストレージ : データベースシステムとの連携によるディスクストレージ省電力化の構想(インターネットと環境・エコロジー,インターネットと環境・エコロジー,一般)
- 地球水循環データアーカイブシステムとユーザインタフェースの構築(データ可視化, 夏のデータベースワークショップDBWS2005)
- AIRSデータ可視化システムにおける多種データ重ね合わせ表示機能の開発(データ可視化, 夏のデータベースワークショップDBWS2005)
- 地球水循環データアーカイブシステムとユーザインタフェースの構築(データ可視化, 夏のデータベースワークショップ2005)
- AIRSデータ可視化システムにおける多種データ重ね合わせ表示機能の開発(データ可視化, 夏のデータベースワークショップ2005)
- 情報爆発論文特集の発行にあたって
- 部分マイグレーション機構を有する3次記憶ファイルシステムPFSの8ミリテープアーカイブ装置への実装とその性能評価
- 2ウェイマージ機能を有するオメガネットワーク
- Webアクセスログとその利活用(ソーシャルネットワーク時代のWebインタラクション)
- 大規模日本語Webアーカイブの構築とその分析 (特集 データマネジメント技術)
- 10.Socio Sense : 過去9年に及ぶWebアーカイブから社会の動きを読む(第2部:情報の高信頼蓄積・検索技術等の開発,学と産の連携による基盤ソフトウェアの先進的開発)
- 5L-5 大規模Webアーカイブにおけるコンテンツ解析支援機構(リーディングプロジェクト e-society:WebアーカイブとWebデータ解析技術,一般セッション,リーディングプロジェクト e-society)
- 特定言語で記述されたwebページの選択的収集手法とその評価(Web マイニング・Web情報検索,データ工学論文)
- 共有ストレージプールを用いた並列データベース処理に於けるオンデマンド資源調節
- 共有ストレージプールを用いた並列データベース処理に於けるオンデマンド資源調節
- 4K-5 並列DBMS: DBKernelにおける動的負荷分散機構の評価
- 並列DBMSに於ける動的負荷分散機構の実装
- 並列SQLによる大規模PCクラスター上の相関ルールマイニング : C実装プログラムとの性能比較
- 並列DBMSにおける動的負荷分散機構 : 負荷情報収集方式の検討
- 概念階層を考慮した相関ルールマイニングの関係データベース管理システム上での実現
- 並列DBMSにおける動的負荷分散機構 : 負荷情報収集に関する一考察
- 並列関係データベース処理システムに於ける動的負荷分散:実装設計
- アウトオブオーダー型データベースエンジンOoODEの構想と初期実験
- 9.ストレージフュージョン : ストレージシステムとデータベース管理システムの融合(第2部:情報の高信頼蓄積・検索技術等の開発,学と産の連携による基盤ソフトウェアの先進的開発)
- 6L-3 Storage Fusion : 自己再編成ストレージシステムの高度化に関する一考察(リーディングプロジェクト e-society: Strage Fusion,一般セッション,リーディングプロジェクト e-society)
- 6L-2 データベース処理を意識したディスクアレイ省電力化のための電力消費モデルの構築(リーディングプロジェクト e-society: Strage Fusion,一般セッション,リーディングプロジェクト e-society)
- 6L-1 Storage Fusion : データベース処理を意識したディスクストレージ省電力化の一考察(リーディングプロジェクト e-society: Strage Fusion,一般セッション,リーディングプロジェクト e-society)
- オンライン構造劣化モニタを用いたデータベース再編成支援(夏のデータベースワークショップ2007(データ工学,一般))
- オンライン構造劣化モニタを用いたデータベース再編成支援(データベース技術,夏のデータベースワークショップ2007(データ工学,一般))
- データベースにおけるリアルタイム構造劣化監視機構の試作(ストレージ)
- データベース更新差分を用いた範囲検索のIOコスト推定(高性能システム, 夏のデータベースワークショップDBWS2005)
- 分散共有メモリ計算機上におけるデータスキューに対する結合演算の性能解析
- 分散共有メモリ計算機上におけるデータスキューに対する結合演算の性能解析
- 分散共有メモリ計算機における並列ハッシュ結合演算処理の性能解析 (高度データベース論文特集)
- 分散共有メモリ並列計算機における関係結合演算の性能
- 共有メモリ型計算機上でのトランスポーズドファイルを用いた並列関係問合せ処理の実装方式とその評価
- 分散共有メモリ計算機における並列ハッシュ結合演算処理方式の設計と実装
- 共有メモリマルチプロセッサ上でのトランスポーズドファイルを用いた並列関係問合せ処理
- 分散共有メモリ計算機における並列ハッシュ結合演算処理方式の設計と実装
- 共有メモリマルチプロセッサ上でのトランスポーズドファイルを用いた並列関係問合せ処理
- トランスポーズドファイル上での並列結合演算処理方式に関する一考察
- 分散共有メモリ計算機における並列ハッシュ結合演算方式の実装
- 分散共有メモリ計算機上における並列ハッシュ結合演算処理方式の一考察
- 並列関係データベースシステムにおけるバッチ問合せ処理最適化技法の検討
- 並列計算機AP1000DDVにおける多重結合演算の実装とその評価
- 並列関係データベースシステムにおける多重問合せ最適化に関する一考察
- 並列データベースシステムにおける多重結合演算処理の最適化とその評価
- 並列データベースシステムにおける多重結合演算の静的最適化技法の一考察
- GN ハッシュ結合方式とその評価
- 並列データベースシステムにおける多重結合演算処理の最適化
- Webマイニングにおける語義曖昧性解消のための擬似負例を用いた能動学習
- 5L-6 ウェブからの分析対象文書抽出手法の検討(リーディングプロジェクト e-society:WebアーカイブとWebデータ解析技術,一般セッション,リーディングプロジェクト e-society)
- オンライントランザクション処理におけるDynamic Voltage and Frequency Scalingの消費電力削減効果に関する実験的考察(実世界データ処理,モバイルデータベースとGIS及び一般)
- 1.キーワードサーチを超える情報爆発サーチ : 自然言語処理で価値ある未知をマイニング(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- 並列SQLサーバSDC-IIにおけるトランスポーズ型ファイル編成適用の検討
- 並列SQLサーバSDC-IIにおけるバッチ問合せ処理方式
- スーパーデータベースコンピュータSDC-IIのバケット平坦化ネットワークにおける負荷特性の評価
- スーパーデータベースコンピュータSDC-IIにおける不均一データ分布での結合演算処理に対する性能評価
- スーパーデータベースコンピュータSDC-IIにおけるシステムソフトウェアの設計と実装
- スーパーデータベースコンピュータSDC-IIにおける並列結合演算処理に関する性能評価
- スーパーデータベースコンピュータSDC-IIのデータネットワークにおけるバケット平坦化機構の実装と評価
- スーパーデータベースコンピュータSDC2における多重結合演算の実装と評価
- スーパーデータベースコンピュータ第二版(SDC2))におけるマルチジョインの実装方式
- スーパーデータベースコンピュータ第二版(SDC2)におけるシステムソフトウェアの構成
- スーパーデータベースコンピュータ(SDC)におけるデータネットワークの論理設計
- スーパーデータベースコンピュータ(SDC)における性能可視化ツール
- スーパーデータベースコンピュータ(SDC)におけるデータ流制御方式の評価
- スーパーデータベースコンピュータ(SDC)のバスモニタ
- スーパーデータベースコンピュータ用バケット平坦化オメガネットワークの非同期動作特性