We present FLASH ( %DIFDELCMD < {\bf %%% F ast%DIFDELCMD < {\bf %%% L SH%DIFDELCMD < {\bf %%% A lgorithm for%DIFDELCMD < {\bf %%% S imilarity search accelerated with %DIFDELCMD < {\bf %%% H PC(High-Performance Computing) \textbf{  ), 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 results URL We evaluate FLASH on several real high dimensional datasets coming from different domains  including text, malicious URL, click-through prediction, social networks, etc. Our experiments shed new light on the difficulties associated with datasets having several millions of dimensions. Current state-of-the-art implementations either fail on the presented scale or are orders of magnitude slower than our system . 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 (n^2D), will require at least 20 TFLOPS. We hope that FLASH gets adopted in practice .
We present FLASH ( %DIFDELCMD < {\bf %%% %DIFDELCMD < {\bf %%% %DIFDELCMD < {\bf %%% %DIFDELCMD < {\bf %%% FastLSHAlgorithm forS imilarity search accelerated with %DIFDELCMD < {\bf %%% \textbf{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 . We evaluate FLASH on several real , high-dimensional datasets from different domains , including text, malicious URL, click-through prediction, social networks, etc. Our experiments shed new light on the difficulties associated with datasets having several million dimensions. Current state-of-the-art implementations either fail on the presented scale or are orders of magnitude slower than FLASH . FLASH is capable of computing an approximate k-NN graph, from scratch, over the full webspam dataset (1.3 billion nonzeros) in less than 10 seconds. Computing a full k-NN graph in less than 10 seconds on the webspam dataset, using brute-force (n^2D), will require at least 20 teraflops. We provide CPU and GPU implementations of FLASH for replicability of our results .
D
F
D
ast
D
L
D
SH
D
A
D
lgorithm for
R
S
F
A
ast
A
L
A
SH
A
A
A
lgorithm for
A
S
D
H
D
PC(High-Performance Computing)
A
H
A
PC
R
which
that
R
computation. Our system is an auspicious illustration of the power of randomized algorithms carefully
computations and is
R
We leverage
By leveraging a
R
combine
combining
R
. The combination,
, we reduce the computational and parallelization costs of similarity search,
R
, 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 results URL We
. We
R
high dimensional datasets coming
, high-dimensional datasets
A
,
R
millions of
million
R
our system
FLASH
A
the
A
a
A
the
R
TFLOPS. We hope that FLASH gets adopted in practice
teraflops. We provide CPU and GPU implementations of FLASH for replicability of our results