Dynamic Path-Decomposed Tries
Dynamic Path-Decomposed Tries
复制标题
动态路径分解尝试
DOI：
10.1145/3418033
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Shunsuke Kanda and Dominik Koeppl and Yasuo Tabei and Kazuhiro Morita and Masao Fuketa
中科院分区：
文献类型：
--
作者：
Tsuruta Kazuya;Koppl Dominik;Kanda Shunsuke;Nakashima Yuto;Inenaga Shunsuke;Bannai Hideo;Takeda Masayuki;Shunsuke Kanda and Dominik Koeppl and Yasuo Tabei and Kazuhiro Morita and Masao Fuketa
关键字字典是一个关联数组，其键是字符串。最近处理主存储器中大量关键字字典的应用程序需要节省空间的实现。当仅限于静态应用程序时，有许多基于实用简洁数据结构的进步的高度压缩的关键字词典。然而，由于大多数简洁的数据结构仅在静态情况下有效，因此实现空间高效且动态的关键字字典仍然很困难。在这篇文章中，我们提出了这样一个关键词词典。我们的主要想法是采用路径分解技术，该技术是为构建缓存友好的尝试而提出的。为了将路径分解的 trie 存储在小内存中，我们基于最新的紧凑哈希 trie 表示设计了数据结构。对现实世界数据集的实验表明，我们的动态关键词词典比现有的最小词典需要的空间减少了 68%，同时实现了相关的时空权衡。
A keyword dictionary is an associative array whose keys are strings. Recent applications handling massive keyword dictionaries in main memory have a need for a space-efficient implementation. When limited to static applications, there are a number of highly compressed keyword dictionaries based on the advancements of practical succinct data structures. However, as most succinct data structures are only efficient in the static case, it is still difficult to implement a keyword dictionary that isspace efficientanddynamic. In this article, we propose such a keyword dictionary. Our main idea is to embrace the path decomposition technique, which was proposed for constructing cache-friendly tries. To store the path-decomposed trie in small memory, we design data structures based on recent compact hash trie representations. Experiments on real-world datasets reveal that our dynamic keyword dictionary needs up to 68% less space than the existing smallest ones, while achieving a relevant space-time tradeoff.