大規模データ処理のための簡潔データ構造

• 定兼, 邦彦

書誌事項

タイトル別名

• ダイキボ データ ショリ ノ タメノ カンケツ データ コウゾウ
• 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

  東京 : 情報処理学会 ; 1960-

キーワード

• 解説

詳細情報

• CRID: 1050001337898050048
• NII論文ID: 110006368640
• NII書誌ID: AN00116625
• ISSN: 04478053
• NDL書誌ID: 8923108
• Web Site: http://id.nii.ac.jp/1001/00065880/
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I8923108
• 本文言語コード: ja
• 資料種別: departmental bulletin paper
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles