We address the problem of creating a dictionary with the finger search property in the strict implicit model, where no information is stored between operations, except the array of elements. We show that for any implicit dictionary supporting finger searches in q(t) = Ω(logt) time, the time to move the finger to another element is Ω(q− 1(logn)), where t is the rank distance between the query element and the finger. We present an optimal implicit static structure matching this lower bound. We furthermore present a near optimal implicit dynamic structure supporting search, change-finger, insert, and delete in times $\mathcal{O}(q(t))$, $\mathcal{O}(q^{-1}(\log n)\log n)$, $\mathcal{O}(\log n)$, and $\mathcal{O}(\log n)$, respectively, for any q(t) = Ω(logt). Finally we show that the search operation must take Ω(logn) time for the special case where the finger is always changed to the element returned by the last query
International Symposium Algorithms and Computation - Taipei, Taiwan Duration: 19 Dec 2012 → 21 Dec 2012 Conference number: 32
Conference
Conference
International Symposium Algorithms and Computation
Number
32
Country
Taiwan
City
Taipei
Period
19/12/2012 → 21/12/2012
Bibliographical note
Title of the vol.: Algorithms and Computation. 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings / eds.: Kun-Mao Chao, Tsan-sheng Hsu, Der-Tsai Lee