4 ms·

Thx for reply. The difference between BSTs and k-trees is that balancing the tree is a huge misconception for k-trees. Also, in my paper, I pose some basic hyp

Thx for reply. The difference between BSTs and k-trees is that balancing the tree is a huge misconception for k-trees. Also, in my paper, I pose some basic hypothesis which are: data are points, without any indication of distribution and the search range is a convex in the point space. Something like a school case. With this hypothesis which are general, balancing the tree (ak. Octree) is a hard misconception coming from BST. It will be difficult to me to explain here why, but it's not really hard to see it. Take this exemple and my hypothesis: you have a logarithmic distribution of points in 1D (but you don't know it particularly) and you are searching the points in random continuous ranges, then the best tree is a total unbalanced tree. And note that my heuristic will gives you a total unbalanced tree. If you have regurlarly distributed points, my heuristic will gives you an octree. One day, I hope, I will find a damn good mathematician to prooves that the K-Means Tree is the best tree in the general hypothesis.:p or maybe i'm wrong =)

sesqu 15y ago
Without a distribution, the algorithms generally match what one would get with a uniform distribution, and convexity is a very small relaxation from a unit cube. These by themselves don't change much, provided the shape of the region is nice. Edit: actually, the convexity might - but then to actually use the convexity property, you'd have to move to theoretical distributions and maybe something like veb-trees. What do you mean by total unbalanced tree? For an exponential distribution, a complete tree would naturally be suboptimal. The real trouble, as I understand it, with k-trees using the median heuristic is that there is no total ordering in more than one dimension, barring special cases, and so binary partitionings can no longer keep all sought nodes inside them. If your larger point is that assuming a uniform distribution in octrees (instead of using a balanced tree structure) is vulnerable, then yes, I agree fully. If not, I'll conclude that you're talking about some sort of clustering, where the partitioning is spatial but the sought points are not necessarily described by a range. That's interesting, too.

sesqu 15y ago

Without a distribution, the algorithms generally match what one would get with a uniform distribution, and convexity is a very small relaxation from a unit cube. These by themselves don't change much, provided the shape of the region is nice. Edit: actually, the convexity might - but then to actually use the convexity property, you'd have to move to theoretical distributions and maybe something like veb-trees. What do you mean by total unbalanced tree? For an exponential distribution, a complete tree would naturally be suboptimal. The real trouble, as I understand it, with k-trees using the median heuristic is that there is no total ordering in more than one dimension, barring special cases, and so binary partitionings can no longer keep all sought nodes inside them. If your larger point is that assuming a uniform distribution in octrees (instead of using a balanced tree structure) is vulnerable, then yes, I agree fully. If not, I'll conclude that you're talking about some sort of clustering, where the partitioning is spatial but the sought points are not necessarily described by a range. That's interesting, too.