Distance Quantization in Computing Distance in High Dimensional Space

• US 20100114871A1
• Filed: 11/02/2009
• Published: 05/06/2010
• Est. Priority Date: 10/31/2008
• Status: Abandoned Application

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Cheong, Hye-Yeon, Ortega, Antonio
• Application Number:
  US12/611,037
• Publication Number:
  US 20100114871A1
• Time in Patent Office: Days
• US Class Current: 707/719
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures

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.

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.

2. The method of claim 1, wherein quantizing the candidate points comprises:

accessing non-uniform intervals based on the query point, each non-uniform interval being described by one or more threshold values and associated with a range of inputs and an output; and

quantizing the candidate points based on non-uniform intervals.

3. The method of claim 2, wherein the query point and the candidate points comprise elements that correspond to respective dimensions, wherein quantizing the candidate points comprises:

using different sets of non-uniform intervals, associated with respective different ones of the dimensions, to quantize the dimensional elements of the candidate points, each set of non-uniform intervals selected based on a respective element of the query point.

4. The method of claim 3, wherein generating metric values based on quantized candidate points comprises:

summing quantized elements of a quantized candidate point to produce a metric value.

5. The method of claim 1, comprising:

determining one or more quantizers that preserve distance ranking between the query point and the candidate points, wherein quantizing the candidate points based on one or more characteristics of the query point comprises using the one or more quantizers.

6. The method of claim 5, wherein quantizing the candidate points based on one or more characteristics of the query point comprises using different quantizers, associated with different dimensions, to quantize elements.

7. The method of claim 5, wherein determining one or more quantizers comprises:

determining a number of quantization levels, one or more quantization threshold values, and mapping values for one or more dimensions.

8. The method of claim 1, comprising:

determining one or more statistical characteristics of multiple, related, query points, wherein the query points comprise elements that correspond to respective dimensions; and

determining one or more quantizers based on the one or more statistical characteristics, each quantizer corresponding to at least one of the dimensions and operable to generate a quantized output based on an input.

9. The method of claim 8, wherein quantizing the candidate points based on one or more characteristics of the query point comprises using the one or more quantizers.

10. The method of claim 8, wherein determining one or more quantizers comprises determining a quantizer that maps successive bins of input values to respective integer values.

11. The method of claim 8, wherein determining one or more quantizers comprises determining threshold values that delineate non-uniform quantization intervals based on an iterative process that minimizes a nearest neighbor search measure.

12. The method of claim 1, comprising:

performing motion estimation based on information comprising the selected one or more candidate points.

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.

14. The method of claim 13, wherein applying non-uniform quantizations comprises quantizing the candidate points based on non-uniform intervals, wherein the non-uniform intervals are described by a set of threshold values that are based on the query point, wherein each one of the quantized candidate points comprises quantized elements corresponding to a plurality of dimensions.

15. The method of claim 14, wherein operating processor electronics to perform operations comprises operating processor electronics to sum quantized elements of a corresponding one of the quantized candidate points to produce a corresponding one of the values.

16. The method of claim 14, wherein the query point comprises elements corresponding to a plurality of dimensions, wherein each one of the candidate points comprises elements corresponding to the plurality of dimensions,

wherein operating processor electronics to perform operations comprises operating processor electronics to generate, for two or more of the dimensions, a partial distance term that is indicative of a distance between corresponding elements of the query point and each one of the candidate points.

17. The method of claim 16, wherein operating processor electronics to perform operations comprises operating processor electronics to quantize the partial distance terms based on the non-uniform intervals.

18. The method of claim 17, wherein operating processor electronics to perform operations comprises operating processor electronics to determine a metric value based on a summation of the quantized partial distance terms associated with the each one of the candidate points.

19. The method of claim 17, wherein the partial distance terms respectively comprise dimension-distance terms, wherein the quantizing reduces a bit-depth of each dimension-distance term.

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.

21. The medium of claim 20, wherein quantizing the candidate points comprises:

accessing non-uniform intervals based on the query point, each non-uniform interval being described by one or more threshold values and associated with a range of inputs and an output; and

quantizing the candidate points based on non-uniform intervals.

22. The medium of claim 21, wherein the query point and the candidate points comprise elements that correspond to respective dimensions, wherein quantizing the candidate points comprises:

using different sets of non-uniform intervals, associated with respective different ones of the dimensions, to quantize the dimensional elements of the candidate points, each set of non-uniform intervals selected based on a respective element of the query point.

23. The medium of claim 22, wherein generating metric values based on quantized candidate points comprises:

summing quantized elements of a quantized candidate point to produce a metric value.

24. The medium of claim 20, wherein the operations comprise:

determining one or more quantizers that preserve distance ranking between the query point and the candidate points, wherein quantizing the candidate points based on one or more characteristics of the query point comprises using the one or more quantizers.

25. The medium of claim 24, wherein quantizing the candidate points based on one or more characteristics of the query point comprises using different quantizers, associated with different dimensions, to quantize elements.

26. The medium of claim 24, wherein determining one or more quantizers comprises:

determining a number of quantization levels, one or more quantization threshold values, and mapping values for one or more dimensions.

27. The medium of claim 20, wherein the operations comprise:

determining one or more statistical characteristics of multiple, related, query points, wherein the query points comprise elements that correspond to respective dimensions; and

determining one or more quantizers based on the one or more statistical characteristics, each quantizer corresponding to at least one of the dimensions and operable to generate a quantized output based on an input.

28. The medium of claim 27, wherein quantizing the candidate points based on one or more characteristics of the query point comprises using the one or more quantizers.

29. The medium of claim 27, wherein determining one or more quantizers comprises determining a quantizer that maps successive bins of input values to respective integer values.

30. The medium of claim 27, wherein determining one or more quantizers comprises determining threshold values that delineate non-uniform quantization intervals based on an iterative process that minimizes a nearest neighbor search measure.

31. The medium of claim 20, wherein the operations comprise:

performing motion estimation based on information comprising the outputted one or more candidate points.

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.

33. The system of claim 32, wherein the processor electronics are configured to access non-uniform intervals based on the query point, each non-uniform interval being described by one or more threshold values and associated with a range of inputs and an output, and quantize the candidate points based on non-uniform intervals.

34. The system of claim 33, wherein the query point and the candidate points comprise elements that correspond to respective dimensions, wherein the processor electronics are configured to use different sets of non-uniform intervals, associated with respective different ones of the dimensions, to quantize the dimensional elements of the candidate points, each set of non-uniform intervals selected based on a respective element of the query point.

35. The system of claim 34, wherein the processor electronics are configured to sum quantized elements of a quantized candidate point to produce a metric value.

36. The system of claim 32, wherein the processor electronics are configured to determine the one or more quantizers to preserve distance ranking between the query point and the candidate points.

37. The system of claim 36, wherein the processor electronics are configured to use different quantizers, associated with different dimensions, to quantize elements.

38. The system of claim 36, wherein determining the one or more quantizers comprises determining a number of quantization levels, one or more quantization threshold values, and mapping values for one or more dimensions.

39. The system of claim 32, wherein the processor electronics are configured to determine one or more statistical characteristics of multiple, related, query points, wherein the query points comprise elements that correspond to respective dimensions and determine one or more quantizers based on the one or more statistical characteristics, each quantizer corresponding to at least one of the dimensions and operable to generate a quantized output based on an input.

40. The system of claim 39, wherein determining the one or more quantizers comprises determining a quantizer that maps successive bins of input values to respective integer values.

41. The system of claim 39, wherein determining the one or more quantizers comprises determining threshold values that delineate non-uniform quantization intervals based on an iterative process that minimizes a nearest neighbor search measure.

42. The system of claim 32, wherein the processor electronics are configured to perform motion estimation based on information comprising the outputted one or more candidate points.