News for hackers. Stuff that matters.
Re:Why HNSW is not the answer and disk-based alternatives mi... by tveita on Monday December 23, 2024 @03:23PM (#42497307)
> 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.

Re:Why HNSW is not the answer and disk-based alternatives mi... by DoctorOetker on Monday December 23, 2024 @07:43PM (#42498772)
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.

Re:Why HNSW is not the answer and disk-based alternatives mi... by VoVAllen on Monday December 23, 2024 @10:29PM (#42499520)
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....
Re:Why HNSW is not the answer and disk-based alternatives mi... by VoVAllen on Monday December 23, 2024 @10:27PM (#42499512)
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.