Distance Quantization in Computing Distance in High Dimensional Space
First Claim
Patent Images
1. A method performed by data processing apparatus, comprising:
- quantizing a set of candidate points based on one or more characteristics of a query point;
generating metric values based on the quantized candidate points, respectively, the metric values being indicative of respective proximities between the query point and the candidate points; and
selecting one or more of the candidate points in response to the query point based on the metric values.
2 Assignments
0 Petitions
Accused Products
Abstract
Techniques and systems for quantization based nearest neighbor searches can include quantizing a set of candidate points based on one or more characteristics of a query point; generating metric values based on the quantized candidate points, respectively, the metric values being indicative of respective proximities between the query point and the candidate points; and selecting one or more of the candidate points in response to the query point based on the metric values. In some implementations, techniques and systems can compress search metric computation resolution by implementing non-uniform scalar quantization within a metric computation process.
21 Citations
42 Claims
-
1. A method performed by data processing apparatus, comprising:
-
quantizing a set of candidate points based on one or more characteristics of a query point; generating metric values based on the quantized candidate points, respectively, the metric values being indicative of respective proximities between the query point and the candidate points; and selecting one or more of the candidate points in response to the query point based on the metric values. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A method performed by data processing apparatus, comprising:
-
accessing a set of candidate points from a memory; and operating processor electronics to perform operations based on the set of candidate points with respect to a query point to produce values being indicative of respective proximities between the query point and the candidate points, and use the values to determine a nearest neighbor point from the set of candidate points, wherein the computations include applying non-uniform quantizations based on one or more characteristics of the query point. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
20. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:
-
quantizing a set of candidate points based on one or more characteristics of a query point; generating metric values based on the quantized candidate points, respectively, the metric values being indicative of respective proximities between the query point and the candidate points; and selecting one or more of the candidate points in response to the query point based on the metric values. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
-
-
32. A system, comprising:
-
a memory configured to store data points, wherein the data points comprise elements that correspond to respective dimensions; and processor electronics configured to access a query point, use one or more of the data points as candidate points, use one or more quantizers to quantize the candidate points based on one or more characteristics of the query point, generate metric values based on the quantized candidate points, respectively, the metric values being indicative of respective proximities between the query point and the candidate points, select one or more of the candidate points, based on the metric values, as an output to the query point. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
-
Specification