Aarhus University Seal

Finger Search in the Implicit Model

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

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
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume7676
Pages (from-to)527-536
Number of pages10
ISSN0302-9743
DOIs
Publication statusPublished - 2012
EventInternational Symposium Algorithms and Computation - Taipei, Taiwan
Duration: 19 Dec 201221 Dec 2012
Conference number: 32

Conference

ConferenceInternational Symposium Algorithms and Computation
Number32
CountryTaiwan
CityTaipei
Period19/12/201221/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

ISBN: 978-3-642-35260-7, 978-3-642-35261-4

See relations at Aarhus University Citationformats

ID: 51949119