Dynamic Path-decomposed Tries
| Autor: | Dominik Köppl, Shunsuke Kanda, Masao Fuketa, Kazuhiro Morita, Yasuo Tabei |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Theoretical computer science Design data Computer science 0102 computer and information sciences 02 engineering and technology Space (commercial competition) 01 natural sciences Associative array Computer Science - Information Retrieval Theoretical Computer Science Succinct data structure 010201 computation theory & mathematics Hash trie Computer Science - Data Structures and Algorithms Trie Path (graph theory) 0202 electrical engineering electronic engineering information engineering Decomposition (computer science) Data Structures and Algorithms (cs.DS) 020201 artificial intelligence & image processing Information Retrieval (cs.IR) |
| Zdroj: | ACM Journal of Experimental Algorithmics. 25:1-28 |
| ISSN: | 1084-6654 |
| DOI: | 10.1145/3418033 |
| Popis: | 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 is space efficient and dynamic. 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. Accepted by ACM Journal of Experimental Algorithmics |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|