원문정보
초록
영어
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.
목차
1. Introduction
2. Basic Data Structures and Algorithms
2.1. Bit array
2.2. Trie
2.3. The LOUDS Representation of Trie
3. The Succinct Representation of Patricia Trie
3.1. Patricia Trie
3.2. The Succinct Representation of Patricia Trie
4. SB-trie
4.1. The Construction of SB-trie
4.2. Search in SB-trie
5. Experiments
5.1. Experiment Environment
5.2. Experiment Results and Analysis
6. Conclusion
Acknowledgements
References