お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年7月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2013-03-18 13:45
ゼロサプレス型二分決定グラフに基くコンパクトかつ高速な索引構造
伝住周平北大)・川原 純奈良先端大)・津田宏治産総研/JST)・有村博紀北大)・湊 真一北大/JST)・定兼邦彦NIICOMP2012-56
抄録 (和) 多くの実問題の中において,集合族を扱う必要に迫られることはままあることである.大規模な集合族を操作することはウェブからの情報抽出や,情報統合,データマイニングに対する重要な基盤技術である.こういった目的に対し,ゼロサプレス型二分決定グラフ(ZDD)と呼ばれる特別な二分決定グラフ(BDD)が使用されることがある.しかしながらZDDを格納するためには巨大なメモリ領域が必要であり,また所属性判定演算も低速であるという問題がある.本論文では静的なZDDを圧縮した索引である集辺式ゼロサプレス型二分決定グラフ(DenseZDD)を導入する.この技術では集合族をコンパクトに索引化するだけではなく所属性判定演算も高速に行えるようになる.さらに,DenseZDDと通常のZDDの混成手法により動的な索引を実現する方法も提案する. 
(英) In many real-life problems, we are often faced with manipulating families of sets. Manipulation of large-scale set families is one of the important fundamental techniques for web information retrieval, integration, and mining. For this purpose, a special type of binary decision diagram (BDD), called Zero-suppressed BDDs (ZDDs), is used. However there is a problem of huge required space for storing ZDDs and slow membership operations. This paper introduces DenseZDD, a compressed index for static ZDDs. Our technique not only indexes set families compactly but also executes fast membership operations. We also propose a hybrid method of DenseZDD and ordinary ZDDs to make the index dynamic.
キーワード (和) 二分決定グラフ / BDD / ゼロサプレス型二分決定グラフ / ZDD / 簡潔データ構造 / 集合族 / 所属性判定演算 / 集辺式ゼロサプレス型二分決定グラフ  
(英) binary decision diagram / BDD / zero-suppressed binary decision diagram / ZDD / succinct data structure / family of sets / membership operation / DenseZDD  
文献情報 信学技報, vol. 112, no. 498, COMP2012-56, pp. 23-30, 2013年3月.
資料番号 COMP2012-56 
発行日 2013-03-11 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2012-56

研究会情報
研究会 COMP  
開催期間 2013-03-18 - 2013-03-18 
開催地(和) 岐阜大学 
開催地(英) Gifu University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2013-03-COMP 
本文の言語 英語(日本語タイトルあり) 
タイトル(和) ゼロサプレス型二分決定グラフに基くコンパクトかつ高速な索引構造 
サブタイトル(和)  
タイトル(英) Compact and Fast Indices Based on Zero-Suppressed Binary Decision Diagrams 
サブタイトル(英)  
キーワード(1)(和/英) 二分決定グラフ / binary decision diagram  
キーワード(2)(和/英) BDD / BDD  
キーワード(3)(和/英) ゼロサプレス型二分決定グラフ / zero-suppressed binary decision diagram  
キーワード(4)(和/英) ZDD / ZDD  
キーワード(5)(和/英) 簡潔データ構造 / succinct data structure  
キーワード(6)(和/英) 集合族 / family of sets  
キーワード(7)(和/英) 所属性判定演算 / membership operation  
キーワード(8)(和/英) 集辺式ゼロサプレス型二分決定グラフ / DenseZDD  
第1著者 氏名(和/英/ヨミ) 伝住 周平 / Shuhei Denzumi / デンズミ シュウヘイ
第1著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: Hokkaido Univ.)
第2著者 氏名(和/英/ヨミ) 川原 純 / Jun Kawahara / カワハラ ジュン
第2著者 所属(和/英) 奈良先端科学技術大学院大学 (略称: 奈良先端大)
Nara Institute of Science and Technology (略称: NAIST)
第3著者 氏名(和/英/ヨミ) 津田 宏治 / Koji Tsuda / ツダ コウジ
第3著者 所属(和/英) 産業技術総合研究所生命情報工学研究センター/JST ERATO湊離散構造処理系プロジェクト (略称: 産総研/JST)
AIST Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology:JST ERATO Minato (略称: AIST/JST)
第4著者 氏名(和/英/ヨミ) 有村 博紀 / Hiroki Arimura / アリムラ ヒロキ
第4著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: Hokkaido Univ.)
第5著者 氏名(和/英/ヨミ) 湊 真一 / Shin-ichi Minato / ミナト シンイチ
第5著者 所属(和/英) 北海道大学/JST ERATO湊離散構造処理系プロジェクト (略称: 北大/JST)
Hokkaido University/JST ERATO Minato Discrete Structure Manipulation System Project (略称: Hokkaido Univ./JST)
第6著者 氏名(和/英/ヨミ) 定兼 邦彦 / Kunihiko Sadakane / サダカネ クニヒコ
第6著者 所属(和/英) 国立情報学研究所 (略称: NII)
National Institute of Informatics (略称: NII)
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2013-03-18 13:45:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2012-56 
巻番号(vol) IEICE-112 
号番号(no) no.498 
ページ範囲 pp.23-30 
ページ数 IEICE-8 
発行日 IEICE-COMP-2013-03-11 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会