PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometric Hashing in MPC with Applications to Clustering and Stochastic Embeddings

Sujoy Bhore, Arnold Filter, Eunjin Oh, Hyeonjun Shin, Himanshi Singh

arXiv:2610.21371v1cs.DScs.CG

TL;DR

Consistent hashing had been used in Euclidean MPC settings where it could be precomputed, but a parallel construction for input doubling metrics was missing. This paper constructs such hashes in fully scalable MPC and establishes a dimension-dependent lower-bound dichotomy. The resulting primitive supports scalable algorithms for geometric problems in doubling metrics.

  • Problem

    No parallel construction was known for consistent hashing when the metric arrived as input and could not be precomputed.

    Source: §1 · p. 5

  • Method

    For doubling metrics, the paper constructs a fully scalable MPC (Γ,2^O(ddim/Γ),∆)-consistent hash using O(ddim/σ^3) rounds.

    Source: §1.1 · p. 5, §3 · p. 10

  • Results

    For ddim ≤ O(σ log n), the hash construction takes O(ddim/σ^3) rounds, whereas ddim = Ω(σ log n) requires polynomially many rounds or n^(1−σ)·2^ddim total space.

    Source: §1.1 · pp. 5–6

  • Takeaways & Limitations

    The hashing primitive yields fully scalable MPC algorithms for stochastic tree embeddings with O(log n) expected distortion and constant-factor facility location in doubling metrics.

    Source: §4.1 · p. 21, §4.2 · p. 22

    The stated efficient construction assumes ddim ≤ O(σ log n) and a polynomially bounded aspect ratio; the lower-bound passage assumes no structural information beyond distance queries.

    Source: §1.1 · pp. 5–6, §5 · p. 25

Abstract

from arXiv · show

In this paper we study consistent hashing (a.k.a. sparse partitions) for doubling metrics in the Massively Parallel Computation (MPC) model. A $(\Gamma,\Lambda)$-hash with diameter bound $\Delta$ partitions a metric space into clusters of diameter at most $\Delta$ such that every ball of radius $\Delta/\Gamma$ intersects at most $\Lambda$ 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^\sigma$, that given an $n$-point metric space with doubling dimension $d\leq O(\sigma \log n)$, samples a randomized $(\Gamma,2^{O(d/\Gamma)})$-hash in $O(d/\sigma^3)$ rounds. There is a dichotomy: if the doubling dimension is $d=\Omega(\sigma\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/\sigma^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(\epsilon^{-2}),1+\epsilon)$-approximation for $k$-median and $k$-means.

1 Introduction

Consistent hashing had enabled geometric MPC algorithms in Euclidean space, but no parallel construction was known for input metrics that could not be precomputed. This paper constructs hashes for doubling metrics and uses them to obtain scalable algorithms, while establishing a dimension-dependent lower-bound dichotomy.

1.2 Related work

  • Prior consistent-hashing applications and recent MPC constructions described here were largely confined to Euclidean spaces, while many earlier clustering approaches required substantial local memory.The paper situates its work alongside sparse partitions, covers, scattering partitions, and shortcut partitions studied in other metric settings.Source: §1 · p. 4, §1.2 · p. 7

1 Introduction

  • Euclidean consistent hashing could be precomputed, but no parallel construction was known when the metric arrived as input and was unknown in advance.The paper frames its central question as whether fully scalable MPC can construct such hashes for broader metric spaces, including doubling metrics.Source: §1 · p. 5

1.1 Our contributions

  • For doubling dimension ddim ≤ O(σ log n), the paper constructs a (Γ,2^O(ddim/Γ),∆)-consistent hash in O(ddim/σ^3) rounds, assuming polynomially bounded aspect ratio.The padding-sparsity tradeoff is described as optimal; its expected-intersection analysis gives 2^O(ddim/Γ), approaching 1 as Γ grows.Source: §1.1 · p. 5
  • When ddim = Ω(σ log n), consistent hashing requires polynomially many rounds or n^(1−σ)·2^ddim total space, yielding a sharp dichotomy with the upper-bound regime.The lower-bound passage states this boundary in the fully scalable MPC setting.Source: §1.1 · p. 6
  • The hashing framework yields fully scalable algorithms for stochastic tree embeddings, facility location, k-median and k-means, EMD, and r-gather in doubling metrics.The stated guarantees include O(log n) expected embedding distortion, constant-factor facility-location approximation, and (1+ε,O(ε−2)) bicriteria approximation for k-median and k-means.Source: §1.1 · pp. 6–7

2 Preliminaries

The preliminaries define doubling metrics, nets, and the paper’s randomized consistent-hashing guarantees. They also explain why input-dependent hashing in doubling metrics requires explicit neighborhood hash pairs and describe the MPC tools used in the construction.

2 Preliminaries

  • A metric has doubling dimension ddim if every radius-r ball can be covered by at most 2^ddim balls of radius r/2; the packing property bounds separated points inside a ball.A (δ,δ′)-net covers every point within δ and separates distinct net points by at least δ′.Source: §2 · p. 8

Consistent hashing.

  • A randomized (Γ,Λ)-hash partitions a metric into clusters of diameter at most ∆, with expected at most Λ hash values on any set of diameter at most ∆/Γ.A hash value identifies a cluster, and the induced partition is called a sparse partition.Source: Consistent hashing · p. 8
  • Unlike Euclidean hashes, a hash for an input doubling metric must be computed with communication, so the paper explicitly tracks neighborhood hash pairs around each point.These pairs record point-hash indices reached within radius ∆/Γ; their expected number is n·Λ.Source: Consistent hashing · p. 8
  • The clustering framework assigns each point to the center maximizing its shift minus distance, using truncated exponential shifts to bound cluster diameter.Truncation bounds the shifts but removes the exponential distribution’s memorylessness.Source: Consistent hashing · p. 9
  • The stated MPC toolkit includes sorting, broadcast, and net construction, with the net routine producing a small net using O(n) total space.The net routine’s stated round complexity is O(log²_s n), with success probability 1−γ under its specified memory condition.Source: Consistent hashing · p. 9

3 Consistent hashing for doubling metrics

This section develops expected sparse partitions and fully scalable MPC consistent hashes for bounded-doubling metrics, with complexity depending on doubling dimension and local machine space. It also bounds the construction’s total space and extends the hashes with neighborhood oracles for cluster queries across a range of radii.

3.1 Sparse partition for doubling metrics

  • The partition based on MPX [MPX13] gives an expected intersection bound with vanishing overlap as ball radius shrinks, unlike ’s worst-case bound.The expected number of intersections approaches one as the radius approaches zero, a property used when applying the partition across recursion levels.Source: §3 · p. 10, §3.1 · pp. 11–12
  • For a net point q, the partition samples a truncated exponential shift and assigns each point to the center maximizing δq − dX(x,q), yielding clusters of diameter at most 3∆.The shifts have rate c·ddim/∆ and are truncated at ∆/2; truncation enforces the diameter bound.Source: §3.1 · pp. 10–11

3.2 MPC construction of sparse partition

  • The MPC algorithm recursively applies MPX clustering across clusters in parallel, retaining centers whose scores are within 2∆/Γ of the winner to represent approximate neighborhood hash pairs.It chooses nets small enough to fit on one machine and reduces cluster diameter at each recursive step.Source: §3.2 · pp. 12, 14
  • With Γ ≥ 16 and σ log n ≥ Ω(ddim), the MPC algorithm constructs a consistent hash and approximate neighborhood hash pairs in O(ddim/σ^3) rounds using Õ(n)·2^O(ddim/Γ) total space.The hash has expected intersection bound Λ = 2^O(ddim/Γ).Source: §3 · p. 10, §3.2 · p. 15
  • With high probability, the sparse-partition construction uses total space ˜O(n) ⋅ 2^O(ddim/Γ) after parallel trials amplify the expected-space bound.Each trial is aborted above twice the expected pair count; independent trials make the probability that all are aborted polynomially small.Source: §3.2 · p. 16

3.3 Neighborhood oracles for consistent hashing

  • The oracle table answers, for radii r ∈ [∆/(4Γ), ∆/(2Γ)], which clusters intersect the query ball in the extended metric.It reports cluster IDs from records whose stored thresholds are at most r.Source: §3.3 · pp. 16–17
  • For every dyadic scale, the algorithm constructs a hash on a common metric extension with parameters (Γ + 2, 2^O(ddim/Γ)) and diameter bound (1 + 2/Γ)∆.The construction computes the hashes and neighborhood-oracle tables simultaneously in O(ddim/σ^3) MPC rounds and ˜O(n) ⋅ 2^O(ddim/Γ) total space.Source: §3.3 · p. 17
  • For each scale i, O_i is a neighborhood oracle for ψ_i on X at scale R_i, and ψ_i is a (Γ + 2, 2O(ddim/Γ))-hash of (X′, dX′).For every scale i and cluster center q ∈ φ_i(X), A_i,q is 1-Lipschitz on (X, dX).Source: §3.3 · p. 19

4 Applications

The section applies the paper’s neighborhood-hash construction to doubling metrics, extending hashing-based MPC methods to several geometric problems. It gives algorithms for tree embeddings, facility location, k-median and k-means, and minimum-size clustering.

4 Applications

  • Neighborhood hash pairs for doubling metrics provide the primitive used to extend consistent-hashing MPC applications beyond Euclidean spaces.The construction runs in O(ddim/σ^3) rounds for ddim ≤ O(σ log n), with local space n^σ.Source: §4 · p. 20

4.1 Stochastic tree embeddings

  • For ddim ≤ O(σ log n), the algorithm samples an HST embedding with expected distortion O(Γ log Γ · log n) in O(ddim/σ^3) rounds.For constant doubling dimension and constant σ, the section states this gives optimal O(log n) expected distortion in O(1) rounds.Source: §4.1 · p. 21
  • The same tree-embedding approach gives an O(Γ log Γ · log n)-approximation for Earth Mover’s Distance in O(ddim/σ^3) rounds.The section identifies this as the first MPC algorithm for EMD in doubling metrics.Source: §4.1 · p. 21

4.2 Facility location

  • For ddim ≤ O(σ log n), the algorithm computes a Γ^O(z)-approximate uniform power-z facility-location solution in O(ddim/σ^3) rounds.For constant doubling dimension and constant σ, the section states an O(1)-approximation in O(1) rounds with near-linear total space.Source: §4.2 · p. 22

4.3 k-median and k-means

  • For fixed σ∈(0,1), every k∈N, z≥1, Γ≥16 and ε∈(0,1), an MPC algorithm on an n-point metric space with ddim≤O(σ log n) computes at most (1+ε)k centers with connection cost Lz(X,C)≤Γ^O(z)ε^-2·OPTcl.The special cases z=1 and z=2 are called k-Median and k-Means, respectively.Source: §4.3 · pp. 22–23

4.4 Minimum-size clustering

  • For fixed σ∈(0,1), Γ∈[4,ddim], r≥1, and arbitrarily small ε,γ>0, the algorithm computes an O(Γ log(1/ε))-approximate r-gather solution in O(ddim/(σ^3γ) · log(1/ε) · log n · log log n) rounds, using n^(1+γ+o(1)) · 2^O(ddim/Γ) total space.It constructs sparse H(R) graphs whose squares are approximate near-neighbor graphs, avoiding the need to store quadratic-size graphs explicitly.Source: §4.4 · pp. 24–25
  • For constant doubling dimension, r-gather has an O(log log log n)-approximation in O((log log n)^2) rounds and n^(1+γ) total space.The section describes r-gather as partitioning points into clusters of size at least r while minimizing the maximum cluster radius.Source: §4.4 · pp. 23, 25

5 Lower bounds

The lower bounds show that stochastic tree embeddings and consistent hashing require polynomially many MPC rounds for general metrics, and extend the boundary to metrics with doubling dimension on the order of σ log n. The arguments reduce these tasks to the query complexity of finding a closest pair using distance queries.

5 Lower bounds

  • The lower bounds assume distance-labeled MPC access, with no additional metric structure and distances obtained only through queries.The input is an n-point metric space distributed across machines.Source: §5 · p. 25

5.1 Stochastic tree embeddings

  • Any randomized c(n)-approximate closest-pair algorithm on the stated distance-oracle metrics requires Ω(n·2^ddim) queries.The lower bound assumes polynomially bounded distances and success probability at least 2/3.Source: §5.1 · p. 26
  • For stochastic embeddings, Ω(2^ddim/n^(ε+σ)) rounds are required, becoming Ω(n^(1−σ−ε)) for general metrics with ddim = log n.The theorem assumes polynomial expected distortion, O(n^(1+ε)) total space, and O(n^σ) local space.Source: §5.1 · p. 27

5.2 Consistent hashing

  • For consistent hashing, Ω(2^ddim/n^(ε+σ)) rounds are required, becoming Ω(n^(1−σ−ε)) when ddim = log n.The bound applies when the algorithm samples a (Γ,Λ)-hash and computes approximate neighborhood hash pairs with O(n^(1+ε)) total space and O(n^σ) local space.Source: §5.2 · p. 28
  • The hashing lower bound follows because its sampled hash and approximate neighborhood hash pairs reveal the closest pair without additional distance queries.With diameter bound Δ = Γ, the proof uses the hash collision or the approximate hash-pair set to identify that pair.Source: §5.2 · p. 28

5.1 Stochastic tree embeddings; 5.2 Consistent hashing

  • The upper-bound dimension restriction is tight for both tasks: achieving near-linear total space and 2^o(ddim) rounds requires ddim = O(σ log n).The embeddings comparison states ddim ≤ c·σ log n, while the hashing comparison gives the same scale with a possibly different constant.Source: §5.1 · p. 27, §5.2 · p. 28

Disclosure of AI assistance

The authors acknowledge ChatGPT Astra for discussions that helped inspire ideas in Section 3.3. They attribute all other research ideas and contributions to independent development by the authors, who take responsibility for the paper.

Disclosure of AI assistance

A Comparison with [Fil24]

This comparison contrasts the shift distributions and analyses in Lemma 4 and. Lemma 4 uses a smooth expected-intersection argument and conditional expectation for truncation, offering a simpler route to the earlier guarantee.

A Comparison with [Fil24]

  • Lemma 4 uses a truncated exponential distribution, whereas uses a beta-tailed exponential distribution with an atom at the threshold.The truncated distribution is smooth throughout; the beta-tailed distribution places mass at λ⊺.Source: A Comparison with [Fil24] · p. 34
  • [Fil24] uses a global argument that bounds the chance many nearby shifts are simultaneously beta-tailed, then applies the Lovász Local Lemma for a worst-case guarantee.Its analysis first establishes a gap between ordered center values before accounting for beta-tailing.Source: A Comparison with [Fil24] · p. 35
  • Lemma 4 bounds expected intersections with a smooth argument and incorporates truncation through simple conditional expectation.The paper says this provides the expected VOP guarantee needed there.Source: A Comparison with [Fil24] · p. 35
  • The simplified analysis also yields a simpler proof route to 's worst-case sparse-partition guarantee, with better hidden constants.It then uses the same Lovász Local Lemma argument as.Source: A Comparison with [Fil24] · p. 35

B MPC implementation details for EMD

The section gives an MPC approach to approximating EMD in doubling metrics through a random HST and a tree-metric matching computation. It contrasts this setting with a general-metric lower bound requiring polynomially many rounds for a specified accuracy.

B MPC implementation details for EMD

  • O(Γ log Γ · log n)-factor EMD approximation takes O(ddim/σ^3) rounds for ddim = O(σ log n), with Γ ≥ 16.The input sets have equal size, and local space is n^σ.Source: B MPC implementation details for EMD · p. 35
  • The algorithm finds an optimal matching in the random HST by processing nodes bottom-up and matching as many unmatched points as possible within each subtree.Unmatched excess is passed to the parent; the tree cost is computed from edge weights and the imbalance of A and B below each node.Source: B MPC implementation details for EMD · pp. 35–36
  • The HST dominates the original metric, and repeating the procedure O(log n) times in parallel allows the algorithm to return the smallest estimated value.The passage states this completes the proof of Corollary 2.Source: B MPC implementation details for EMD · p. 36
  • For general metrics, estimating unnormalized EMD within multiplicative error 1 + εδ/2 requires Ω(n^(1−ε−σ−δ)) rounds under the stated space bounds.The cited query lower bound applies for 0 < δ < 1 − ε − σ and the passage describes the resulting round count as n^Ω(1).Source: B MPC implementation details for EMD · p. 36
Loading 2610.21371v1…