| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-03-18 13:45 ゼロサプレス型二分決定グラフに基くコンパクトかつ高速な索引構造 ○伝住周平（北大）・川原 純（奈良先端大）・津田宏治（産総研/JST）・有村博紀（北大）・湊 真一（北大/JST）・定兼邦彦（NII）  COMP2012-56 |
|
| 抄録 | （和） | 多くの実問題の中において，集合族を扱う必要に迫られることはままあることである．大規模な集合族を操作することはウェブからの情報抽出や，情報統合，データマイニングに対する重要な基盤技術である．こういった目的に対し，ゼロサプレス型二分決定グラフ（ＺＤＤ）と呼ばれる特別な二分決定グラフ（ＢＤＤ）が使用されることがある．しかしながらＺＤＤを格納するためには巨大なメモリ領域が必要であり，また所属性判定演算も低速であるという問題がある．本論文では静的なＺＤＤを圧縮した索引である集辺式ゼロサプレス型二分決定グラフ（ＤｅｎｓｅＺＤＤ）を導入する．この技術では集合族をコンパクトに索引化するだけではなく所属性判定演算も高速に行えるようになる．さらに，ＤｅｎｓｅＺＤＤと通常のＺＤＤの混成手法により動的な索引を実現する方法も提案する． |
| （英） | 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著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-03-18 13:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2012-56 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.498 |
| ページ範囲 | pp.23-30 |
| ページ数 | 8 |
| 発行日 | 2013-03-11 (COMP) |
[研究会発表申込システムのトップページに戻る]