Appendix

The existence of such a subgraph is guaranteed (See Lemma 3). Let x,y Rn be vectors of dimensionn. We choose a random embeddingZP Das thepivot (line 2), based on which wesplittheremaining embeddings intofourgroups (lines3-8). Thisprocess continues recursively on each group (lines 9-10) till a partition gets empty (line 1). D.3 k-NNquery k-NN utilizes the same bounds from Alg. 2 to prune and prioritize the search space.