文献

J-GLOBAL ID：201302274647032149   整理番号：13A0783801

大規模疎行列を扱うZDDの演算を高速化する飛び越しリンク構造

Auxiliary Skip Links for Quick Traversal of ZDDs to Manipulate Large-Scale Sparse Matrices

著者 (2件)： 湊真一 (北大 大学院情報科学研究科) ,  湊真一 (JST-ERATO)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 498(COMP2012 52-62)  ページ： 15-22  発行年： 2013年03月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ZDD(ゼロサプレス型二分決定グラフ)は,大規模な組合せ集合をコンパクトに表現し,高速に演算処理する技法として広く利用されている。本研究では,飛び越しリンク構造を用いて,大規模疎行列を扱うZDDの検索処理を高速化する手法を提案する。本稿では提案手法の平均計算量を解析し,最適なパラメータ設定値を明らかにする。本手法はZDDの各節点に飛び越しリンクを1個追加するだけで,既存のZDD処理系にも容易に実装できる。実験の結果,数千アイテムからなる大規模疎行列の例題に対して,検索処理を数十倍高速化することができた。本手法によりZDD処理系の有効な応用範囲がさらに広がると期待される。(著者抄録)

シソーラス用語： *二分決定グラフ ,  *スパース行列 ,  大規模系 ,  *情報検索 ,  高速化 ,  高速アルゴリズム ,  節点 ,  実装設計 ,  評価試験 ,  性能評価
準シソーラス用語： *ZDD【グラフ】 ,  *大規模疎行列

分類 (3件)： グラフ理論基礎  (IA02020S) ,  数値計算  (JE02000J) ,  検索技術  (AC06020S)

タイトルに関連する用語 (6件)： 大規模 ,  疎行列 ,  ZDD ,  高速化 ,  飛び越し ,  リンク構造