information-retrieval - 存储一组点（嵌入）以便快速计算最近点的查询的最有效方法是什么
问题描述
给定一组嵌入，即一组[名称，向量表示]，我应该如何存储它以便快速计算对最近点的查询。例如，给定二维空间中的 100 个嵌入，如果我在最接近 (10,12) 的 5 个点上查询数据结构，它将返回 { [a,(9,11.5)] , [b,(12,14) ]，...}
简单的方法是计算所有距离，排序并返回前 k 个点。或者，人们可能会考虑以 mXn 空间的块/单位存储在二维数组中，以覆盖嵌入空间的范围。我不认为这可以扩展到更高的维度，但我愿意被纠正。
解决方案
您可以使用标准的近似最近邻库，例如faiss、flann、java-lsh等（基于LSH或Product Quantization）。
最快的解决方案（我发现它很有用）是通过使用Johnson-Lindenstrauss变换将（比如 100 维）向量转换为长变量（64 位）。然后，您可以使用汉明相似度（即 64 减去XOR b中设置的位数）来计算位向量a和b之间的相似度。您可以使用POPCOUNT机器指令来达到这种效果（非常快）。
实际上，如果您在 C 中使用POPCOUNT，即使您对整个二进制转换向量集（64 位的长变量）进行完整迭代，它仍然会非常快。