A k-nearest-neighbour index over points.
Monty asks scipy for this — KDTree(graph.pos) — and then queries it once per
hypothesis to find the stored nodes an unobserved pose would have been seen
from. Comparing against every node instead is the same answer at a cost that
grows with the product of hypotheses and nodes: a pretrained object of two
thousand nodes matched by two thousand hypotheses is four million distance
calculations per graph per step, and that is where most of the port's time
went.
So this is the same structure scipy builds: a binary tree that splits the points along whichever axis they are most spread over, at their median, so a query descends to the region its answer is in and stops looking at regions that cannot beat what it already has. It is our own code rather than a port — scipy's tree is not part of Monty — and is documented as such.
Determinism
Answers are ordered nearest first, and a tie in distance goes to the lower id,
which is what makes two runs of the same episode choose the same nodes. Points
are taken as {point, id} pairs so the caller decides what an id is.
Summary
Functions
Indexes points, each a {point, id} pair.
The reference index: our own tree, in Elixir.
The ids of the count points nearest query, nearest first.
The ids of the count points nearest each of queries, one list per query.
The same answers as nearest_many/3, left as the bytes the index wrote.
The count points nearest query with their distances, nearest first.
The same answer as nearest/3, and how many nodes finding it took.
Points as the bytes an index or a kernel reads: three little-endian f64 each.
Types
Functions
Indexes points, each a {point, id} pair.
The native index when this machine has one, the tree below otherwise. Both
answer the same question; build_elixir/1 is the one that says which.
The reference index: our own tree, in Elixir.
This is what the tests describe — including how many nodes a query looks at — and what runs wherever the native index is not built. A caller asking for it by name wants that answer, not the fastest one.
@spec nearest(t(), point(), pos_integer()) :: [id()]
The ids of the count points nearest query, nearest first.
Fewer than count when the tree holds fewer points.
@spec nearest_many(t(), [point()], pos_integer()) :: [[id()]]
The ids of the count points nearest each of queries, one list per query.
One call for a step's worth of questions, in the order they were asked, and
each answer is exactly what nearest/3 would have said: a caller never has to
interleave the index with its own loop. On the native index this is genuinely
one call — twenty thousand queries cross the boundary once, not twenty
thousand times.
@spec nearest_many_ids(t(), [point()] | binary(), pos_integer()) :: {binary(), pos_integer()} | nil
The same answers as nearest_many/3, left as the bytes the index wrote.
Nothing is decoded, rejected or grouped: the answer is {ids, count} —
queries * count little-endian u32 ids, row after row, with
4_294_967_295 where a query found fewer than count — because the caller is
a native kernel that reads them there. Decoding twenty thousand ids into lists
of lists was a fifth of what the answers cost, and the kernel can skip the
marker itself.
nil for a tree that is not the native index: the Elixir tree has no such
bytes, and a caller that needs them keeps the decoded path.
@spec nearest_with_distances(t(), point(), pos_integer()) :: [{float(), id()}]
The count points nearest query with their distances, nearest first.
scipy answers this from the same call as the ids — return_distance=True —
and the distance is what a caller needs when it wants to compare answers
rather than use them: two objects differ most where one has a part the other
lacks, which shows up as a node far from everything in the other graph.
@spec nearest_with_visits(t(), point(), pos_integer()) :: {[id()], non_neg_integer()}
The same answer as nearest/3, and how many nodes finding it took.
The count is the point of a tree: a query is supposed to descend to the region its answer is in and stop, so the number of nodes it looks at belongs to the logarithm of the tree rather than to the number of points. A test can hold it to that, which is the only way to notice if pruning stops pruning — the answers stay right while the cost goes linear.
Points as the bytes an index or a kernel reads: three little-endian f64 each.
Public so that a caller which asks two native things about the same points encodes them once, and so that both see exactly the same numbers.