Method of determining a nearest numerical neighbor point in multi-dimensional space
AssigneeHewlett-Packard Development Company, L.P.
InventorsMark E. Boettcher, Nathan D. Mellor
Life of this patent
Estimating the term…
Abstract
A method of determining a near neighbor to a target point in multidimensional space from among a set of candidate points includes generating a matrix of bins and identifying a first bin that contains the target point. The first bin is searched for a first candidate point, and a set of proximate bins selected from the matrix are identified. Each of the proximate bins has at least a portion potentially closer to a first selected point in the first bin than is a second selected point in the first bin.
Claims13
A method of determining a near neighbor to a target point in multidimensional space from among a set of candidate points, comprising:
- generating a matrix of bins;
- identifying a first bin that contains the target point;
- locating a first candidate point in the first bin;
- searching at least a second bin adjacent to the first bin for a second candidate point;
- calculating the distances between each of the first and second candidate points and the target point;
- and
- calculating the distance between the first candidate point and the target point prior to searching the second bin, and including determining which bin to search based on the distance between the first candidate point and the target point.
A method of determining a near neighbor to a target point in multidimensional space from among a set of candidate points, comprising:
- generating a matrix of bins;
- identifying a first bin that contains the target point;
- searching the first bin for a first candidate point;
- identifying a set of proximate bins selected from the matrix, each of the proximate bins having at least a portion potentially closer to a first selected point in the first bin than is a second selected point in the first bin;
- and
- wherein identifying the set of proximate bins includes selecting all bins having a portion separated from any portion of the first bin by a distance less than the distance between two maximally separated points in opposed corners of the first bin.
Dependencies are inferred from the claim text.