Re: K-D tree or something similar

Discussion in 'Java' started by Roger Lindsjö, Jan 28, 2009.

  1. Ken T. wrote:
    > I have a need of a data structure similar to a k-d tree, but with the
    > ability to find the n nearest points in the data. Each two dimensional
    > point will be associated with an object. I might want to retrieve the
    > four objects nearest to the point 15,30 and their associated locations.
    >
    > I'd rather not have to roll my own since this seems like something that
    > would show up commonly. Is there an implementation of a K-D tree or
    > similar data structure that would allow me to do this?


    Did you serach for a implementation? On Google I searched for "java k-d
    tree" and got many hits.

    --
    Roger Lindsjö
    Roger Lindsjö, Jan 28, 2009
    #1
    1. Advertising

  2. Roger Lindsjö

    Tom Anderson Guest

    On Fri, 30 Jan 2009, Ken T. wrote:

    > On Wed, 28 Jan 2009 20:08:16 +0100, Roger Lindsjö wrote:
    >
    >> Ken T. wrote:
    >>> I have a need of a data structure similar to a k-d tree, but with the
    >>> ability to find the n nearest points in the data. Each two dimensional
    >>> point will be associated with an object. I might want to retrieve the
    >>> four objects nearest to the point 15,30 and their associated locations.
    >>>
    >>> I'd rather not have to roll my own since this seems like something that
    >>> would show up commonly. Is there an implementation of a K-D tree or
    >>> similar data structure that would allow me to do this?

    >>
    >> Did you serach for a implementation? On Google I searched for "java k-d
    >> tree" and got many hits.

    >
    > Yeah, I looked at a few of them. I can't seem to find one that will
    > allow me to search for n-nearest elements. I can find the nearest node,
    > but not the n-nearest.


    You can do that with a k-d tree. Sayeth wikipedia:

    In can provide the k-Nearest Neighbors to a point by maintaining k
    current bests instead of just one. Branches are only eliminated when they
    can't have points closer than any of the k current bests.

    I'm no dendrologist, but i have a vague understanding of how
    nearest-neighbour search works in a k-d tree, and i think i can see how to
    follow that advice. I'm sure you can work it out in enough detail to
    actually do it!

    I note that 'closer than any of the k current bests' really means 'closer
    than the furthest of the k current bests', and that this might be a good
    use for a SortedMap.

    tom

    --
    Only men's minds could have mapped into abstraction such a territory
    Tom Anderson, Jan 30, 2009
    #2
    1. Advertising

  3. Roger Lindsjö

    Lew Guest

    Tom Anderson wrote:
    >> I'm no dendrologist, but i have a vague understanding of how
    >> nearest-neighbour search works in a k-d tree, and i think i can see how
    >> to follow that advice. I'm sure you can work it out in enough detail to
    >> actually do it!
    >>
    >> I note that 'closer than any of the k current bests' really means
    >> 'closer than the furthest of the k current bests', and that this might
    >> be a good use for a SortedMap.


    Ken T. wrote:
    > Due to time constraints I was really hoping to find an implementation
    > that already supported this functionality. Any ideas?


    Start your homework assignment sooner.

    You posted your original question on Jan. 27, GMT. It is now Jan. 31, GMT.
    In the roughly 3 1/3 days since you posted your question, you might have
    googled for information, read the wikipedia article that Tom found, and coded
    your own solution.

    Or you might not have. My point is that Usenet is not often the fastest route
    to such a solution.

    --
    Lew
    Lew, Jan 31, 2009
    #3
  4. On Fri, 30 Jan 2009 21:16:38 -0500, Lew wrote:

    > Tom Anderson wrote:
    >>> I'm no dendrologist, but i have a vague understanding of how
    >>> nearest-neighbour search works in a k-d tree, and i think i can see
    >>> how to follow that advice. I'm sure you can work it out in enough
    >>> detail to actually do it!
    >>>
    >>> I note that 'closer than any of the k current bests' really means
    >>> 'closer than the furthest of the k current bests', and that this might
    >>> be a good use for a SortedMap.

    >
    > Ken T. wrote:
    >> Due to time constraints I was really hoping to find an implementation
    >> that already supported this functionality. Any ideas?

    >
    > Start your homework assignment sooner.
    >
    > You posted your original question on Jan. 27, GMT. It is now Jan. 31,
    > GMT. In the roughly 3 1/3 days since you posted your question, you might
    > have googled for information, read the wikipedia article that Tom found,
    > and coded your own solution.
    >
    > Or you might not have. My point is that Usenet is not often the fastest
    > route to such a solution.


    I found a Java K-D tree implementation that does N nearest neighbours in
    under 5 minutes of Googling. For the OP's edification, the search
    keywords were "K-D tree nearest neighbours"...seemed pretty obvious to me.

    And the link was on the _first_ results page using these keywords.

    AHS
    Arved Sandstrom, Jan 31, 2009
    #4
  5. Roger Lindsjö

    Tom Anderson Guest

    On Sat, 31 Jan 2009, Arved Sandstrom wrote:

    > On Fri, 30 Jan 2009 21:16:38 -0500, Lew wrote:
    >
    >> Tom Anderson wrote:
    >>>> I'm no dendrologist, but i have a vague understanding of how
    >>>> nearest-neighbour search works in a k-d tree, and i think i can see
    >>>> how to follow that advice. I'm sure you can work it out in enough
    >>>> detail to actually do it!
    >>>>
    >>>> I note that 'closer than any of the k current bests' really means
    >>>> 'closer than the furthest of the k current bests', and that this might
    >>>> be a good use for a SortedMap.

    >>
    >> Ken T. wrote:
    >>> Due to time constraints I was really hoping to find an implementation
    >>> that already supported this functionality. Any ideas?

    >>
    >> Start your homework assignment sooner.
    >>
    >> You posted your original question on Jan. 27, GMT. It is now Jan. 31,
    >> GMT. In the roughly 3 1/3 days since you posted your question, you might
    >> have googled for information, read the wikipedia article that Tom found,
    >> and coded your own solution.


    Yup. I reckon if i had the source of a k-d implementation, and that
    wikipedia article, i could add N-nearest-neighbour searching in under an
    hour. If i was planning, i'd estimate it as a quarter-day task including
    writing the tests, refactoring, and contingency.

    >> Or you might not have. My point is that Usenet is not often the fastest
    >> route to such a solution.


    And sometimes you just have to man up and write some code.

    > I found a Java K-D tree implementation that does N nearest neighbours in
    > under 5 minutes of Googling. For the OP's edification, the search
    > keywords were "K-D tree nearest neighbours"...seemed pretty obvious to me.
    >
    > And the link was on the _first_ results page using these keywords.


    Or i'd contract Arved to find an implementation for me!

    tom

    --
    Technology is anything that wasn't around when you were born. -- Alan Kay
    Tom Anderson, Jan 31, 2009
    #5
  6. On Sat, 31 Jan 2009 13:47:44 +0000, Ken T. wrote:

    > On Sat, 31 Jan 2009 02:29:28 +0000, Arved Sandstrom wrote:
    >
    >> On Fri, 30 Jan 2009 21:16:38 -0500, Lew wrote:
    >>
    >>> Tom Anderson wrote:
    >>>>> I'm no dendrologist, but i have a vague understanding of how
    >>>>> nearest-neighbour search works in a k-d tree, and i think i can see
    >>>>> how to follow that advice. I'm sure you can work it out in enough
    >>>>> detail to actually do it!
    >>>>>
    >>>>> I note that 'closer than any of the k current bests' really means
    >>>>> 'closer than the furthest of the k current bests', and that this
    >>>>> might be a good use for a SortedMap.
    >>>
    >>> Ken T. wrote:
    >>>> Due to time constraints I was really hoping to find an implementation
    >>>> that already supported this functionality. Any ideas?
    >>>
    >>> Start your homework assignment sooner.
    >>>
    >>> You posted your original question on Jan. 27, GMT. It is now Jan. 31,
    >>> GMT. In the roughly 3 1/3 days since you posted your question, you
    >>> might have googled for information, read the wikipedia article that
    >>> Tom found, and coded your own solution.
    >>>
    >>> Or you might not have. My point is that Usenet is not often the
    >>> fastest route to such a solution.

    >>
    >> I found a Java K-D tree implementation that does N nearest neighbours
    >> in under 5 minutes of Googling. For the OP's edification, the search
    >> keywords were "K-D tree nearest neighbours"...seemed pretty obvious to
    >> me.
    >>
    >> And the link was on the _first_ results page using these keywords.

    >
    > I appreciate the pointer, but as with most requests for implementations
    > of algorithms in this group, I was really looking for recommendations
    > from people who had used the implementation. You're absolutely right, I
    > could code it myself, but that would distract from the real task I'm
    > working on. I could just download a bunch of implementations and try
    > them all out, but one of the points of USENET is to get feedback on
    > things like this.
    >
    > I chose USENET not to find a pointer to a single implementation, but to
    > find a recommendation of one over the others. That isn't something I
    > could really get from google.
    >
    > I understand that few people have used code like this now, so I'll
    > probably modify one of the implementations I looked at already, or use
    > the one you just pointed to.
    >
    > Again, thank you all for the pointers.


    Consider it an implicit recommendation...as much of one as I can make
    without testing it myself. I perused the website, and made sure it wasn't
    code dashed out by some script kiddies. In other words, in your shoes
    this is the first implementation I found that I would have tried.

    AHS
    Arved Sandstrom, Jan 31, 2009
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mike42
    Replies:
    21
    Views:
    17,308
    Chris Uppal
    Nov 14, 2005
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,076
  3. Bo Peng
    Replies:
    31
    Views:
    780
    Ron Adam
    Jun 30, 2005
  4. Replies:
    0
    Views:
    329
  5. JimmyD
    Replies:
    0
    Views:
    321
    JimmyD
    Sep 19, 2006
Loading...

Share This Page