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:Article
Entered by:chita
TitleImproved Bounds for Finger Search on a RAM
Bibtex cite IDRACTI-RU1-2011-63
Journal Algorithmica
Year published 2011
Month November
Keywords data structures,dictionary problem,balls and bins problem,interpolation search,expected analysis
We present a new finger search tree with O(log log d) expected search time 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. Our data structure improves upon a previous result by Andersson and Mattsson that exhibits expected O(log log n) search time by incorporating the distance d into the search time complexity, and thus removing the dependence on n. We are also able to show that the search time is O(log log d + φ(n)) with high probability, where φ(n) is any slowly growing function of n. 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
J33-Algorithmica-Finger-Search.pdf (main file)
Publication ID917