通过组合地理空间索引进行多维搜索

Question

我构建了存储数百万个浮点向量的应用程序,每个向量具有~100维度.使用查询向量,我需要在这些向量中搜索k个最近(欧几里德)匹配.运行时间必须比扫描数百万个向量更快."向量"我的意思是在线性代数项中包含~100个浮点数的列表,即[0.3, -15.7, 0.004, 457.1, ...]

我知道像MySQL和MongoDB这样的数据库提供了适用于2维的空间索引.有没有办法使用复合索引将其适应更多维度？或者还有其他数据存储支持更多维度的索引？

Answer 1

如果您正在寻找精确匹配，100 个维度就很多了。如果您准备满足近似匹配，有一类局部敏感哈希方案。您可以为数据集生成一个散列或一系列散列值，并使用普通数据库或二维空间数据库根据散列值查找匹配项。一份参考资料是http://people.csail.mit.edu/indyk/p117-andoni.pdf。