Consistent hashing method speeds up geometric computations in parallel systems
Geometric Hashing in MPC with Applications to Clustering and Stochastic Embeddings
Data Structures and AlgorithmsComputational Geometry
Summary
This paper solves the problem of dividing complex geometric data into manageable parts for fast processing on many computers working together. The authors develop a new way to create these divisions even when the shape and distances in the data are unknown beforehand. Their method works well in spaces with limited complexity and allows key tasks like grouping data points into clusters to be done quickly over multiple rounds of parallel computing. This makes it easier to handle important problems like facility location and clustering in large, complex datasets.
What this means in practice
- •For cloud computing engineers: Partition large metric datasets efficiently across parallel machines to accelerate geometric clustering and embedding computations.
- •For operations research teams: Run faster facility location and clustering approximations on big spatial data using scalable parallel hashing methods.
Authors
Sujoy Bhore, Arnold Filter, Eunjin Oh, Hyeonjun Shin, Himanshi Singh
Abstract
In this paper we study consistent hashing (a.k.a. sparse partitions) for doubling metrics in the Massively Parallel Computation (MPC) model. A $(Γ,Λ)$-hash with diameter bound $Δ$ partitions a metric space into clusters of diameter at most $Δ$ such that every ball of radius $Δ/Γ$ intersects at most $Λ$ clusters in expectation. Consistent hashing has emerged as a central tool in geometric MPC algorithms. However, so far it has been solely used in Euclidean spaces, where it can be pre-computed. On the other hand, in cases where the metric space is received as input and unknown in advance, no previous parallel construction was known. We present the first fully scalable MPC algorithm over machines with local space $n^σ$, that given an $n$-point metric space with doubling dimension $d\leq O(σ\log n)$, samples a randomized $(Γ,2^{O(d/Γ)})$-hash in $O(d/σ^3)$ rounds. There is a dichotomy: if the doubling dimension is $d=Ω(σ\cdot\log n)$, a polynomial number of rounds is required to compute such a hash. We conclude by showing that this MPC primitive yields $O(d/σ^3)$-round fully scalable MPC algorithms for a broad class of fundamental geometric problems in doubling metrics, including stochastic tree embeddings with $O(\log n)$ expected distortion, constant factor approximation for facility location, bicriteria $(O(ε^{-2}),1+ε)$-approximation for $k$-median and $k$-means.