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:
TitleImproved Bounds for Finger Search on a RAM
Bibtex cite IDRACTI-RU1-2003-29
Booktitle 11th Annual European Symposium on Algorithms (ESA 2003)
Series Lecture Notes in Computer Science
Year published 2003
Month September
Volume 2832
Pages 325-336
Publisher Springer Verlag
Location Budapest, Hungary
We present a new finger search tree with O(1) worst-case update time and O(log log d) expected search time with high probability in the Random Access Machine (RAM) model of computation for a large class of input distributions. The parameter d represents the number of elements (distance) between the search element and an element pointed to by a finger, in a finger search tree that stores n elements. For the need of the analysis we model the updates by a "balls and bins" combinatorial game that is interesting in its own right as it involves insertions and deletions of balls according to an unknown distribution.
Kaporis, Alexis
Makris, Christos
Sioutas, Spyros
Tsakalidis, Athanasios
Tsichlas, Kostas
Zaroliagis, Christos
C30-esa2003a-fst.pdf (main file)
Publication ID403