A Generic Inverted Index Framework for Similarity Search on the GPU

Jingbo Zhou, Qi Guo, H. V. Jagadish, Lubos Krcal, Siyuan Liu, Wenhao Luan, Anthony K. H. Tung, Yueji Yang, Yuxin Zheng
National University of Singapore
34th IEEE International Conference on Data Engineering (ICDE), 2018


   title={A Generic Inverted Index Framework for Similarity Search on the GPU},

   author={Zhou, Jingbo and Guo, Qi and Jagadish, H. V. and Krcal, Lubos and Liu, Siyuan and Luan, Wenhao and Tung, Anthony K. H. and Yang, Yueji and Zheng, Yuxin},



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 tau-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.
Rating: 5.0/5. From 1 vote.
Please wait...

* * *

* * *

* * *

HGPU group © 2010-2022 hgpu.org

All rights belong to the respective authors

Contact us: