Hacker News Reader

> For example, the typical distance computation complexity between two D-dimensional vectors is O(D^2), but compressing floats into bits reduces this by a factor of 1024 (32x32).

This isn't right, cosine distance between two vectors is definitely O(D)…

Of course replacing float multiplications with xor+popcount is a nice speedup in computation, but assuming you're memory bandwidth limited, speedup should be linear.

View on HN

Hi, I'm the author of the article. I think you're right, and we’ll update the description in the blog. Since binary operations are simpler than floating-point operations, the speedup could indeed be greater than 32x.

Some snippets:

> Leverages concentration of measure phenomena

> Uses anisotropic vector quantization to optimize inner product accuracy by penalizing errors in directions that impact high inner products, achieving superior recall and speed.

I only skimmed the article, but the 2 words I emphasized seems to imply they apply a quadratic metric for distance, i.e. they assume the data coordinates are with respect to non-orthogonal basis vectors, resulting in off-diagonal distance metric terms.

Hi, I'm the author of the article. We actually rely on a new quantization method called RaBitQ instead of ScaNN. You can read more about it at https://dev.to/gaoj0017/quantization-in-the-counterintuitive....

Reply on news.ycombinator.com