Near-optimal online multiselection in internal and external memory

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 [20] when q=ω(m1−ϵ) for any fixed positive constant ϵ, 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.