Path Decompositionを用いたメモリ効率の良い動的キーワード辞書の実装法

• Item type: SIG Technical Reports(1)
• 公開日: 2017-09-11
• タイトル: Path Decompositionを用いたメモリ効率の良い動的キーワード辞書の実装法
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: スケーラブルなデータ処理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 徳島大学大学院先端技術科学教育部／学術振興会
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者所属: 徳島大学大学院先端技術科学教育部
• 著者名: 神田, 峻介; 森田, 和宏; 泓田, 正雄
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: キーワード辞書とは文字列をキーとする連想配列であり，文字列集合を保管するためのデータ構造として古くから用いられている．一方で近年，このキーワード辞書を用いて大規模な文字列データを主記憶で管理するといった実例が数多く報告されており，メモリ効率の良い実装が求められている．現在のところ，静的用途に限定すれば数多くの実装が高いメモリ効率を達成している．しかし，それらに比べて既存の動的な実装は遥かに多くのメモリを消費する．そこで本稿では，Path Decomposition を用いたメモリ効率の良い動的キーワード辞書の実装法を提案する．Path Decomposition とは本来，キャッシュフレンドリーな Trie 辞書を実装するために用いられる技法であるが，本提案では省メモリな動的辞書を実現するためにこの技法を用いる．大規模な現実のデータセットを用いた実験により，提案手法は既存の最もメモリ効率の良い実装と比べ，最大で 2.8 倍もコンパクトに動的辞書を実現できることを示す．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 研究報告データベースシステム（DBS）; 巻 2017-DBS-165, 号 15, p. 1-6, 発行日 2017-09-11
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-871X
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会