How can we detect 100,000 diverse object classes in a photo? Traditionally, computational cost scales linearly in the number of classes, rendering such a system infeasible on a single machine. We propose a system that can evaluate 100,000 deformable-part-model-based classifiers on a single multi-core machine in about 20 seconds per image. Our approach makes two key contributions: a multiclass feature hashing scheme that shares features across all classes, and a cascade architecture that prunes unlikely hypotheses early. Together, these reduce the cost from days to seconds, making large-scale detection practical.

Object detection is a fundamental task in computer vision, yet most existing detectors are designed for a small number of categories — typically 20 (PASCAL VOC) or 200 (ImageNet Detection). As visual recognition databases grow to include tens or hundreds of thousands of categories, the question arises: can we build a detection system that scales to this number while remaining computationally feasible on commodity hardware? The naive approach of running an independent detector per class is clearly prohibitively expensive.

Our work builds on the deformable part model (DPM) framework of Felzenszwalb et al., which represents each class as a root filter plus a collection of part filters with spatial constraints. While DPM achieves strong detection accuracy, its per-class cost is substantial: evaluating a single DPM takes on the order of seconds, making 100,000-class detection a multi-day computation. Our key insight is that the majority of computation across classes is redundant — many classes share similar features and spatial patterns that can be exploited.

Prior work on scalable object detection has explored several directions. Cascade classifiers, popularized by Viola and Jones, provide early rejection of easy negatives but are typically designed for single-class or few-class settings. Feature sharing approaches compute a shared feature representation once and reuse it across classes, but existing methods do not scale beyond a few hundred categories. Hashing-based methods in the retrieval literature offer sub-linear search but have not been applied to structured detection models like DPM.

The ImageNet Large Scale Visual Recognition Challenge (ILSVRC) has spurred interest in recognition at scale, with the classification task covering 1,000 categories. However, the detection track remains limited to 200 categories, reflecting the computational barriers. Our work bridges this gap by demonstrating that detection at 100,000 classes is achievable with algorithmic innovations rather than brute-force hardware scaling.

The core of our approach is a feature sharing strategy based on vector quantization. In a standard DPM, each class requires computing HOG features convolved with class-specific filters. We observe that filter weights across 100,000 classes can be approximated by a shared codebook of prototypical filter vectors. Each filter is encoded as a sparse combination of codebook entries, and the convolution responses for all codebook entries are computed once and shared across all classes. This reduces the per-class marginal cost to a simple lookup and weighted sum.

Beyond feature sharing, we introduce a locality-sensitive hashing (LSH) scheme to further accelerate the scoring stage. For each candidate detection window, rather than evaluating all 100,000 classifiers, we use hash functions to identify a short list of plausible classes. The hash functions are designed so that windows whose feature vectors are close to a class's filter will hash to the same bucket. This reduces the scoring from O(C) to approximately O(1) per window, where C is the number of classes.

We also employ a multi-stage cascade that progressively refines hypotheses. In the first stage, a coarse root-filter score eliminates the vast majority of windows. Surviving hypotheses are then evaluated with part filters and spatial constraints. This cascade architecture ensures that the full DPM computation is only performed on a tiny fraction of candidates, further reducing the average per-image cost while maintaining detection accuracy close to the unaccelerated baseline.

We evaluate our system on up to 100,000 object categories derived from ImageNet. On a single machine with 16 CPU cores, the full system processes an image in approximately 20 seconds for 100,000 classes. Without our optimizations, the same computation would take over 6 days. The feature sharing via vector quantization yields a speedup of approximately 20x, and the hashing scheme provides an additional 100x speedup. The cascade adds further gains. In terms of accuracy, on the PASCAL VOC 2007 benchmark (20 classes), our approximate system achieves mAP within 1% of the exact DPM baseline.

We further analyze the scaling behavior of our system. The detection time grows sub-linearly with the number of classes: doubling the number of classes increases the runtime by approximately 30% rather than 100%. This sub-linear scaling is the direct result of our shared computation strategy. We also study the trade-off between codebook size and accuracy, finding that a codebook of 4,096 entries captures over 95% of the original detection accuracy across all categories.

We have presented a system capable of detecting 100,000 object classes on a single machine with practical runtime. Our key contributions — feature sharing via vector quantization, hashing-based scoring, and multi-stage cascades — collectively achieve over four orders of magnitude speedup with minimal accuracy loss. This work demonstrates that large-scale detection is fundamentally an algorithmic challenge, not merely a hardware one. We believe our techniques are broadly applicable to other structured classification problems that must scale to very large label spaces.