Rapid nearest neighbor searching using KD-ferns

摘要

A system includes a transceiver, processor, database, and memory. Instructions for executing a nearest neighbor search are recorded in memory. Receipt of a query point by the transceiver from a camera or other input device causes the processor to construct a KD-Fern having nodes as an ordered set of splitting dimensions and thresholds. All nodes at the same level of the KD-Fern have the same splitting dimension d and the same threshold τ. A binary bit is generated at each node describing a respective threshold comparison decision for that particular node. The processor associates each of a plurality of binary addresses in the binary map with a corresponding nearest neighbor index, determines the binary address of the query point, and returns, e.g., to a vehicle braking, steering, or body control module, a nearest neighbor result by extracting the nearest neighbor from the binary map.

主权项

1. A system comprising:
a transceiver; a processor; a database containing a plurality of data points; tangible, non-transitory computer-readable memory on which is recorded instructions for executing a nearest neighbor search; and a controller in communication with the processor; wherein the processor is configured to construct a multi-level KD-Fern having a set of nodes as an ordered set of splitting dimensions and thresholds, wherein all of the nodes at the same level of the KD-Fern have the same splitting dimension d and the same threshold T, and wherein receipt of a query point by the transceiver from an input device causes the processor device, via execution of the instructions by the processor, to: independently generate, for each of the nodes of the KD-Tree, a binary (0 or 1) bit describing a respective threshold comparison decision for that particular node; associate each of a plurality of binary addresses in the binary map with a corresponding nearest neighbor index; determine the binary address of the query point; and return a nearest neighbor result to the controller, via the transceiver, by extracting the corresponding nearest neighbor for the query point from the binary map, and wherein the controller is configured to execute a control action with respect to the system in response to the received nearest neighbor result.