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

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

作　　者：王钲旋[1] 李海军[2] 周春光[1] 

机构地区：[1]吉林大学计算机学院,吉林长春130012 [2]烟台大学计算机学院,山东烟台264005

出　　处：《小型微型计算机系统》2004年第12期2120-2125,共6页Journal of Chinese Computer Systems

基　　金：吉林省科技发展计划项目 ( 2 0 0 10 3 0 4-1)资助 .

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

关 键 词：高维数据空间 范围查找 街区距离 棋盘距离 欧氏距离 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]