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.
2. The system of claim 1 , wherein the system is configured to construct a plurality of the KD-ferns, randomly select a splitting dimension from among a fixed number of dimensions with a maximal variance, and return an approximate nearest neighbor result as the nearest neighbor result.
3. The system of claim 1 , wherein the binary map includes a plurality of binary strings each of length L recorded in a lookup table having 2L entries, and wherein the binary map is accessed just one time during execution of the nearest neighbor search in order to determine the nearest neighbor result for the query point.
4. The system of claim 1 , wherein the input device is a camera operable to output a digital image, and wherein the processor is configured to receive, as the query point, a point in the digital image.
5. The system of claim 1 , wherein the controller is a vehicle controller, and wherein the transceiver is configured to return the nearest neighbor result to the vehicle controller as an output signal.
6. The system of claim 5 , wherein the vehicle controller is a braking or a steering controller operable to output a braking or steering torque, respectively, in response to the nearest neighbor result.
7. The system of claim 6 , wherein the nearest neighbor result identifies a driver from among a population of drivers, and wherein the vehicle controller is body control module configured to automatically adjust a setting of one of a vehicle system in response to the nearest neighbor result to thereby match a preference of the identified driver.
8. A method comprising:
constructing a multi-level KD-Fern via a processor using data points stored in a database, wherein the KD-Fern has a set of nodes as an ordered set of splitting dimensions d and thresholds T, and wherein all of the nodes at the same level of the KD-Fern have the same splitting dimension d and the same threshold T;
receiving a query data point, via a transceiver, from an input device;
independently generating, for each of the nodes of the constructed KD-Tree, a binary (0 or 1) bit describing a respective threshold comparison decision for that particular node;
associating each of a plurality of binary addresses in the binary map with a corresponding nearest neighbor index;
determining the binary address of the query point; and
returning a nearest neighbor result to an external device, via the transceiver, by extracting the corresponding nearest neighbor for the query point from the binary map; and
executing a control action with respect to a system, via a controller, in response to the received nearest neighbor result.
9. The method of claim 8 , wherein constructing a multi-level KD-Fern includes constructing a plurality of the KD-ferns and randomly select a splitting dimension from among a fixed number of dimensions with a maximal variance, and wherein returning a nearest neighbor result includes returning an approximate nearest neighbor result as the nearest neighbor result.
10. The method of claim 8 , further comprising: recording, as part of the binary map, a plurality of binary strings each of length L in a lookup table having 2L entries, and accessing the binary map just one time during the nearest neighbor search in order to determine the nearest neighbor result for the query point.
11. The method of claim 8 , wherein the input device is a camera, and wherein receiving the query point includes receiving a point in a digital image from the camera.
12. The method of claim 8 , wherein the controller is a vehicle controller, and wherein returning the nearest neighbor result includes transmitting the nearest neighbor result to the vehicle controller.
13. The method of claim 12 , wherein the vehicle controller is a brake or steering controller, the method further comprising: outputting a braking or a steering torque via the respective brake or steering controller.
14. The method of claim 12 , wherein the vehicle controller is body control module, the method further comprising identifying a driver from a population of drivers, and then adjusting a setting of a vehicle system via the body control module in response to the NN result to thereby match a preference of the identified driver.
15. A vehicle comprising:
a controller;
a digital camera; and
a system comprising:
a transceiver;
a processor;
a database containing a plurality of data points, wherein the processor is configured to construct, using the plurality of data points in the database, a multi-level KD-Fern having a set of nodes as an ordered set of splitting dimensions d and
thresholds T, with all of the nodes at the same level of the KD-Fern have the same splitting dimension d and the same threshold T; and
tangible, non-transitory computer-readable memory on which is recorded instructions for executing a nearest neighbor (NN) search;
wherein receipt of a query point by the transceiver from the digital camera causes execution of the instructions by the processor, and thereby causes the computer device 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 a property of the vehicle in response to the returned nearest neighbor result.
16. The vehicle of claim 15 , wherein the controller is one of a braking controller and the property of the vehicle is a braking force applied by a set of brake actuators and a steering controller and the property of the vehicle is a steering force applied by a steering motor.
17. The vehicle of claim 15 , wherein the controller is a body control module, and the property of the vehicle is an HVAC or driving position setting.
18. The vehicle of claim 15 , wherein the binary map includes a plurality of binary strings each of length L and recorded in a lookup table having 2L entries,
and wherein the processor accesses the binary map just one time during the nearest neighbor search in order to determine the nearest neighbor result for the query point.
19. The vehicle of claim 15 , wherein the system is configured to construct a plurality of the KD-ferns, randomly select a splitting dimension from among a fixed number of dimensions with a maximal variance, and return an approximate nearest neighbor result as the nearest neighbor result.