A Generic Inverted Index Framework for Similarity Search on the GPU - Technical Report
This work addresses the challenge of simplifying GPU programming for similarity search, which is incremental as it builds on existing methods like LSH but introduces new components for broader applicability.
The authors tackled the problem of reducing programming complexity for parallel similarity search on GPUs by proposing GENIE, a generic inverted index framework that supports various data types and similarity measures, resulting in an efficient and effective system demonstrated through extensive experiments on real-life datasets and released as open source.
We propose a novel generic inverted index framework on the GPU (called GENIE), aiming to reduce the programming complexity of the GPU for parallel similarity search of different data types. Not every data type and similarity measure are supported by GENIE, but many popular ones are. We present the system design of GENIE, and demonstrate similarity search with GENIE on several data types along with a theoretical analysis of search results. A new concept of locality sensitive hashing (LSH) named $τ$-ANN search, and a novel data structure c-PQ on the GPU are also proposed for achieving this purpose. Extensive experiments on different real-life datasets demonstrate the efficiency and effectiveness of our framework. The implemented system has been released as open source.