
Too many layers: In previous works, each data point \(x_i\)  is sub-sampled independently in \(R\)  layers, i.e, generates \(R\)  subsets of coordinates \(S_i^1,\dots , S_i^R\subset [d]\) . The sketch of the query point \(S(q)\)  then needs to be compared to each \(S(x_i)\)  in every layer. Since there are \(R = \Omega (n)\)  layers in [1]}, [2]} of size \(\Omega (d)\)  across all all data points, the total time complexity will be at least \(\Omega (n d)\) , which is the trivial query time.

Non-linearity:  The aforementioned sketching algorithms [1]}, [2]} involve nonlinear operations, and thus cannot be directly used for distance estimation.

Slow decoding:  The aforementioned sketches take linear time to decode the distance from the sketch, which is too slow for our application.

