Talk:K-d tree: Difference between revisions
Content added Content deleted
| Line 89: | Line 89: | ||
::: 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. |
::: 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. |
::: 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 and the tree is sufficiently large (and if it is implemented correctly). |
||
::: 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) |
::: 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) |
||