Is there a KDTree that provides an iterator in Python3?

  kdtree, python-3.x, scikit-learn, scipy

A KDTree is a tree indexed by N-D position in space. If I have an item with coordinate [1,2,3] and another item with coordinate [1.0001,2,3], then a KDTree would return this nearest neighbor in a single O(logN) operation.

I have an algorithmic approach where I would like to sort the whole set of items in the KDTree by distance from the incident object.

incident_obj_coords = coords(incident_obj)
sorting = myKDTree.query(incident_obj_coords, count=len(myKdTree))

Then, I proceed along my sorting to find the best item:

score_threshold = 0.95
best_score = -inf
best_item = None
for item in sorting:
    score = similarity(item, incident_obj)
    if score > best_score:
        best_item = item
        best_score = score
    if score > score_threshold:
        break

Well, the above situation has complexity O(N*log(N)); what I would like is an O(log(N)) amortized runtime.

In order to get an O(log(N)) amortized runtime during the query, I need a KDTree.query_iterator that only gets the next item in the query when I need it (lazily):

score_threshold = 0.95
best_score = -inf
best_item = None
kd_it = myKDTree.query_iterator(incident_obj_coords)
while True:
    nxt = next(kd_it,None)
    
    if nxt is None:
        break
    
    score = similarity(item, incident_obj)

    if score > best_score:
        best_item = item
        best_score = score

    if score > score_threshold:
        break

Is there a KDTree in the python3 toolkit that can provide this sort of incremental search?

Source: Python-3x Questions

LEAVE A COMMENT