^{1} Department of Computer Science, Science and Technology, Aarhus University^{2} Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University^{3} Karlsruhe Institute of Technology^{4} Department of Computer Science, Science and Technology, Aarhus University

DOI:

10.1007/978-3-642-40104-6_4

Abstract:

We study the one-dimensional range minimum query (RMQ) problem in the external memory model. We provide the first space-optimal solution to the batched static version of the problem. On an instance with N elements and Q queries, our solution takes Θ(sort(N + Q)) = Θ( N+QB log M /B N+QB ) I/O complexity and O(N + Q) space, where M is the size of the main memory and B is the block size. This is a factor of O(log M /B N) improvement in space complexity over the previous solutions. We also show that an instance of the batched dynamic RMQ problem with N updates and Q queries can be solved in O ( N+QB log2M/B N+QB ) I/O complexity and O(N + Q) space.

ISBN:

9783642401046, 9783642401039

Type:

Conference paper

Language:

English

Published in:

Lecture Notes in Computer Science: 13th International Symposium, Wads 2013, London, On, Canada, August 12-14, 2013. Proceedings, 2013, p. 37-48

Main Research Area:

Science/technology

Publication Status:

Published

Series:

Lecture Notes in Computer Science

Review type:

Peer Review

Conference:

International Symposium on Algorithms and Data StructuresAlgorithms and Data Structures Symposium, 2013