THE HYBRID DIGITAL TREE: A NEW INDEXING TECHNIQUE FOR LARGE STRING DATABASES

Qiang Xue, Sakti Pramanik, Gang Qian, Qiang Zhu

2005

Abstract

There is an increasing demand for efficient indexing techniques to support queries on large string databases. In this paper, a hybrid RAM/disk-based index structure, called the Hybrid Digital tree (HD-tree), is proposed. The HD-tree keeps internal nodes in the RAM to minimize the number of disk I/Os, while maintaining leaf nodes on the disk to maximize the capability of the tree for indexing large databases. Experimental results using real data have shown that the HD-tree outperformed the Prefix B-tree for prefix and substring searches. In particular, for distinctive random queries in the experiments, the average number of disk I/Os was reduced by a factor of two to three, while the running time was reduced in an order of magnitude.

Paper Citation

in Harvard Style

Xue Q., Pramanik S., Qian G. and Zhu Q. (2005). THE HYBRID DIGITAL TREE: A NEW INDEXING TECHNIQUE FOR LARGE STRING DATABASES . In Proceedings of the Seventh International Conference on Enterprise Information Systems - Volume 1: ICEIS, ISBN 972-8865-19-8, pages 115-121. DOI: 10.5220/0002518501150121

in Bibtex Style

@conference{iceis05,
author={Qiang Xue and Sakti Pramanik and Gang Qian and Qiang Zhu},
title={THE HYBRID DIGITAL TREE: A NEW INDEXING TECHNIQUE FOR LARGE STRING DATABASES},
booktitle={Proceedings of the Seventh International Conference on Enterprise Information Systems - Volume 1: ICEIS,},
year={2005},
pages={115-121},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002518501150121},
isbn={972-8865-19-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Seventh International Conference on Enterprise Information Systems - Volume 1: ICEIS,
TI - THE HYBRID DIGITAL TREE: A NEW INDEXING TECHNIQUE FOR LARGE STRING DATABASES
SN - 972-8865-19-8
AU - Xue Q.
AU - Pramanik S.
AU - Qian G.
AU - Zhu Q.
PY - 2005
SP - 115
EP - 121
DO - 10.5220/0002518501150121