Hacker News new | comments | show | ask | jobs | submit login
The Bkd Tree: A Dynamic Disk Optimized BSP Tree (medium.com)
63 points by NickGerleman on Dec 25, 2015 | hide | past | web | favorite | 2 comments

I wonder how it performs compared to a VP tree. Yes, the VP tree has all the problems of the KD tree, i.e. it becomes unbalanced when inserting, but most fast implementations use linear search in leaf nodes instead of creating a full tree, and splitting a leaf once it exceeds its max size (which is normally around 100-1000) usually gives a pretty good vantage point. I guess the same can be done on a KD tree. In my experiments, the VP tree was the fastest tree for range queries when you can't establish a total order over your data.

VP trees are interesting (previously discussed here: https://news.ycombinator.com/item?id=3304685), and there is also the MVP variant (multi vantage point trees -- https://en.wikipedia.org/wiki/MVP_tree):

Indexing Large Metric Spaces For Similarity Search Queries http://citeseerx.ist.psu.edu/viewdoc/download?doi=

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact