|This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies.
For more information visit Aigaion.nl.|
|Type of publication:||Article|
|Title||ISB-tree: A new indexing scheme with efficient expected behaviour|
|Bibtex cite ID||RACTI-RU1-2010-71|
|Year published ||2010|
|Keywords ||B-tree,External memory data structure,Interpolation search,Data indexing|
We present the interpolation search B-tree (ISB-tree), a new cache-aware indexing scheme
that supports update operations (insertions and deletions) in O(1) worst-case block
transfers and search operations in O(logB logn) 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 worst-case 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) worst-case block transfer bounds for search and update operations achieved
by the B-tree and its numerous variants. This is also verified by an accompanying