Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search
Yiqiu Wang, Anshumali Shrivastava, Jonathan A. Wang, Junghee Ryu · 2018
We present FLASH (F ast L SH A lgorithm for S imilarity search accelerated with H PC), a similarity search system for ultra-high dimensional datasets on a single machine, that does not require similarity computations and is tailored for high-performance computing platforms. By leveraging a LSH style randomized indexing procedure and combining it with several principled techniques, such as reservoir sampling, recent advances in one-pass minwise hashing, and count based estimations, we reduce the computational and parallelization costs of similarity search, while retaining sound theoretical guarantees.