Tree Embedding in High Dimensions: Dynamic and Massively Parallel, and Streaming Facility Location in High Dimension via Geometric Hashing – 2
Published:
Tree Embedding in High Dimensions
Dynamic and Massively Parallel, and Streaming Facility Location via Geometric Hashing
So this is going to be a template for a future post: I have been reading the papers Tree Embedding in High Dimensions: Dynamic and Massively Parallel and Streaming Facility Location in High Dimension via Geometric Hashing. So, I am going to make some sense out of these papers, and hopefully, I will be able to use the geometric hashing method to come up with ideas and problems on how to tackle them and how to work through a problem-solving session. Well, both problems at hand seem very geometrical, and the existence of the hash functions really makes life easier, so if we have hash functions based on the ideas of these papers, we can do two things: firstly, we can run a sort of importance sampling, as in discretizing settings, where the balance of the density of the points may not be equal, so in the case that uniform sampling does not work. Secondly, we can find the related points in a dynamic setting and do some calculations thereafter, so in a geometric problem, for example, such as k-means or metric embeddings, we can use the inherent nature of the hash functions to run our algorithm in a dynamic setting, albeit in a probabilistic setting. Let’s first mention some theorems and contemplate them.
Definition ($(\Gamma,\Lambda)$-hash function). A (randomized) hash function
\[\phi : \mathbb{R}^d \rightarrow \mathbb{R}^d\]is called a $\Gamma$-gap $\Lambda$-consistent hash with diameter bound $\tau>0$, or simply a $(\Gamma,\Lambda)$-hash function, if it satisfies the following properties:
(Diameter) For every image $z \in \phi(\mathbb{R}^d)$, \(\operatorname{diam}\!\left(\phi^{-1}(z)\right) \le \tau.\)
(Consistency) For every set $S \subseteq \mathbb{R}^d$ with \(\operatorname{diam}(S) \le \frac{\tau}{\Gamma},\) we have \(\mathbb{E}\!\left[\,|\phi(S)|\,\right] \le \Lambda.\)
Theorem 4.2.
Assume there exists a \((\Gamma,\Lambda)\)-hash \(\phi : \mathbb{R}^d \to \mathbb{R}^d\) with diameter bound \(\tau\) such that for \(p \in \mathbb{R}^d\), the hash value \(\phi(p)\) and the set of hash values \(\phi(B(p,\tau/\Gamma))\) can be evaluated in \(O(\mathrm{poly}(d))\) and \(O(|\phi(B(p,\tau/\Gamma))|\cdot \mathrm{poly}(d))\) time, respectively.
Then there exists a dynamic algorithm which, for a dynamic set of points \(P \subseteq \mathbb{R}^d\) with \(|P|\le n\) undergoing point insertions and deletions, maintains a tree embedding of \(P\) with \(O(\Gamma \log \Gamma \log n)\) distortion in \(\widetilde{O}(d+\Lambda)\) expected amortized update time.
The underlying tree embedding is rebuilt by the algorithm after every $n$ updates. An update to the input points $P$ results in \(\widetilde{O}(1)\) expected updates to the tree embedding of the following types:
- Type 1: A leaf of the embedding becomes inactive in the sense that no point in $P$ corresponds to it.
- Type 2: A new leaf and a path connecting the leaf to an existing node in the tree embedding are inserted into the embedding.
Theorem 3.1. There is a one-pass randomized algorithm that, given $P \subseteq [\Delta]^d$ presented as a dynamic geometric stream, samples a random point $p^* \in P \cup {\bot}$ such that
\[\forall x \in P,\quad \Pr[p^* = x] \ge \Omega\!\left(\frac{1}{\mathrm{poly}(d \cdot \log \Delta)}\right)\cdot \frac{r_x}{\sum_{y \in P} r_y},\]and also reports a 2-approximation $\widehat{\Pr}[p^*]$ for the probability of sampling this point, i.e.,
\[\Pr[p^* = x] \le \widehat{\Pr}[p^*] \le 2\,\Pr[p^* = x].\]This algorithm uses $\mathrm{poly}(d \cdot \log \Delta)$ bits of space, and fails with probability at most $1/\mathrm{poly}(\Delta^d)$.
