Finger Search in the Implicit Model

Gerth Stølting Brodal, Jesper Sindahl Nielsen, and Jakob Truelsen

In Proc. 23th Annual International Symposium on Algorithms and Computation, volume 7676 of Lecture Notes in Computer Science, pages 527-536. Springer Verlag, Berlin, 2012.

Abstract

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)=Ω(log t) time, the time to move the finger to another element is Ω(q-1(log n)), 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 O(q(t)), O(q-1(log n)log n), O(log n), and O(log n), respectively, for any q(t) = Ω(log t). Finally we show that the search operation must take Ω(log n) time for the special case where the finger is always changed to the element returned by the last query.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2012. All rights reserved.

Online version

isaac12.pdf (318 Kb)

DOI

10.1007/978-3-642-35261-4_55

Links

BIBTEX entry

@incollection{isaac12,
  author = "Gerth St{\o}lting Brodal and Jesper Sindahl Nielsen and Jakob Truelsen",
  booktitle = "Proc. 23th Annual International Symposium on Algorithms and Computation",
  doi = "10.1007/978-3-642-35261-4_55",
  isbn = "978-3-642-35260-7",
  pages = "527-536",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Finger Search in the Implicit Model",
  volume = "7676",
  year = "2012"
}