Near-optimal online multiselection in internal and external memory

DOI10.1016/j.jda.2015.11.001zbMath1351.68310arXiv1206.5336OpenAlexW1720225735MaRDI QIDQ2634712

Jérémy Barbay, Ankur Gupta, Jonathan P. Sorenson, Srinivasa Rao Satti

Publication date: 18 February 2016

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1206.5336

zbMATH Keywords

dynamicsortingselectiononline algorithmsexternal memorymultiselectiondeferred data structures

Mathematics Subject Classification ID

Searching and sorting (68P10) Online algorithms; streaming algorithms (68W27)

Uses Software

• Find

Cites Work

• Unnamed Item
• Multiple Quickselect -- Hoare's Find algorithm for several elements
• Dynamic deferred data structuring
• Finding the median
• Surpassing the information theoretic bound with fusion trees
• Time bounds for selection
• Fun-Sort -- or the chaos of unordered binary search
• Theory and Implementation of Online Multiselection Algorithms
• On the limits of cache-obliviousness
• Interval Sorting
• Optimal Time Minimal Space Selection Algorithms
• Selecting the Median
• Discrete Mathematics
• An efficient algorithm for partial order production
• Dynamic Online Multiselection in Internal and External Memory
• Algorithms and Computation
• External selection
• Automata, Languages and Programming

This page was built for publication: Near-optimal online multiselection in internal and external memory