2
\$\begingroup\$

I'm looking a way to make my k nearest neighbors search more efficient. The context of the question is that I'm given a list of topics that have a unique ID (integer) and a (x,y) coordinate (floats) associated with each topic. Subsequently, I'm given another point and the number of nearest topics to find around the given point. The topics need to be returned in order of distance to the point. However, if the distance between two topics is <= .001, the topic with the larger ID should come first. Here's the full description if you're looking for a better description: http://www.quora.com/challenges#nearby.

My solution is implemented using a QuadTree. I'm looking for ways to make the search function of the QuadTree faster.

In addition to the four quadrants (children QuadTrees), the QuadTree class has two member variables x and y representing the point at which it is split into northeast, northwest, southeast, and southwest. Both findTopics() and findTopicsWithinRadius() are functions of the QuadTree.

class Topic:
    def __init__(self, x, y, val):
        self.id = val
        self.x = x
        self.y = y

# point: (x,y) tuple
# numResponses: integer    
def findTopics(self, point, numResponses):
    radius = 1
    topicToDistance = {}
    update = topicToDistance.update
    while len(topicToDistance) < numResponses:
        # dont want to see topics in previous searches
        update(self.findTopicsWithinRadius(point, radius, radius/2))
        radius += radius # faster to add radius to itself than multiply by 2
    def firstGreaterCmp(a, b):
        if abs(a[1]-b[1]) <= .001:
            if a[0].id < b[0].id:
                return 1
        if a[1] > b[1]:
            return 1
        return -1
    topics = sorted(topicToDistance.items(), cmp=firstGreaterCmp)
    # sorting by key may be faster than using a cmp function
    topics = [x[0].id for x in topics]
    return topics[:numResponses]

# search for topics around the given point with distance in the range of [minimum, radius]
# minimum is used so topics are not considered more than once
# point: (x,y) tuple
# radius: integer
# minimum: int    
def findTopicsWithinRadius(self, point, radius, minimum=0):
    topics = {}
    if not self.northwest:
        # this is a leaf
        for topic in self.topics:
            dist = distance((topic.x, topic.y), point)
            if minimum <= dist <= radius:
                topics[topic] = dist
        return topics
    # check subtrees
    if self.x >= point[0]-radius and self.y <= point[1]+radius:
        topics.update(self.northwest.findTopicsWithinRadius(point,radius, minimum))
    if self.x <= point[0]+radius and self.y <= point[1]+radius:
        topics.update(self.northeast.findTopicsWithinRadius(point,radius, minimum))
    if self.x >= point[0]-radius and self.y >= point[1]-radius:
        topics.update(self.southwest.findTopicsWithinRadius(point,radius, minimum))
    if self.x <= point[0]+radius and self.y >= point[1]-radius:
        topics.update(self.southeast.findTopicsWithinRadius(point,radius, minimum))
    return topics
\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.