We present FLASH (Fast LSH Algorithm for Similarity search accelerated with HPC (High-Performance Computing)), a similarity search system for ultra-high dimensional datasets on a single machine, which does not require similarity computation. Our system is an auspicious illustration of the power of randomized algorithms carefully tailored for high-performance computing platforms. We leverage LSH style randomized indexing procedure and combine it with several principled techniques, such as, reservoir sampling, recent advances in one-pass minwise hashing, and count based estimations. The combination, while retaining sound theoretical guarantees, reduces the computational as well as parallelization overhead of our proposal. We provide CPU and hybrid CPU-GPU implementations of FLASH for replicability of our results1

 

We evaluate FLASH on several real high dimensional datasets coming from different domains including text, malicious URL, click-through prediction, social networks, etc.  FLASH is capable of computing an approximate k-NN graph, from scratch, over full webspam dataset (1.3 billion nonzeros) in less than 10 seconds. Computing full k-NN graph in less than 10 seconds on webspam dataset, using brute-force, will require at least 20 TFLOPS.  FLASH is even faster than computing 100 random projections of the data in parallel.

 

On our ultra-high dimensional benchmarks, FLASH is significantly faster than state-of-the-art implementation NMSLIB-HNSW algorithm.