10 0 0 0 大規模データ処理のための簡潔データ構造
- 著者
- 定兼 邦彦
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理 (ISSN:04478053)
- 巻号頁・発行日
- vol.48, no.8, pp.899-902, 2007-08-15
- 被引用文献数
- 1
データ列に対して検索効率などを効率化するため,索引を付加することがある.演算を効率化するために,データに対して特定の情報を付加したものを,ここではデータ構造と呼ぶこととする.本稿ではこのようなデータ構造のうち,もとのデータの長さnに対してo(n)程度の付加情報のみを与える,簡潔データ構造と呼ばれる分野について解説する.特に,最も基本的かつ応用範囲の広いビットベクトルに関する簡潔データ構造に焦点を当てる.ビットベクトルBに対して,先頭からi番目までのビット中の1の数を与えるrank1(B i)と,i番目の1の位置を与える select1(B i)という演算は,基本的かつ重要な演算である.これらの演算が定数時間で可能な簡潔データ構造について,具体的なデータ構造とアルゴリズムを紹介し,次に付加するデータサイズの下界についての結果を示し,最後に今後の展望について述べる.
2 0 0 0 OA 全二分木の簡潔な表現
- 著者
- 馬場 雅大 小野 廣隆 定兼 邦彦 山下 雅史
- 雑誌
- 研究報告アルゴリズム(AL)
- 巻号頁・発行日
- vol.2010-AL-129, no.1, pp.1-8, 2010-02-26
大規模なデータを効率よく扱うために圧縮されたデータ上で高速な操作を行える簡潔データ構造が提案されてきた.本稿ではパトリシアトライなどに使われる全二分木に焦点を当てる.提案する全二分木の簡潔表現のサイズは n+o(n) ビットであり,右の子へ巡回するといった操作を定数時間で行うことができる.また接尾辞木 (ST) を全二分木に変換することで圧縮可能であることを示す.
- 著者
- 伝住 周平 有村 博紀 定兼 邦彦
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers (ISSN:09135693)
- 巻号頁・発行日
- vol.97, no.12, pp.1080-1085, 2014-12
大規模な文字列データの操作は,文字列処理の分野で最も重要な課題の一つである.本稿では,文字列集合をコンパクトに圧縮し様々な操作を可能とする系列二分決定グラフ(系列BDD,SeqBDD)を紹介し,関連するパターン照合技術について紹介する.この系列BDDは,文字列データに拡張したZDDの一種であるが,同時に,従来から自然言語処理や文字列処理分野で研究されてきたトライや,有限オートマトン,接尾辞グラフなどのテキスト索引のためのデータ構造とも密接な関連を持つ.これら既存のデータ構造との関係や,近年発展が著しい簡潔データ構造と関連した話題についても述べる.
2 0 0 0 OA ルビーによる高生産な超並列・超分散計算ソフトウェア基盤
本研究開発では、関数型オブジェクト指向言語であるRubyを拡張し、HPC向け高生産言語としてHPC Ruby言語を確立した。また、Rubyの特徴である計算環境の統合を生かし、HPC情報環境における新しいソフトウェア体系を実現した。HPC向け新言語の普及のため地球科学分野、天文分野、離散最適化分野においてRuby言語モデルを用いて問題定式化し、Rubyの科学技術計算位おける優位性を示した。分散実行環境の実証研究では、日米欧を100Gbpsインターネットで結び、その90%を高効率利用する通信方式を確立し、実験により実証した。これらの成果を総合し、Rubyを中心とした科学技術計算の体系を確立した。
1 0 0 0 ゲノム配列の高次圧縮・索引構築と高次幾何構造解析による知識発見
ゲノムデータベースからの知識発見のためのアルゴリズムとデータ構造に関する研究を行った.まず,ゲノム配列データベースからの高速パタン検索のアルゴリズムとデータ構造を開発した.索引としては既存の圧縮接尾辞配列を用いたが,新しいアルゴリズムにより従来の30倍の速度での検索が可能になった.次に,2つの長いゲノム配列のアラインメントを計算するための手法である,MUM(Maximal Unique Match)を列挙する省スペースなアルゴリズムを開発した.配列の長さをnとすると,既存手法ではO(n log n)ビットのスペースが必要であったが,本研究ではこれをO(n)ビットに圧縮した.これにより,ヒトの全DNA配列2つのMUMの計算がメモリ4GBのPC1台を用いて約6時間で計算できた.また,ヒトとマウスの間の共通部分については約24時間で計算できた.データベースからの知識発見のために,データベース中の複数の属性間の最適相関ルールを求める高速アルゴリズムを開発した.最適とは,支持率を固定した場合の最大確信度ルールまたは確信度を固定したときの最大支持率ルールを表す.従来手法では2値属性のみしか効率良く扱えなかったが,本研究の手法では数値属性に対して効率良く動作する.また,数値属性間の最適相関ルールを拡張し,様々な確信度に対する最適領域をピラミッド型の図形で表現する方法を提案し,その効率の良い計算法を提案した.これを最適ピラミッドによる相関ルール表現と呼ぶ.これを用いることでデータベースから抽出した知識を簡潔に表現することができ,過学習の回避もできる.また,ピラミッドを用いてデータの可視化を行うこともできる.
1 0 0 0 OA 大規模データ処理のための簡潔データ構造
データ列に対して検索効率などを効率化するため,索引を付加することがある.演算を効率化するために,データに対して特定の情報を付加したものを,ここではデータ構造と呼ぶこととする.本稿ではこのようなデータ構造のうち,もとのデータの長さnに対してo(n)程度の付加情報のみを与える,簡潔データ構造と呼ばれる分野について解説する.特に,最も基本的かつ応用範囲の広いビットベクトルに関する簡潔データ構造に焦点を当てる.ビットベクトルBに対して,先頭からi番目までのビット中の1の数を与えるrank1(B i)と,i番目の1の位置を与える select1(B i)という演算は,基本的かつ重要な演算である.これらの演算が定数時間で可能な簡潔データ構造について,具体的なデータ構造とアルゴリズムを紹介し,次に付加するデータサイズの下界についての結果を示し,最後に今後の展望について述べる.
1 0 0 0 OA 道路ネットワーク上の経路探索クエリのための枝刈りツリーラベリングアルゴリズム
- 著者
- 小池 敦 定兼 邦彦
- 雑誌
- 研究報告アルゴリズム(AL) (ISSN:21888566)
- 巻号頁・発行日
- vol.2016-AL-159, no.7, pp.1-8, 2016-09-16
本論文では,道路ネットワーク上の経路探索クエリについて,新しいアルゴリズムを提案する.提案手法は Hub Labeling や Pruned Highway Labeling と同様,ラベリング法に基づくものである.前処理において,入力グラフを複数の木に分解し,各ノードが hub ノード集合の代わりに木の ID の集合を保持することでラベルサイズを削減させる.本論文ではアルゴリズムを実装し,米国の道路ネットワークを用いて評価を行うことで,提案アルゴリズムの有効性を示す.
1 0 0 0 OA 実際的簡潔データ構造の開発と大量データ活用
1 0 0 0 OA 情報爆縮基盤技術
- 著者
- 竹田 正幸 定兼 邦彦 坂本 比呂志 瀧本 英二 坂内 英夫 稲永 俊介 喜田 拓也 畑埜 晃平 井 智弘 中島 祐人 成澤 和志
- 出版者
- 九州大学
- 雑誌
- 基盤研究(A)
- 巻号頁・発行日
- 2013-04-01
爆縮とは工学用語で,爆発の圧力が;外側ではなく内側へ集中する現象をいい,通常では得難い物理現象を発生させるために利用される.本研究では,膨れ上がるデータを爆発的に凝縮することにより,(i) データ量削減, (ii) データ処理の高速化,(iii) 知識獲得の三つを達成する基盤技術の確立を目指し,これを情報爆縮 (information implosion) と名付けた.情報爆縮基盤技術の確立のために,(A)高速データストリーム圧縮アルゴリズム,(B)圧縮データ上の高速データ処理アルゴリズム,(C)大規模データ解析アルゴリズムという3つの研究項目をおいて研究開発を行い多くの成果を得た.
1 0 0 0 圧縮接尾辞配列を用いた文字列アルゴリズム
- 著者
- 定兼 邦彦
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
- 巻号頁・発行日
- vol.2000, no.84, pp.73-80, 2000-09-21
全文検索のための索引である接尾辞配列は,他の全文検索索引と比較すると省スペースであるが,転置ファイルのような単語索引と比較するとサイズが大きい.この問題を解決するために圧縮接尾辞配列が提案されたが,検索にはテキスト自身も必要であるため,索引サイズはテキストよりも小さくならない.本稿では圧縮接尾辞配列を用いた検索アルゴリズムを,テキスト自身が不要になるように変更する.また,テキスト全体やその一部を圧縮接尾辞配列から復元するアルゴリズムを提案する.これにより,テキストの圧縮と高速な検索の両立が可能となる.A compressed text database based on the compressed suffix array is proposed. The compressed suffix array of Grossi and Vitter occupies only O(n) bits for a text of length n; however it also uses the text itself that occupies O(n log|Σ|) bits for the alphabet Σ. On the other hand, our data structure does not use the text itself, and supports important operations for text databases: inverse, search and decompress. Our algorithms can find occ occurrences of any substring P of the text in O(|P|log n + occ log^ε n) time and decompress a part of the text of length l in O(l+log^ε n) time for any fixed 1 > ε > 0. Our data structure occupies only 1/εnH_0 + n(6+3logH_0)<log^εn>/<log^εn-1>+2n+|Σ|log|Σ|+o(n) bits where H_0〓log|Σ| is the order-0 entropy of the text.
1 0 0 0 省スペースな圧縮接尾辞配列構成アルゴリズム
- 著者
- 定兼 邦彦 宋永健 姚兆明 林徳華
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
- 巻号頁・発行日
- vol.2001, no.115, pp.19-26, 2001-11-27
文字列検索のための索引として接尾辞配列が有名であるが,そのサイズが問題となっている.圧縮接尾辞配列はそれを圧縮したもので,通常は元の文字列よりもサイズが小さくなる.ただし圧縮接尾辞配列を構成するアルゴリズムとしては一旦接尾辞配列を構成するものしか存在しないため,一時的だが大量のメモリが必要となる.本研究では長さ n の文字列に対し,$O(n)$ ビットの一時記憶を用いる O(n|Σ|log n)$ 時間 (|Σ|はアルファベットサイズ)のアルゴリズムを提案する.このアルゴリズムは短い文字列に対する圧縮接尾辞配列から長い文字列に対するものを徐々に作成するものになっており,データの追加を容易に行える点も利点である.Though the suffix array is now famous as an index for string matching, it has a problem of its size. The compressed suffix array is a compressed version of the suffix array whose size is usually smaller than the size of the string. However all known algorithms construct the compressed suffix arrays via uncompressed suffix arrays, which temporarily occupy huge amount of memory. This paper proposes an O(n|Σ| log n) time algorithm to construct a compressed suffix array of a string of length n on alphabet Σ using only O(n) bits temporal space. This is an incremental algorithm, which construct the compressed suffix array of a concatenation of a character and a string from that of the string. Therefore this algorithm also has the merit of appending data quickly.
1 0 0 0 圧縮接尾辞配列構築アルゴリズムの改良
- 著者
- 韓 永楷 定兼 邦彦 宋 永健
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.104, no.55, pp.1-7, 2004-05-13
文字列検索のためのデータ構造としては接尾辞本,接尾辞配列などが有名であるが,これらにはデータ構造の必要とする記他領域が大きいという欠点がある.近年GrossiとVitterによって提案された圧縮接尾辞配列は検索速度を落とすことなく接尾辞配列を圧縮したものであり,サイズは長さnの文字列に対してO(nlog|A|)ビット(Aはアルファベット)である.これは文字列のサイズの線形となっている.圧鎔接尾辞配列を構築するアルゴリズムとして,Honらの提案したO(nlog|A|)ビットの一時的な記他領域を使用するO(nloglogUI)時間アルゴリズムが存在する,これは領域に関しては最適だが時間に関しては最適ではない,本論文ではアルファベットサイズが小さいとき(log|A| = O((log log n)^<1-ε>))に0(n)時間で動くアルゴリズムを提案する.
1 0 0 0 文書データベースへの効率的な索引付けとその更新に関する研究
- 著者
- 後藤 隆元 小野 廣隆 定兼 邦彦 山下 雅史
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.105, no.72, pp.1-8, 2005-05-13
計算機の性能の向上や, インターネットの普及により, 我々が扱うデータの量は急速に増加している.そしてそれに伴い, 大きなデータの中から必要なデータを探し出す機会も多くなっている.しかし, 扱うデータの量が増えるにつれて検索に必要な時間計算量や空間計算量も増加するため, より効率の良い検索アルゴリズムが求められている.一般に, 文字列検索を行う際にはあらかじめ対象となるファイルに対して索引付けを行って検索しやすくしている.そこで, 本研究では複数のファイルを格納した文書データベースに対して, 圧縮接尾辞配列を用いた索引付けを行うことにより, 時間的にも空間的にも効率が良く, 検索漏れが生じない文字列検索アルゴリズムを提案する.