A succinct string dictionary index in external memory

ISCAS OpenIR

	A succinct string dictionary index in external memory
	Zhang, Guoqing; Rong, Mei; Zhang, Guangquan; Rong, M.(rongmei@sz.jnu.edu.cn)
	2014
发表期刊	International Journal of Database Theory and Application
ISSN	20054270
卷号	7 期号:3 页码:13-22
摘要	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. © 2014 SERSC. ; 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. © 2014 SERSC.
收录类别	EI
部门归属	(1) School of Computer Science and Technology, Soochow University, Suzhou, 215006, China; (2) Shenzhen Tourism College, Jinan University, Shenzhen, 518053, China; (3) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Science, Beijing, 100190, China
语种	英语
内容类型	期刊论文
版本	出版稿
URI标识	http://ir.iscas.ac.cn/handle/311060/17021
专题	中国科学院软件研究所
通讯作者	Rong, M.(rongmei@sz.jnu.edu.cn)
推荐引用方式 GB/T 7714	Zhang, Guoqing,Rong, Mei,Zhang, Guangquan,et al. A succinct string dictionary index in external memory[J]. International Journal of Database Theory and Application,2014,7(3):13-22.
APA	Zhang, Guoqing,Rong, Mei,Zhang, Guangquan,&Rong, M..(2014).A succinct string dictionary index in external memory.International Journal of Database Theory and Application,7(3),13-22.
MLA	Zhang, Guoqing,et al."A succinct string dictionary index in external memory".International Journal of Database Theory and Application 7.3(2014):13-22.