#kdtree and ball trees seem cool, but require full knowledge of the thing I'm searching for. What if it's 7 dimensional and I only know 4 of the values?
I feel like a "parallel kd tree" with a separate binary index on each dimension would work better here.
Reduce depth. Allow unspecified values. It'd also be a snap to create and search each dim in parallel.
This must already exist...
@davidr @recursive I don’t have a library to offer you, but I did some exploration around this. In the more general case, you can weight each of your seven dimensions. If you want something, that’s exactly like four of them, but you have a lot of flexibility on the other three, it can represent that.
I kind of feel that’s what Spotify’s rec algo does sometimes. “ here’s a song by the same artist. Now here’s a song made in the same year. Now here’s a song with the same word in the title.”
@brohrer @recursive Yeah, they probably do. Which reminds me, a tree like this would also be easy to add dimensions without recomputing anything else.
My actual application is 3D positions + time, with optional velocities. More specifically, it'd be 2D pos + time all as ranges, a third pos as a disjoint set of very small ranges and optional velocity ranges.
Interesting that nobody named something that does this. Possibly it's just an obvious neighbor of KD trees and regular old DB tables.
dr 🛠️🛰️📡🎧
Brandon Rohrer