動的簡潔順序木 Dynamic Succinct Ordinal Trees

この論文をさがす

著者

    • 定兼 邦彦 SADAKANE Kunihiko
    • 九州大学大学院システム情報科学研究院 Department of Computer Science and Communication Engineering, Kyushu University

抄録

動的な順序木に対する簡潔データ構造を提案する.簡潔データ構造とは,サイズが表現するデータの情報理論的下限に漸近的に一致するデータ構造であり,n節点の順序木に対する下限は2n-Θ(log n)ビットである.本論文のデータ構造は順序木に対する様々な問合せと,木構造の変更(節点の追加・削除)を効率よく実現する.2つのデータ構造があり,1つはサイズが2n+O(n/log n)ビットで全ての演算をO(log n)時間で行える.もう1つはサイズが2n+O(n log log n/log n)ビットで多くの演算をO(log n/log log n)時間,木構造の変更をO(log n)均し時間で実現する.

This paper proposes succinct data structures for dynamic ordinal trees. Succinct data structures are the ones whose size are asymptotically the same as the information-theoretic lower bounds of data, and the lower bound for n-node trees is 2n-Θ(log n) bits. Data structures of this paper efficiently support various queries and update operations (insertion/deletion of nodes) to ordinal trees. There are two types of data structures; the one is of size 2n+O(n/log n) bits and supports all operations in O(log n) time, and the other is of size 2n+O(n log log n/log n) bits and supports most of the queries in O(log n/log log n) time, and update operations in amortized O(log n) time.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 109(9), 37-41, 2009-04-10

    一般社団法人電子情報通信学会

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

各種コード

  • NII論文ID(NAID)
    110007227306
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    09135685
  • NDL 記事登録ID
    10219994
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ