0
$\begingroup$

I am working on KD-Tree for nearest neighbor algorithm, where at each level of the tree we arbitrarily choose a dimension to cut upon and sort the points based on that chosen dimension value, after which we can choose mid-point to split upon such that dividing the points from that middle point will give us a balanced tree (has same number of points in either of the subtrees). At each level a single dimension is chosen and process is repeated.

For example: for data having dimensions (x,y,z) let's say first level of the tree 'X' is chosen at cut dimension, 'Y' at second level, 'Z' at third and then repeated again with 'X' again at fourth level and so on. So for first level all points are sorted according to dimension 'X' and split into left and right subtree based on the middle value of the sorted data.

I am sure you got the gist of it. Otherwise please read more here. KD-Tree (Wiki)

Now what I want to try something where rather than using each dimension at different level, I use all at the same level. i.e. I take points p(x,y,z) as vectors. But as you can guess if I do this, I have no way of ordering (not any I know of) the vectors (points) such that I can find a vector to divide upon hence still keeping my tree somewhat balanced.

PS: I am not much concerned about if it is actually a better or worse way of doing thing. Right now it's more about if it is possible to do it this way and then find out why it is better or worse.

Please ask if I should provide any more information or if I mentioned something wrong. I appreciate your help.

Please add more tags if appropriate, I couldn't find any.

Edit: Just to make it clear. Basically I want to be able to have an ordering which won't destroy the order based on distances. i.e. if a point/vector A has less distance from another point P, it comes first in the order than some farther point, let's say B. My end goal is to use this to try and create some kind of nearest neighbor algorithm.

$\endgroup$
  • $\begingroup$ It would help you to get answers if you added which environment you are working in (R? Python? etc.). $\endgroup$ – Richard Careaga Nov 18 '18 at 3:27
  • $\begingroup$ @RichardCareaga I am currently exploring python, though my question is mostly research based. So that if there is a way to order vectors I would like to know it to be able to use it for my purpose. But if there is an environment specific solution too, I would be happy to know. Thanks for the comment. $\endgroup$ – Ashok Suthar Nov 18 '18 at 9:23
3
$\begingroup$

If I understand your question correctly, you're looking for something that another (beyond KD-trees) standard space partitioning algorithm does. This one is called BSP-trees (for Binary Space Partition) and it uses vectors instead of dimensions for its space subdivision/partitioning. You can see it contrasted to KD-trees in slide 29 (previewed below) and beyond of this presentation.

The criterion that is used in the algorithm is intended to balance the data in the branches of the tree. This guides the definition of an order on vectors for what seems to be your purpose as well.

Otherwise, more generally speaking, one way to define a total order on a vector space is by identifying an order vector. Then your ordering is defined by the dot product with this vector. This represents projecting the entire space on the line defined by the vector and thus using the total order of the one-dimensional space it defines. For a more detailed explanation of the dot product, consider this video.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Appreciate the help. I will read on the information provided by you and see if it helps me for what I am looking for. I will let you know :) $\endgroup$ – Ashok Suthar Dec 26 '18 at 12:06
  • $\begingroup$ can you explain a bit about what you mean by "identifying an order vector", or guide me somewhere I can read about how it can be done. Are you suggesting for an arbitrary ordering vector to be chosen and sort every vector according to the dot product of that vector and order vector? Thanks in advance. $\endgroup$ – Ashok Suthar Dec 28 '18 at 7:22
  • $\begingroup$ Yes, but I wouldn't call it "arbitrary". You actually choose it in order to determine the direction of the order $\endgroup$ – mapto Dec 31 '18 at 13:57
  • $\begingroup$ @AshokSuthar, I've added a link to a video that visually explains how the dot product serves as a total order on a vector space. $\endgroup$ – mapto Jan 2 '19 at 8:35
  • $\begingroup$ Sorry for being so late. I understand how it can work, but am unable to understand how I can find an order vector? i.e. let's say I have some data, in terms of vectors. How do I find an order vector which can sort that accordingly? Is there something I am missing? $\endgroup$ – Ashok Suthar Feb 14 '19 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.