B-tries for disk-based string management

Askitis, N and Zobel, J 2009, 'B-tries for disk-based string management', VLDB Journal, vol. 18, no. 1, pp. 157-179.


Document type: Journal Article
Collection: Journal Articles

Title B-tries for disk-based string management
Author(s) Askitis, N
Zobel, J
Year 2009
Journal name VLDB Journal
Volume number 18
Issue number 1
Start page 157
End page 179
Total pages 23
Publisher Springer
Abstract A wide range of applications require that large quantities of data be maintained in sort order on disk. The B-tree, and its variants, are an efficient general-purpose diskbased data structure that is almost universally used for this task. The B-trie has the potential to be a competitive alternative for the storage of data where strings are used as keys, but has not previously been thoroughly described or tested. We propose new algorithms for the insertion, deletion, and equality search of variable-length strings in a disk-resident B-trie, as well as novel splitting strategies which are a critical element of a practical implementation.We experimentally compare the B-trie against variants of B-tree on several large sets of strings with a range of characteristics. Our results demonstrate that, although the B-trie uses more memory, it is faster, more scalable, and requires less disk space.
Subject Data Structures
Keyword(s) B-tree
Burst trie
Data structures
Secondary storage
Vocabulary accumulation
Word-level indexing
DOI - identifier 10.1007/s00778-008-0094-1
Copyright notice © 2008 Springer-Verlag.
ISSN 1066-8888
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 4 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 7 times in Scopus Article | Citations
Altmetric details:
Access Statistics: 386 Abstract Views  -  Detailed Statistics
Created: Wed, 17 Nov 2010, 16:09:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us