Talk:K-d tree: Difference between revisions
→Dubious about speed claims here
Line 84:
:: You could say the same thing about any search tree if all you need is find one node. Search-trees are for repeated lookups, where tree construction is amortized. Once constructed, search complexity is the tree height which should be <math>O(log(N))</math> if the tree is reasonably full. Compare that to the sequential search's <math>O(N)</math>, the implication should be clear. --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 17:16, 6 June 2014 (UTC)
::: Yes, the implications are clear: for some searches, the cost of the kdtree search is cheaper than the cost of the brute force search. For other searches, the cost of the brute force search is cheaper than the cost of the kdtree search. Meanwhile, creating the kdtree always costs more than creating the original dataset.
::: To find when the amortized kdtree cost is cheaper than the brute force cost, you need to be aware of those costs as well as the cost of building the kdtree. You also need to have an idea of how many times the kdtree gets used, which is going to be, in the general case, an unknown.
::: Put differently: kdtrees are better than brute force for single point queries against a static dataset which receives a high volume of independent queries, if the volume is sufficiently high.
::: But other algorithms are also possible. For example, a n-dimensional grid (partitioning using evenly sized n-cubes). The grid approach has characteristics in common with both the brute force approach and the kdtree approach. What's best depends on the dataset and how often it gets updated, among other things (but other issues: cache architecture, use patterns, etc... also matter for determining cost, and the relevance of those costs). --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 18:43, 6 June 2014 (UTC)
| |||