2015 | OriginalPaper | Buchkapitel
Dynamic Online Multiselection in Internal and External Memory
Autoren: Jérémy Barbay, Ankur Gupta, Srinivasa Rao Satti, Jonathan Sorenson
Verlag: Springer International Publishing
We consider the dynamic version of the
online multiselection
problem for internal and external memory, in which
q
selection queries are requested on an unsorted array of
N
elements. Our internal memory result is 1-competitive with the offline result of Kaligosiet al.[ICALP 2005]. In particular, we extend the results of Barbaryet al.[ESA 2013] by supporting arbitrary
insertions
and
deletions
while supporting online
select
and
search
queries on the array. Assuming that the insertion of an element is immediately preceded by a search for that element, we show that our dynamic online algorithm performs an optimal number of comparisons, up to lower order terms and an additive
O
(
N
) term.
For the external memory model, we describe the first online multiselection algorithm that is
O
(1)-competitive. This result improves upon the work of Sibeyn [Journal of Algorithms 2006] when
q
>
m
, where
m
is the number of blocks that can be stored in main memory. We also extend it to support searches, insertions, and deletions of elements efficiently.
