davidmoten/rtree

How to do an incremental knn search?

Open

#163 opened on Nov 30, 2022

View on GitHub
 (5 comments) (0 reactions) (0 assignees)Java (209 forks)batch import
help wantedquestion

Repository metrics

Stars
 (1,038 stars)
PR merge metrics
 (Avg merge 1m) (1 merged PR in 30d)

Description

Incremental knn search save the priority queue in each round generated by knn search if best-first strategy is adopted, and use priority queue saved in the previous round to search knn in the current round. I want to do an incremental knn search. Does anyone can teach me, thank you very much!

Contributor guide

Research direction
To implement incremental kNN search in rtree, you need to modify the knn search method to accept a priority queue from the previous round. The standard knn search uses a best first strategy that maintains a priority queue of nodes to visit. For incremental search, after each round k, save the priority queue state. In the next round for k+1, resume from that saved queue. Ensure that the queue is sorted by distance to the query point. Also handle the case where the tree structure is dynamic (insertions/deletions). Refer to the existing knn implementation in the codebase.
Tech stack
java
Domain
backend
Issue type
Research
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
3
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
Half day
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
Active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
Clear
Prerequisites
JavaR tree concepts
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
40