On (dynamic) range minimum queries in external memory

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • L. Arge
  • Johannes Fischer, Karlsruhe Institute of Technology, Germany
  • Peter Sanders, Karlsruhe Institute of Technology, Germany
  • Nodari Sitchinava, Karlsruhe Institute of Technology, Germany
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.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures : 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings
EditorsFrank Dehne, Roberto Solis-Oba, Jörg-Rüdiger Sack
Number of pages12
PublisherSpringer VS
Publication year2013
Pages37-48
ISBN (print)9783642401039
ISBN (Electronic)978-3-642-40104-6
DOIs
Publication statusPublished - 2013
EventInternational Symposium on Algorithms and Data Structures - London, United Kingdom
Duration: 12 Aug 201314 Aug 2013
Conference number: 13

Conference

ConferenceInternational Symposium on Algorithms and Data Structures
Nummer13
LandUnited Kingdom
ByLondon
Periode12/08/201314/08/2013
SeriesLecture Notes in Computer Science
Volume8037
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 56165920