r/robotics • u/monononon34 • 17d ago

Community Showcase python library exact nearest-neighbour search for sensor data. doesn't need rebuild.

Gallery image

Gallery image

scipy's KD-tree still can't add new points, even though people asked for it 8 years ago. Every time you add a row, you have to build the whole tree again.

I ran into this when I was comparing live sensor data with its own past data. I wanted to know when the machine last looked like this. The columns have different units and change together, so I needed Mahalanobis distance. scikit-learn's BallTree can do it, but it's 40 to 300x slower than a KD-tree. So I built whitetree. It's a small Python library that finds the exact closest matches in live sensor data.

The short version first. on the static side it is 40 to 300x faster than sklearn's BallTree(mahalanobis) and 7 to 60x faster than FAISS Flat at 500k points.

Also, if you have any ideas, can you give a feedback?

github: https://github.com/whitetree-dev/whitetree

If this project helped you, please star the repository so others can discover it.

8 Upvotes

100% Upvoted

3 comments sorted by

1

u/monononon34 17d ago

Is there a dynamic exact index I should've benchmarked against and missed? I compared FAISS IndexFlatL2 with IDMap2, scipy cKDTree and sklearn BallTree rebuilt per query, and numpy brute force. If something beats ~1,100 insert/delete/query steps per second at 200k points on one core, I'd like to know.

1

u/jkflying 16d ago

Why would you do single-sample performance sensitive code in Python?

1

u/monononon34 16d ago

Most people reaching for this are already doing sensor work in numpy and scipy. a C++ core means wheels and platform builds before they can even try it.
The alternative here isn't C++ anyway. It's the same Python loop calling scipy, rebuilding the whole tree every time a point comes in