Lars Arge

On (dynamic) range minimum queries in external memory

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

Standard

On (dynamic) range minimum queries in external memory. / Arge, L.; Fischer, Johannes; Sanders, Peter; Sitchinava, Nodari.

Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. ed. / Frank Dehne; Roberto Solis-Oba; Jörg-Rüdiger Sack. Springer VS, 2013. p. 37-48 (Lecture Notes in Computer Science, Vol. 8037 ).

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

Harvard

Arge, L, Fischer, J, Sanders, P & Sitchinava, N 2013, On (dynamic) range minimum queries in external memory. in F Dehne, R Solis-Oba & J-R Sack (eds), Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. Springer VS, Lecture Notes in Computer Science, vol. 8037 , pp. 37-48, International Symposium on Algorithms and Data Structures, London, United Kingdom, 12/08/2013. https://doi.org/10.1007/978-3-642-40104-6_4

APA

Arge, L., Fischer, J., Sanders, P., & Sitchinava, N. (2013). On (dynamic) range minimum queries in external memory. In F. Dehne, R. Solis-Oba, & J-R. Sack (Eds.), Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings (pp. 37-48). Springer VS. Lecture Notes in Computer Science, Vol.. 8037 https://doi.org/10.1007/978-3-642-40104-6_4

CBE

Arge L, Fischer J, Sanders P, Sitchinava N. 2013. On (dynamic) range minimum queries in external memory. Dehne F, Solis-Oba R, Sack J-R, editors. In Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. Springer VS. pp. 37-48. (Lecture Notes in Computer Science, Vol. 8037 ). https://doi.org/10.1007/978-3-642-40104-6_4

MLA

Arge, L. et al. "On (dynamic) range minimum queries in external memory"., Dehne, Frank Solis-Oba, Roberto Sack, Jörg-Rüdiger (editors). Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. Springer VS. (Lecture Notes in Computer Science, Vol. 8037 ). 2013, 37-48. https://doi.org/10.1007/978-3-642-40104-6_4

Vancouver

Arge L, Fischer J, Sanders P, Sitchinava N. On (dynamic) range minimum queries in external memory. In Dehne F, Solis-Oba R, Sack J-R, editors, Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. Springer VS. 2013. p. 37-48. (Lecture Notes in Computer Science, Vol. 8037 ). https://doi.org/10.1007/978-3-642-40104-6_4

Author

Arge, L. ; Fischer, Johannes ; Sanders, Peter ; Sitchinava, Nodari. / On (dynamic) range minimum queries in external memory. Algorithms and Data Structures: 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings. editor / Frank Dehne ; Roberto Solis-Oba ; Jörg-Rüdiger Sack. Springer VS, 2013. pp. 37-48 (Lecture Notes in Computer Science, Vol. 8037 ).

Bibtex

@inproceedings{65ef4e2c546d4086bf00c0be7f4fbc8d,
title = "On (dynamic) range minimum queries in external memory",
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.",
author = "L. Arge and Johannes Fischer and Peter Sanders and Nodari Sitchinava",
year = "2013",
doi = "10.1007/978-3-642-40104-6_4",
language = "English",
isbn = "9783642401039",
series = "Lecture Notes in Computer Science",
publisher = "Springer VS",
pages = "37--48",
editor = "Dehne, {Frank } and { Solis-Oba}, {Roberto } and Sack, {J{\"o}rg-R{\"u}diger }",
booktitle = "Algorithms and Data Structures",
note = "null ; Conference date: 12-08-2013 Through 14-08-2013",

}

RIS

TY - GEN

T1 - On (dynamic) range minimum queries in external memory

AU - Arge, L.

AU - Fischer, Johannes

AU - Sanders, Peter

AU - Sitchinava, Nodari

N1 - Conference code: 13

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84881132276&partnerID=8YFLogxK

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

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

M3 - Article in proceedings

AN - SCOPUS:84881132276

SN - 9783642401039

T3 - Lecture Notes in Computer Science

SP - 37

EP - 48

BT - Algorithms and Data Structures

A2 - Dehne, Frank

A2 - Solis-Oba, Roberto

A2 - Sack, Jörg-Rüdiger

PB - Springer VS

Y2 - 12 August 2013 through 14 August 2013

ER -