A Succinct String Dictionary Index in External Memory
Guoqing Zhang, Mei Rong, Guangquan Zhang · International Journal of Database Theory and Application · 2014
With the coming of the big data age, more and more string dictionaries need to be processed.The existing string dictionary indexes are either too space-consuming, or lack of locality of reference, making them inapplicable in the external memory environment.Targeted with these problems, first we design a new succinct representation of Patricia trie using LOUDS encoding.Then applying it to external memory indexing problem, we propose a new string dictionary index SB-trie, which is not only succinct on space, but also has good locality of reference, making it I/O efficient in external memory environment.Experiments show that SB-trie consumes less space and has greater searching performance in disk environment.