In problems with a large number of labels, most multi-label and multi-class techniques incur a significant computational burden at test time. This is because, for each test instance, they need to systematically evaluate every label to decide whether it is relevant for the instance or not. We address this problem by designing computationally efficient label filters that eliminate the majority of labels from consideration before the base multi-class or multi-label classifier is applied. The proposed label filter projects a test instance on a filtering line and eliminates all the labels that had no training instances falling in the vicinity of this projection. The filter is learned directly from data by solving a constraint optimization problem, and it is independent of the base multi-label classifier. Experiments show that the proposed label filters can speed up prediction by orders of magnitude without significant impact on performance.