We consider the classication problem as a problem of approximating a given training set. This approximation is constructedas a multi-resolution sparse grid, and organized in a tree-structure. It allows efficient training and query, both in constant time per training point, for low-dimensional classication problems (D <~ 10) with large data sets. The memory required for such problems is usually substantially smaller than the size of the training set.