大規模データ処理のための離散構造処理系

大規模データ処理のための離散構造処理系

ダイキボ データ ショリ ノ タメノ リサン コウゾウ ショリケイ

川原純

生駒 : 奈良先端科学技術大学院大学, 2013.4

授業アーカイブ

巻号情報

全1件
No. 刷年 所在 請求記号 資料ID 貸出区分 状況 予約人数

1

  • LA-I-R[MPDASH][Mobile]

M010741

内容紹介

本講演では,大規模データ処理のための離散構造処理系,特に,集合族をコンパクトに効率良く表現するためのデータ構造であるゼロサプレス型二分決定グラフ(ZDD) について解説を行う.ZDDを用いると,与えられたグラフの様々な種類 の部分グラフを効率良く列挙し,索引化することが可能となる.例えば,15 × 15 グリッドグラフ上の左上隅から右下隅に至るパス227449714676812739631826459327989863387613323440(=2.27×10^47)本を 数分で列挙, 保存し,それらの中から指定した条件を満たすパスを高速に検索することができる.本手法の汎用化について,講演者の最近の研究も紹介する.In this presentation, I will talk about discrete structure manipulation systems for large-scale data processing, especially the zero-suppressed binary decision diagram (ZDD), which is a compact and efficient data structure representing a family of sets. For a given graph, it is possible to enumerate and index many kinds of subgraphs of the graph by using a ZDD. For example, 227449714676812739631826459327989863387613323440 (=2.27x10^47) nonintersecting paths joining opposite corners of a 15x15 grid graph can be enumerated and stored in a few minutes, and paths satisfying given conditions can quickly be searched from the set of these paths. I will also introduce my recent work for generalizing this method.

詳細情報

刊年

2013

形態

電子化映像資料(38分09秒)

別書名

Discrete Structure Manipulation Systems for Large-Scale Data Processing

シリーズ名

情報科学研究科・ゼミナール講演 ; 平成25年度

注記

講演者所属: 奈良先端科学技術大学院大学 情報科学研究科 ソフトウェア工学研究室

講演日: 平成25年4月17日

講演場所: 情報科学研究科大講義室L1

標題言語

日本語 (jpn)

本文言語

日本語 (jpn)

著者情報

川原, 純 (カワハラ, ジュン)