3-d中的点由(x,y,z)定义.任何两个点(X,Y,Z)和(x,y,z)之间的距离d是d = Sqrt [(Xx)^ 2 +(Yy)^ 2 +(Zz)^ 2].现在文件中有一百万个条目,每个条目都是空间中的某个点,没有特定的顺序.给定任意点(a,b,c)找到最近的10个点.您将如何存储百万点以及如何从该数据结构中检索这10个点.
鉴于我的知识库中有以下内容:
1 0 6 20 0 0 6 20
1 0 3 6 0 0 3 6
1 0 15 45 0 0 15 45
1 0 17 44 0 0 17 44
1 0 2 5 0 0 2 5
Run Code Online (Sandbox Code Playgroud)
我希望能够找到以下向量的最近邻居:
1 0 5 16 0 0 5 16
Run Code Online (Sandbox Code Playgroud)
根据距离度量.所以在这种情况下,给定一个特定的阈值,我应该发现列出的第一个向量是给定向量的近邻.目前,我的知识数据库的大小大约为数百万,因此计算每个点的距离度量,然后进行比较证明是昂贵的.对于如何以显着的加速实现这一目标,还有其他选择吗?
我几乎对任何方法都持开放态度,包括在MySQL中使用空间索引(除了我不完全确定如何解决这个问题)或某种哈希(这将是伟大的,但我不完全确定).