Patent Document ID: 8499003
Application ID: 13563864
Patent Status: 1

Claim One:
1. A method for determining a distance between at least two vectors of n coordinates, the method comprising: identifying a set of heavy coordinates from a set of n coordinates associated with at least two vectors as a set of heavy coordinates, wherein a heavy coordinate is represented as |x i |≧ε 2 ∥x∥ 1 , where x is a vector, i is a coordinate in the set of n coordinates, and ε is an arbitrary number; identifying a set of light coordinates from the set of n coordinates associated with the at least two vectors, as a set of light coordinates, wherein a light coordinate is represented as |x i |<ε 2 ∥x∥ 1 ; determining a first estimation of a contribution from the set of heavy coordinates to a rectilinear distance between the at least two vectors; wherein determining the first estimation comprises multiplying each of a set of stream updates by a subset of a set of constructed hash functions, wherein the subset is defined based on ε 2 ; determining a second estimation of a contribution from the set of light coordinates to the rectilinear distance, wherein determining the second estimation comprises multiplying each of a set of stream updates by a subset of the set of constructed hash functions, wherein the subset is defined based on ε 2 , and wherein the second estimation is determined separate from the first estimation; and combining the first estimation with the second estimation.