Earticle

초록

영어

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.

목차

Abstract
 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

키워드

저자

• Guoqing Zhang [ School of Computer Science & Technology, Soochow University, Suzhou, 215006, China ]
• Mei Rong [ Shenzhen Tourism College, Jinan University, Shenzhen, 518053, China ]
• Guangquan Zhang [ School of Computer Science & Technology, Soochow University, Suzhou, 215006, China, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Science, Beijing, 100190, China ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Database Theory and Application

• 간기

  격월간

• pISSN

  2005-4270

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605