A hybrid index structure for querying large string databases. (1st July 2005) - Xue, Qiang; Pramanik, Sakti; Qiang, Gang; Zhu, Qiang
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.