research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleISB-Tree: A New Indexing Scheme with Efficient Expected Behaviour
Bibtex cite IDRACTI-RU1-2005-57
Booktitle 16th Annual International Symposium on Algorithms and Computation
Series Lecture Notes in Computer Science
Year published 2005
Volume 3827
Pages 318-327
Publisher Springer-Verlag
Organization ISAAC 2005
Location Hainan, China
We present the interpolation search tree (ISB-tree), a new cache-aware indexing scheme that supports update operations (insertions and deletions) in O(1) worst-case (w.c.) block transfers and search operations in O(logB log n) expected block transfers, where B represents the disk block size and n denotes the number of stored elements. The expected search bound holds with high probability for a large class of (unknown) input distributions. The w.c. search bound of our indexing scheme is O(logB n) block transfers. Our update and expected search bounds constitute a considerable improvement over the O(logB n) w.c. block transfer bounds for search and update operations achieved by the B-tree and its numerous variants. This is also suggested by a set of preliminary experiments we have carried out. Our indexing scheme is based on an externalization of a main memory data structure based on interpolation search.
Kaporis, Alexis
Makris, Christos
Mavritsakis, George
Sioutas, Spyros
Tsakalidis, Athanasios
Tsichlas, Kostas
Zaroliagis, Christos
fulltext1.pdf (main file)
Publication ID493