We present a novel and systematic method, called Superfast Selection, for
selecting the "optimal split" for decision tree and feature selection
algorithms over tabular data. The method speeds up split selection on a single
feature by lowering the time complexity, from O(MN) (using the standard
selection methods) to O(M), where M represents the number of input examples and
N the number of unique values. Additionally, the need for pre-encoding, such as
one-hot or integer encoding, for feature value heterogeneity is eliminated. To
demonstrate the efficiency of Superfast Selection, we empower the CART
algorithm by integrating Superfast Selection into it, creating what we call
Ultrafast Decision Tree (UDT). This enhancement enables UDT to complete the
training process with a time complexity O(KMlogM) (K is the number of
features). Additionally, the Training Only Once Tuning enables UDT to avoid the
repetitive training process required to find the optimal hyper-parameter.
Experiments show that the UDT can finish a single training on KDD99-10% dataset
(494K examples with 41 features) within 1 second and tuning with 214.8 sets of
hyper-parameters within 0.25 second on a laptop.

我们提出了一种名为 Superfast Selection 的新颖系统方法，用于在表格数据上选择决策树和特征选择算法的 “最优分裂”。该方法通过降低时间复杂度（从 O（MN）降至 O（M））来加快在单个特征上的分裂选择，M 表示输入示例的数量，N 表示唯一值的数量。此外，消除了特征值异质性的预编码需求，例如独热或整数编码。为了展示 Superfast Selection 的高效性，我们将其集成到 CART 算法中，创造了我们所称的 Ultrafast Decision Tree (UDT)。这种改进使 UDT 能够在时间复杂度为 O（KMlogM）（其中 K 是特征的数量）的情况下完成训练过程。此外，Training Only Once Tuning 使得 UDT 可以避免寻找最优超参数所需的重复训练过程。实验证明，在笔记本电脑上，UDT 可以在 1 秒内完成对 KDD99-10％数据集（494K 个示例，41 个特征）的单次训练，并在 0.25 秒内使用 214.8 个超参数集进行调优。