MedianOfNinthers
Fast deterministic selection. The selection problem, in forms such as finding the median or choosing the (k) top ranked items in a dataset, is a core task in computing with numerous applications in fields as diverse as statistics, databases, machine learning, finance, biology, and graphics. The selection algorithm Median of Medians, although a landmark theoretical achievement, is seldom used in practice because it is slower than simple approaches based on sampling. The main contribution of this paper is a fast linear-time deterministic selection algorithm MedianOfNinthers based on a refined definition of MedianOfMedians. A complementary algorithm MedianOfExtrema is also proposed. These algorithms work together to solve the selection problem in guaranteed linear time, faster than state-of-the-art baselines, and without resorting to randomization, heuristics, or fallback approaches for pathological cases. We demonstrate results on uniformly distributed random numbers, typical low-entropy artificial datasets, and real-world data. Measurements are open-sourced alongside the implementation at url{https://github.com/andralex/MedianOfNinthers}.
Keywords for this software
References in zbMATH (referenced in 5 articles , 1 standard article )
Showing results 1 to 5 of 5.
Sorted by year (- Dumitrescu, Adrian: Finding a mediocre player (2021)
- Schoot Uiterkamp, Martijn H. H.; Hurink, Johann L.; Gerards, Marco E. T.: A fast algorithm for quadratic resource allocation problems with nested constraints (2021)
- Chen, Ke; Dumitrescu, Adrian: Selection algorithms with small groups (2020)
- Dumitrescu, Adrian: A selectable sloppy heap (2019)
- Alexandrescu, Andrei: Fast deterministic selection (2017)