ALCOMFT-TR-03-154

Alexis Kaporis, Christos Makris, Spyros Sioutas, Athanasios Tsakalidis, Kostas Tsichlas and Christos Zaroliagis
Improved Bounds for Finger Search on a RAM
Patras. Work package 4. December 2003.

Abstract: 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. Our data structure improves upon a previous result by Andersson and Mattson that exhibits expected O(log log n) time and O(1) worst-case update time, by incorporating the distance d into the search time complexity, thus removing the dependence on n, and by proving that the attained search time complexity holds with high probability. 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.

Postscript file: ALCOMFT-TR-03-154.ps.gz (177 kb).