高维空间中用计算街区和棋盘距离的线性组合代替计算欧氏距离

摘要

在高维空间中点的超球范围查找问题是:已知一个高维数据点集,输入一个点和半径数值,询问所确定超球范围内包含有给出点集中哪些点.考查了解决这个问题时利用计算街区和棋盘距离的线性组合代替计算欧氏距离的方法.这一方法由于减少了乘法计算而明显地可以提高效率.为提高计算精度,对如何选择构造线性组合时的系数进行了深入分析,提出了使选择系数达到上、下确界或最优值的计算方法.为提出的方法设计了实现算法并进行了运行实验.结果表明方法是有效的,可以应用到有关高维空间中距离计算的广泛问题中.