比较K-D树和蛮力搜索时间 [英] Comparison search time between K-D tree and Brute-force

问题描述

这是根据我编写的k-d树的大小和蛮力的执行速度的图形.指针集的数量固定为1 M(1,000,000)，并且Query测量执行的速度1000次.k-d树的增加很大，但蛮力不是.我想知道为什么会出现这些结果，以及如何加以改善.

This is a graph of the execution speed according to the dimension of the k - d tree and brute-force that I wrote. The number of pointer sets was fixed at 1 M (1,000,000), and Query measured the speed performed 1000 times. The increase in the k - d tree is huge, But brute-force is not. I wonder why these results have come out and how they can be improved.

推荐答案

一些想法:

• 性能可能在很大程度上取决于数据的特征.例如，数据点是否均匀分布，聚集或以其他方式排列?

• The performance may depend a lot on the characteristics of the data. For example, are the data points evenly distributed, clustered or otherwise arranged?

此外，您正在执行哪种查询?一种解释是您使用的是窗口查询，该查询返回整个点集或其中的大部分.在这种情况下，蛮力总是会更快.

Also, what is the kind of query you are performing? One explanation would be that you are using a window-query that returns the whole point set, or large parts of it. In that case, brute force will always be faster.

KD-Tree实施中是否可能存在缺陷?

Is there maybe a flaw in the KD-Tree implementation?

通常，人们都知道kD树在高维方面无法很好地扩展.因此，例如在机器学习中，维数通常会减小到10到20.但是，除非您在GPU上进行蛮力操作，否则KD-Tree应该更快.

Generally it is known that kD-Trees don't scale very well with high dimensionality. So, for example in machine learning, dimensionality is often reduced to be around 10 to 20. However, unless you do the brute force on a GPU, KD-Tree should be faster.

如果您正在寻找可以在高尺寸下更好地缩放的结构(插入/窗口查询)，请查看 R *树或 PH-树(后者是自-广告，目前限制为60个尺寸，但本周将发布高清版本).对于k近邻搜索，请查看 CoverTrees 或我的存储库中查看实现..我还实现了此处的R * Tree .

If you are looking for structures that scale better with high dimensions (insertion / window-query), have a look at R*Trees or the PH-Tree (the latter is self-advertisement and currently limited to 60 dimensions, but a high-dim version will be released this week). For k-nearest neighbor search, have a look at CoverTrees or BallTrees. If you are using Java, you can have a look at implementations in my repo. I also implemented an R*Tree here.

这篇关于比较K-D树和蛮力搜索时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！