Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search
Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search
复制标题
DOI：
10.1145/3183713.3196925
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Yiqiu Wang;Anshumali Shrivastava;Jonathan Wang;Junghee Ryu
中科院分区：
文献类型：
--
作者：
Yiqiu Wang;Anshumali Shrivastava;Jonathan Wang;Junghee Ryu
我们提出Flash（F ast l sh l a lgorithm用于使用H PC加速加速的s Imaliality搜索），这是单台计算机上超高维数据集的相似性搜索系统，这不需要相似性计算，并且针对高性能计算平台量身定制。通过利用LSH样式随机索引程序并将其与多种原则性技术相结合，例如储层抽样，一pass minwise Hashing的最新进展和基于计数的估算，我们降低了相似性搜索的计算和并行化成本，同时保留了声音理论的理论。保证。我们评估来自不同域中的几个真实高维数据集的Flash，包括文本，恶意URL，点击直接预测，社交网络等。我们的实验为与具有数百万个维度的数据集相关的困难提供了新的启示。当前的最新实现要么在呈现的刻度上失败，要么是比闪存慢的数量级。 Flash能够在不到10秒的时间内通过整个WebSPAM数据集（13亿个NONZEROS）计算出近似K-NN图。使用Brute-Force（N2D）在WebSPAM数据集上不到10秒内计算完整的K-NN图将需要至少20个teraflops。我们提供FLASH的CPU和GPU实现，以复制结果。
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. 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 (n2D), will require at least 20 teraflops. We provide CPU and GPU implementations of FLASH for replicability of our results.