1 Department of Computer Science, Science and Technology, Aarhus University2 Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University3 Karlsruhe Institute of Technology4 Department of Computer Science, Science and Technology, Aarhus University
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.
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:
Lecture Notes in Computer Science
International Symposium on Algorithms and Data StructuresAlgorithms and Data Structures Symposium, 2013