Department of Computer Science & Engineering

This paper introduces a classification algorithm called HyperCuts. Like the previously best known algorithm, HiCuts, HyperCuts is based on a decision tree structure. Unlike HiCuts, however, in which each node in the decision tree represents a hyperplane, each node in the HyperCuts decision tree represents a k-dimensional hypercube, where k > 1. Using this extra degree of freedom and a new set of heuristics to find optimal hypercubes for a given amount of storage, HyperCuts can provide an order of magnitude improvement over existing classification algorithms. It uses 2 to 10 times less memory than HiCuts optimized for memory, while the worst case search time of HyperCuts is 50-500% better than that of HiCuts optimized for speed. Compared with another scheme recently introduced in Infocom 2003 called EGT-PC, HyperCuts uses 1.8-7 times less memory space while the worst case search time is up to $5$ times smaller. More importantly, unlike EGT-PC, HyperCuts can be fully pipelined to provide one classification result every memory access time, and has fast updates.

Pre-2018 CSE ID: CS2003-0736