Bandwidth Efficient Near-Storage Accelerator for High-Dimensional Similarity Search
Gongjin Sun, Sang-Woo Jun · 2020
Performance of high-dimensional similarity search systems is often determined by the rate of distance calculation between a query and candidate neighbors. This is because as the dimensionality of data becomes higher, it suffers the so-called “curse of dimensionality”, which makes conventional indexing methods inefficient. Since the sheer size of datasets of interest often mandate storing them in secondary storage, this means the performance of a similarity search may be primarily limited by the storage device bandwidth, especially if the distance calculation can be offloaded to a high-performance accelerator built with GPUs or FPGAs. In this paper, we present ZipNN, which moves the bottleneck away from the storage performance in order to make more effective use of available computation resources. We achieve this via two approaches: First, ZipNN is a near-storage accelerator which takes advantage of the high internal bandwidth of storage. Second, it implements multiple pipelines of an application-optimized, wire-speed compression algorithm which can handle full storage bandwidth. We evaluate ZipNN using real-world datasets and an FPGA-based implementation. Compared to a comparable FPGA accelerator deployed in a standalone device, it demonstrates over 6× performance improvements. It also delivers an order of magnitude improvement compared to a purely software implementation.