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
Optimize QuadTree to find K Nearest Neighbors
python;performance;python 2.7;computational geometry;clustering