トライにおける逆方向遷移可能かつコンパクトな配列構造

• Item type: SIG Technical Reports(1)
• 公開日: 2015-07-29
• タイトル: トライにおける逆方向遷移可能かつコンパクトな配列構造
• タイトル / 言語: en
• タイトル: A Compact Array Structure with Reverse Traversal in a Trie
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: アルゴリズム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Intelligent Systems, Tokushima University
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Intelligent Systems, Tokushima University
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Intelligent Systems, Tokushima University
• 著者所属(英): en
• 著者所属(英): Department of Information Science and Intelligent Systems, Tokushima University
• 著者名: 神田, 峻介; 泓田, 正雄; 森田, 和宏; 青江, 順一
• 著者名(英): Shunsuke, Kanda; Masao, Fuketa; Kazuhiro, Morita; Jun-ichi, Aoe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: トライと呼ばれる順序木を効率的に表現するデータ構造として，高速な検索を提供するダブル配列がある．また，データの大規模化に伴いコンパクト性が重視される背景に応じて，様々なダブル配列の圧縮表現が提案されてきた．しかし，これらの圧縮表現は，トライにおける順方向の遷移 （親から子） のみを提供し，逆方向の遷移 （子から親） を提供していないため，結果としてダブル配列における逆引きや動的更新を犠牲にしている．本論文では，逆方向遷移を可能としたコンパクトな配列構造を提案する．記憶量について，ダブル配列の約 36%でトライを表現可能なことが実験により確認されている．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A double-array efficiently represents an ordered tree called “trie”, and provides fast retrieval in the trie. Recently, many compact representations of the double-array have been proposed because a compact data structure is important in big data. The double-array provides inorder (from a parent to a child) and reverse (from a child to a parent) traversals, but the compact representations provide only the inorder traversal. Therefore, the compact representations don't have a dynamic update and a reverse lookup in the double-array. This paper proposes a compact array structure with the reverse traversal. In addition, experimental results show that the new structure represents the trie with 36% of the double-array size.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10114171
• 書誌情報: 研究報告情報基礎とアクセス技術（IFAT）; 巻 2015-IFAT-119, 号 10, p. 1-6, 発行日 2015-07-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8884
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会