Classification via Two-Way Comparisons
Open Access
- 7 February 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (2) , 1-19
Abstract
Given a weighted, ordered query set \(Q\) and a partition of \(Q\) into classes, we study the problem of computing a minimum-cost decision tree that, given any query \(q\in Q\) , uses equality tests and less-than tests to determine \(q\) 's class. Such a tree can be faster and smaller than a conventional search tree and smaller than a lookup table (both of which must identify \(q\) , not just its class). We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes.
Keywords
All Related Versions
Funding Information
- Division of Computing and Communication Foundations (CCF-2153723)
This publication has 18 references indexed in Scilit:
- Classification via Two-Way Comparisons (Extended Abstract)2023
- On Huang and Wong’s algorithm for generalized binary split treesActa Informatica, 2022
- Optimal classification treesMachine Learning, 2017
- Optimal search trees using two-way key comparisonsActa Informatica, 1994
- Optimum split treesJournal of Algorithms, 1984
- Generalized binary split treesActa Informatica, 1984
- Optimal binary split treesJournal of Algorithms, 1984
- Constructing optimal binary decision trees is NP-completeInformation Processing Letters, 1976
- Optimum binary search treesActa Informatica, 1971
- Variable-Length Binary EncodingsBell System Technical Journal, 1959