Improved Bounds for Finger Search on a RAM |
| |
Authors: | Alexis Kaporis Christos Makris Spyros Sioutas Athanasios Tsakalidis Kostas Tsichlas Christos Zaroliagis |
| |
Affiliation: | 1. Department of Information and Communication Systems Engineering, University of the Aegean, Karlovassi, Samos, 83200, Greece 2. Department of Computer Engineering and Informatics, University of Patras, 26500, Patras, Greece 3. Computer Technology Institute, Patras University Campus, N. Kazantzaki Str, 26504, Patras, Greece 4. Department of Informatics, Ionian University, Corfu, Greece 5. Department of Informatics, Aristotle University of Thessaloniki, Thessaloniki, Greece
|
| |
Abstract: | We present a new finger search tree with O(loglogd) 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(loglogn) 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(loglogd+?(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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|