|
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 |
Entered by: | chita |
Title | Improved Bounds for Finger Search on a RAM |
Bibtex cite ID | RACTI-RU1-2011-63 |
Journal | Algorithmica |
Year published | 2011 |
Month | November |
Keywords | data structures,dictionary problem,balls and bins problem,interpolation search,expected analysis |
Abstract | 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. |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments |
J33-Algorithmica-Finger-Search.pdf (main file) |
|
Publication ID | 917 |
|
|