On (dynamic) range minimum queries in external memory

DOI10.1007/978-3-642-40104-6_4MaRDI QIDQ2842141zbMATH OpenOpenAlexFDO

Authors Lars Arge, Johannes Fischer, Peter Sanders, Nodari Sitchinava

Publication date 12 August 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40104-6_4

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• I/O-efficient range minima queries
• How to answer a small batch of RMQs or LCA queries in practice
• Efficient dynamic range minimum query
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Optimal succinctness for range minimum queries

Cited in

(9)

• How to answer a small batch of RMQs or LCA queries in practice
• Efficient external memory structures for range-aggregate queries
• Tight lower bounds for query processing on streaming and external memory data
• The batched predecessor problem in external memory
• I/O-efficient range minima queries
• Maximizing Range Sum in External Memory
• Efficient dynamic range minimum query
• Cache oblivious algorithms for the RMQ and the RMSQ problems
• Quantum data structure for range minimum query

This page was built for publication: On (dynamic) range minimum queries in external memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842141)