In the paper, the codebook does not suffice uniformly distribution on the sphere, why does it work?

[chimborazo11]

https://arxiv.org/pdf/2409.09913

apparently it's not uniform: arctan(1.5/0.5) is not equal to pi11/12(pi/2-2pi/12/2, means the circle is divided by 12) nor pi7/8 (pi/2-2pi/16, means the circle is divided by 16 and regards 4 points on the axis). This situation remains in high-dimensional space, so how could theorem 3.2 work? as its basic assumption is 'vectors follow a random uniform distribution on a (D-1)-dimensions sphere'?

[gaoj0017]

"The codebook spread evenly on the unit sphere." is not an assumption of theorem 3.2, so I deliberately avoid using "the codebook distribute uniformly on the unit sphere". It explains the insights only. The point is that we want to spread the codebook as even as possible, but besides this consideration, there are other constraints on the design. For example, the codebook should better be generated from vectors of unsigned integers such that it can inherit the arthemetics. Overall, we prove that with this design of the codebook, the optimality (theorem 3.2) holds.

[chimborazo11]

Great work. I re-implement it recently and it works very well, but I still can not understand the mathematical relationship between this codebook and proofs in Appendix B. Since chapter 3.4 indicates the theoretical optimality is based on theorem 3.2, and theorem 3.2 is proved by Lemma B.1, I wonder 'the codebook vector distribute uniformly on the unit sphere' shall be an assumption?

[gaoj0017]

Here the "uniform distribution" is for "the data vectors after random rotation", so the statement always holds. It is not for the codebook vectors.

Apologize that we will archive this repo. For further issues, please feel free reach out in the RaBitQ Library repo :)

Link: https://github.com/VectorDB-NTU/RaBitQ-Library