NV-QALSH+: Locality-Sensitive Hashing Optimized for Non-volatile Memory

Locality-Sensitive Hashing (LSH) is a well-known method to solve the Approximate Nearest Neighbor (ANN) search problem. Query-Aware LSH (QALSH), a state-of-the-art LSH method, is a disk-based algorithm and suffers from high latency of disk I/O, even though it exploits disk-friendly B+-Trees as index data structures. On the other hand, DRAM-based methods occupy large amounts of expensive DRAM space and have long index rebuilt time. To solve the hardware problems, a variant of QALSH called NV-QALSH was proposed to leverage non-volatile memory (NVM), which combines the advantageous features of DRAM and disks. In this paper, we first study the projection mechanism, the core of QALSH, and find the value-to-position property of the projection. According to that property, we propose Interpolation Search Array (ISA), a novel array-based data structure, which is more efficient than B+-Trees under NVM. Finally, we extend NV-QALSH to NV-QALSH+ by replacing B+-Trees with ISA. The experimental results show that NV-QALSH+ is 7–48 \(\times \) faster than the disk-based QALSH. Additionally, NV-QALSH+ occupies extremely low DRAM space and can recover instantly with a near-zero index rebuilt time. Furthermore, NV-QALSH+ outperforms NV-QALSH in query speed, DRAM occupancy, and index rebuilt time.