A hybrid index structure for querying large string databases. (1st July 2005)

• Record Type: Journal Article
• Authors: Xue, Qiang; Pramanik, Sakti; Qiang, Gang; Zhu, Qiang
• Is Part Of: International journal of electronic business. Volume 3:Number 3/4(2005)
• Page Start: 243
• Page End: 254
• Publication Date: 2005-07-01
• Subjects: large string databases -- indexing methods -- hybrid RAM/disk-based data structure -- prefix searching -- substring searching -- e-business -- electronic business -- electronic documents -- information retrieval -- internet; Electronic commerce -- Periodicals; 658.05467805
• Languages: English
• ISSNs: 1470-6067

Abstract

Rapid growth in e-business has created a demand to efficiently index and search an increasingly large amount of strings. In this paper, we propose a hybrid RAM/disk-based index structure, called the HD-tree, making proper use of both RAM and disk spaces to achieve high performance for querying large string databases. Our experimental results demonstrate that the HD-tree outperforms the popular Prefix B-tree for prefix and substring searches. In particular, the average number of disk I/Os is reduced by a factor of two to three, and the total running time is approximately five times faster.