请教, 谁对求欧氏距离最小值有研究

贺兰云天

原帖由 scutan 于 2009-1-8 21:48 发表


我的性能瓶颈在读数据上, 因为数据是数10G的文件中去查找. 所以想怎样先排序.

其实读只是一个基本的步骤，主要时间还是查找和排序了，看你采取什么查找方法了，而且提醒下，排序准则最重要了。。。。。
很显然 var key = (X-Y)^2+(X-Z)^2+·······是你要的目标排序键值。。。
不过这计算量就大了。。。。。比如 |X-Y| + |X-Z|+···也是一个标准，计算量少点，但是这个键值得到的最优值不一定就是最接近正确值的，换句话说，就是尽量把那个key的多项式拆开成计算简单的一个函数。。。后面的我当初没仔细研究

system888net

原帖由 scutan 于 2009-1-8 21:48 发表


我的性能瓶颈在读数据上, 因为数据是数10G的文件中去查找. 所以想怎样先排序.

用分布存储可有效的解决读数据文件的瓶颈.

poor-man

这个问题其实可以看做是两个向量之间的距离的问题.
假设有向量A和向量B，则有A-B=|a1-b1|+|a2-b2|+...+|an-bn|=(a1+a2+...+an)+(b1+b2+...+bn),
即向量之间的距离可以转化为两个向量各分量和之差。求一个向量到另外一组向量的最短距离就是求到该组向量各向量各分量和之差的最小值问题.
现在的问题是这些向量是无序的，所以你要查找的时候就需要到整个空间去搜索，这太耗费资源了，解决的办法就是将这些向量排序。
具体实现，可以用T树来实现，为了简化处理，可以将每个文件中的每组值转成int并累加，得到一个int值,用该值作为KEY，再用该值所在文件的路径作hash处理，并和该组值所在文件的偏移量合并将该值作为T树的VALUE，
查找的时候，先将向量也按这样的方式先生成一个KEY,再在T树中用该KEY找到离该KEY最近的一个KEY。因为T树是有序的，故可以很快找到向量最近的一个向量。
得到向量后，就可以得到该组值所在的文件及文件偏移量。

[ 本帖最后由 poor-man 于 2009-1-9 12:30 编辑 ]

mwishes

原帖由 poor-man 于 2009-1-9 11:08 发表
这个问题其实可以看做是两个向量之间的距离的问题.
假设有向量A和向量B，则有A-B=|a1-b1|+|a2-b2|+...+|an-bn|=(a1+a2+...+an)+(b1+b2+...+bn),
即向量之间的距离可以转化为两个向量各分量和之差。求一个向量 ...

理解, 用Trie树确实是个不错的建议,但是利用T树同样需要遍历所有文件:很显然生成T树便需要遍历...  您的做法是将求Euler距离演化到求绝对值之和,或者演化到T树的生成(距离最少可以在T树邻近节点中获得). 如果这个能满足需求的话, 显然是个不错的解决办法. 题设中有一点没有说明清楚的是: 到底是浮点的Euler距离计算是主要矛盾还是数据规模是主要矛盾, 这个需要楼主描述清楚下... 不知道分析是否有价值?

reiase

发现我被无视了，无穷范不就是“一个向量到另外一组向量的最短距离就是求到该组向量各向量各分量和之差的最小值”....

另外，可以考虑一下数据本身的特性，只搜索给定KEY的一个领域，但是这就要求用数据库了。把数据全放数据库里，给定一个KEY a，向数据库查询a的领域里的所有记录，领域使用无穷范数距离定义（一个向量到另外一组向量的最短距离就是求到该组向量各向量各分量和之差的最小值 ），然后对这个领域内的所有记录进行遍历，这个时候就可以使用二范距离了

cugb_cat

原帖由 scutan 于 2009-1-8 21:20 发表
通过测试发现目前90%的时间在于从硬盘读数据这儿, 已经使用了RAID了.
现在的CPU处理倒是蛮强的.

用数据库啊。

poor-man

我怀疑他在两个方面都有。前面好像说数据有10G，说明数据规模非常大，这么大的数据量，每次查询都要遍历整个数据，自然，浮点计算就成问题了。

poor-man

不要生气，呵呵！
只是大家表述不一样罢，我用我自己理解的方式来表达，你用数学语言来描述而已。

emacsnw

数据用kd-tree存储.

http://en.wikipedia.org/wiki/Kd-tree