Type of publication: | Inproceedings |
Entered by: | |
Title | Improved Bounds for Finger Search on a RAM |
Bibtex cite ID | RACTI-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 |
URL | http://www.conferences.hu/algo2003/algo_2003.htm |
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. 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. |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments |
C30-esa2003a-fst.pdf (main file) |
|
Publication ID | 403 |