大規模データ処理のための簡潔データ構造 Succinct Data Structures for Large-Scale Data Processing

この論文にアクセスする

この論文をさがす

著者

抄録

データ列に対して検索効率などを効率化するため,索引を付加することがある.演算を効率化するために,データに対して特定の情報を付加したものを,ここではデータ構造と呼ぶこととする.本稿ではこのようなデータ構造のうち,もとのデータの長さnに対してo(n)程度の付加情報のみを与える,簡潔データ構造と呼ばれる分野について解説する.特に,最も基本的かつ応用範囲の広いビットベクトルに関する簡潔データ構造に焦点を当てる.ビットベクトルBに対して,先頭からi番目までのビット中の1の数を与えるrank1(B i)と,i番目の1の位置を与える select1(B i)という演算は,基本的かつ重要な演算である.これらの演算が定数時間で可能な簡潔データ構造について,具体的なデータ構造とアルゴリズムを紹介し,次に付加するデータサイズの下界についての結果を示し,最後に今後の展望について述べる.

収録刊行物

  • 情報処理

    情報処理 48(8), 899-902, 2007-08-15

    一般社団法人情報処理学会

参考文献:  5件中 1-5件 を表示

被引用文献:  1件中 1-1件 を表示

各種コード

  • NII論文ID(NAID)
    110006368640
  • NII書誌ID(NCID)
    AN00116625
  • 本文言語コード
    JPN
  • 資料種別
    Departmental Bulletin Paper
  • ISSN
    04478053
  • NDL 記事登録ID
    8923108
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-352
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS  IPSJ 
ページトップへ