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

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

On Computing for Replacing Eulideans Distance by Linear Combination of Cityblock and Chessboard Distances in High Dimensional Space

The problem of hypersphere range search in high dimensional space is: give a set of points in high dimensional space, input a point and a radius value, inquire about the number of points in given set these points are included in the hypersphere. A method for solving the problem was studied, and the method uses the linear combination of cityblock and chessboard distance in place of Eulidean distance in computing process. The efficiency was apparently improved as a result of decrease in number of multiplication. In order of improve precision, a way of how to select coefficents of linear combination was carefully discussed. The computational method that causes the selected coefficents to reach upper or lower determinate bound or optimal value in two conditions was given. The algorithm for given method was designed and implemented, and some experiments are carried out. The result shows that the algorithm was effective, and can be apply in many problems for computing distances in high dimensional space .