JHQ: Johnson-Lindenstrauss Enhanced Hierarchical Quantization for High-Dimensional Approximate Nearest Neighbor Search
Jiabao Han, Mengxuan Zhang, Goce Trajcevski · Proceedings of the VLDB Endowment · 2026
High-dimensional approximate nearest neighbor (ANN) search provides efficiency and scalability that are fundamental to modern AI applications such as retrieval-augmented generation and recommendation systems. While vector quantization (VQ) methods excel at compressing vectors for efficient search, existing approaches face critical bottlenecks: (i) prolonged indexing times due to expensive data-dependent training; (ii) slow query processing from quadratic distance computations; and (iii) poor scalability on large datasets. In this paper, we introduce a novel quantization framework that leverages the orthogonal Johnson-Lindenstrauss (JL) transformation to lay the foundation for resolving these bottlenecks. Our key insight is that the JL transformation induces a predictable near-Gaussian distribution with independent dimensions, enabling quick code-book generation without expensive iterative training. Based on this, we propose two algorithms: JQ (JL-enhanced Quantization) achieves fast indexing through training-free codebook construction while maintaining provable distance error bounds; and JHQ (JL-enhanced Hierarchical Quantization) extends JQ with a two-level architecture that uses primary quantization for rapid candidate filtering and residual quantization for accurate refinement, achieving a better query accuracy-speed trade-off on large-scale datasets. Finally, extensive experiments on six benchmark datasets with up to 3,072 dimensions demonstrate that our methods achieve 310× query speedups over state-of-the-art baselines at ≥95% recall, with 10–30× index construction speedups. In particular, JHQ excels on massive datasets, maintaining 210× higher queries per second at >90% recall compared to JQ.