Norm-Aware Residual Hashing for Fast Nearest Neighbor Search

Approximate nearest neighbor (ANN) search in high-dimensional spaces plays an important role in modern AI applications. To reduce the cost of high-dimensional distance computations in ANN search, binary hashing represents vectors as compact binary codes and uses inexpensive Hamming distances to select candidates. However, we observe that vectors in several real-world datasets are concentrated within a narrow angular region. When such vectors are encoded, the resulting bits can be imbalanced and have low entropy, limiting the ability of binary codes to distinguish true neighbors from other candidates. Our experiments further show that more balanced bits alone do not ensure accurate L2 candidate ranking, since Hamming distance does not capture vector lengths. We propose Norm-Aware Residual Hashing (NARH), a mean-centered binary distance estimator designed to address these limitations. Our key idea is to center vectors before encoding to reduce angular concentration and make their directions more distinguishable. Since centering changes angles but preserves Euclidean distances, NARH uses angles estimated from centered binary codes and each vector's distance to the center to estimate original squared Euclidean distances. We further extend the estimator to inverted-file search with a separate mean for each posting list, using precomputed center projections to reduce expensive query-time projection computations. Our analysis provides a high-probability bound on squared-distance estimation error in terms of code length and residual norms, and a sufficient condition for preserving pairwise rankings. Experiments on four real-world datasets show that NARH reduces bit imbalance, improves recall at fixed reranking budgets, and achieves better search performance than binary hashing baselines based on random projection and Iterative Quantization (ITQ).