Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation

• URL: http://arxiv.org/abs/2008.03260v2
• Date: Mon, 17 Aug 2020 22:48:52 GMT
• Title: Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation
• Abstract summary: SLASH is a distributed system for approximate similarity search over terabyte scale datasets. We show how SLASH can index this 2.3 terabyte data over 20 nodes in under an hour, with query times in a fraction of milliseconds.
• Score: 40.75034970144169
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present SLASH (Sketched LocAlity Sensitive Hashing), an MPI (Message Passing Interface) based distributed system for approximate similarity search over terabyte scale datasets. SLASH provides a multi-node implementation of the popular LSH (locality sensitive hashing) algorithm, which is generally implemented on a single machine. We show how we can append the LSH algorithm with heavy hitters sketches to provably solve the (high) similarity search problem without a single distance computation. Overall, we mathematically show that, under realistic data assumptions, we can identify the near-neighbor of a given query $q$ in sub-linear ($ \ll O(n)$) number of simple sketch aggregation operations only. To make such a system practical, we offer a novel design and sketching solution to reduce the inter-machine communication overheads exponentially. In a direct comparison on comparable hardware, SLASH is more than 10000x faster than the popular LSH package in PySpark. PySpark is a widely-adopted distributed implementation of the LSH algorithm for large datasets and is deployed in commercial platforms. In the end, we show how our system scale to Tera-scale Criteo dataset with more than 4 billion samples. SLASH can index this 2.3 terabyte data over 20 nodes in under an hour, with query times in a fraction of milliseconds. To the best of our knowledge, there is no open-source system that can index and perform a similarity search on Criteo with a commodity cluster.

Related papers

• Log-Time K-Means Clustering for 1D Data: Novel Approaches with Proof and Implementation [0.0]
  This thesis bridges theory and practice for 1D $k$-means clustering, delivering efficient and sound algorithms. Benchmarks demonstrate over a 4500x speedup compared to scikit-learn for large datasets.
  arXiv  Detail & Related papers  (2024-12-19T09:03:39Z)
• Distributed Collapsed Gibbs Sampler for Dirichlet Process Mixture Models in Federated Learning [0.22499166814992444]
  This paper proposes a new distributed Markov Chain Monte Carlo (MCMC) inference method for DPMMs (DisCGS) using sufficient statistics. Our approach uses the collapsed Gibbs sampler and is specifically designed to work on distributed data across independent and heterogeneous machines. For instance, with a dataset of 100K data points, the centralized algorithm requires approximately 12 hours to complete 100 iterations while our approach achieves the same number of iterations in just 3 minutes.
  arXiv  Detail & Related papers  (2023-12-18T13:16:18Z)
• DeepLSH: Deep Locality-Sensitive Hash Learning for Fast and Efficient Near-Duplicate Crash Report Detection [0.29998889086656577]
  With real-time streaming bug collection, systems are needed to quickly answer the question: What are the most similar bugs to a new one?, that is, efficiently find near-duplicates. LSH has not been considered in the crash bucketing literature. We introduce DeepLSH, a Siamese architecture with an original loss function, that perfectly approximates the locality-sensitivity property.
  arXiv  Detail & Related papers  (2023-10-10T15:26:27Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search [57.18075258042082]
  This competition compares ANNS algorithms at billion-scale by hardware cost, accuracy and performance. We compiled six diverse billion-scale datasets, four newly released for this competition.
  arXiv  Detail & Related papers  (2022-05-08T02:41:54Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings [18.916058638077274]
  This paper focuses on non-parametric and data-independent learning from set-structured data using approximate nearest neighbor (ANN) solutions. We propose Sliced-Wasserstein set embedding as a computationally efficient "set-2-vector" mechanism that enables downstream ANN. We demonstrate the effectiveness of our algorithm, denoted as Set-LOcality Sensitive Hashing (SLOSH), on various set retrieval datasets.
  arXiv  Detail & Related papers  (2021-12-11T00:10:05Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  Methods have to trade between obtaining high accuracy while maintaining load balance and scalability in distributed settings. We propose a novel approach called IRLI, which iteratively partitions the items by learning the relevant buckets directly from the query-item relevance data. We mathematically show that IRLI retrieves the correct item with high probability under very natural assumptions and provides superior load balancing.
  arXiv  Detail & Related papers  (2021-03-17T23:13:25Z)
• LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew [58.21885402826496]
  All-pairs set similarity is a widely used data mining task, even for large and high-dimensional datasets. We present a new distributed algorithm, LSF-Join, for approximate all-pairs set similarity. We show that LSF-Join efficiently finds most close pairs, even for small similarity thresholds and for skewed input sets.
  arXiv  Detail & Related papers  (2020-03-06T00:06:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.