O (m log m) instance selection algorithms—RR-DROPs
Marek Orliński, Norbert Jankowski · 2020
This paper is focused on an instance selection algorithm for classification purposes. We propose a new fast version of DROP algorithms with complexity reduced to O(m log m), while the original complexity was O(m3). The new RR-DROP algorithms use random region hashing forests and jungle, and several other data structures to keep the computational complexity as low as possible. The proposed algorithms can be used for huge datasets, with classification remaining unchanged, as proven by a statistical analysis on several datasets.