  Approximate Nearest Neighbour Search (ANNS) is a subroutine in algorithms
routinely employed in information retrieval, pattern recognition, data mining,
image processing, and beyond. Recent works have established that graph-based
ANNS algorithms are practically more efficient than the other methods proposed
in the literature, on large datasets. The growing volume and dimensionality of
data necessitates designing scalable techniques for ANNS. To this end, the
prior art has explored parallelizing graph-based ANNS on GPU leveraging its
high computational power and energy efficiency. The current state-of-the-art
GPU-based ANNS algorithms either (i) require both the index-graph and the data
to reside entirely in the GPU memory, or (ii) they partition the data into
small independent shards, each of which can fit in GPU memory, and perform the
search on these shards on the GPU. While the first approach fails to handle
large datasets due to the limited memory available on the GPU, the latter
delivers poor performance on large datasets due to high data traffic over the
low-bandwidth PCIe bus. In this paper, we introduce BANG, a first-of-its-kind
GPU-based ANNS method which works efficiently on billion-scale datasets that
cannot entirely fit in the GPU memory. BANG stands out by harnessing compressed
data on the GPU to perform distance computations while maintaining the graph on
the CPU. BANG incorporates high-optimized GPU kernels and proceeds in stages
that run concurrently on the GPU and CPU, taking advantage of their
architectural specificities. We evaluate BANG using a single NVIDIA Ampere A100
GPU on ten popular ANN benchmark datasets. BANG outperforms the
state-of-the-art in the majority of the cases. Notably, on the billion-size
datasets, we are significantly faster than our competitors, achieving
throughputs 40x-200x more than the competing methods for a high recall of 0.9.
