System and method adapted to facilitate dimensional transform

• US 7,043,514 B1
• Filed: 03/01/2002
• Issued: 05/09/2006
• Est. Priority Date: 03/01/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Achlioptas, Dimitris
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US10/086,309
• Time in Patent Office: 1,530 Days
• Field of Search: 708/400, 708/401, 707/101
• US Class Current: 708/401
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis

Abstract

Systems and methods that facilitate dimensional transformations of data points are disclosed. In particular, the subject invention provides for a system and methodology that simplifies dimensional transformations while mitigating variations of a distance property between pairs of points. A set of n data points in d dimensional space is represented as an n×d input matrix, where d also corresponds to the number of attributes per data point. A transformed matrix represents the n data points in a lower dimensionality k after being mapped. The transformed matrix is an n×k matrix, where k is the number of attributes per data point and is less than d. The transformed matrix is obtained by multiplying the input matrix by a suitable projection matrix. The projection matrix is generated by randomly populating the entries of the matrix with binary or ternary values according to a probability distribution. Unlike previous methods, the projection matrix is formed without obtaining an independent sample from a Gaussian distribution for each entry in the projection matrix, without applying a linear algebraic technique to generate the projection matrix and without employing arbitrary floating point numbers. Processes and/or algorithms can utilize the reduced transformed matrix instead of the larger input matrix to facilitate computational efficiency and data compression.

Claims

1. A computer hardware system that dimensionally transforms a pointset, comprising the following computer executable components:

a receive matrix component that receives the pointset; and

,

a transformation component that reduces the dimensionality of the pointset via employment of a projection matrix having randomly selected entries from a set comprising +1, 0, and −

1, while maintaining a pairwise distance property of the pointset.

2. The system of claim 1, the pointset including n points in d dimensional Euclidean space that may be represented as an n×

d input matrix with respective points represented as a row (vector) having d attributes (coordinates), the points being transformed into k dimensional space so as to be representable as a n×

k transformed matrix with each point represented as a row (vector) having k attributes (coordinates).

3. The system of claim 2, the projection matrix having randomly selected entries of +1 with probability of 1/2 and −

1 with probability of 1/2.

4. The system of claim 2, the projection matrix having randomly selected entries of +1 with probability of 1/6, 0 with probability of 2/3 and −

1 with probability of 1/6.

5. The system of claim 2, a range of the pairwise distance property being maintained within an acceptable predetermined percentage.

6. The system of claim 2, the k selected to maintain the pairwise distance property.

7. The system of claim 2, the k being logarithmic in n and independent of d.

8. The system of claim 2, the transformed pointset utilized by an algorithm to compute a distance between a first point and a second point, the first point and the second point belonging to the pointset.

9. The system of claim 1, the transformation component embedding the pointset in different dimensionalities according to the following:

P is an arbitrary set of n points in d dimensional Euclidian space (^d) represented as a n×

d matrix A, given ε

,β

>

0, where ε

controls accuracy of the embeddings in terms of distance preservation and β

controls probability of success $k_0=\frac{4+2<br><br>\mathrm{\beta <br><br>}}{{\mathrm{\varepsilon <br><br>}}^2/2-{\mathrm{\varepsilon <br><br>}}^3/3}<br><br>\log <br><br><br><br>n$

where, for k≧

k₀, R is a d×

k projection matrix with R(i,j)=r_ij, where {r_ij} includes independent random variables from either one of probability distributions $\begin{array}{c}{r}_{\mathrm{ij}}=\{\begin{array}{c}+1\\ -1\end{array}<br><br>\mathrm{with}<br><br><br><br>\mathrm{probability}<br><br>\begin{array}{c}1/2\\ 1/2\end{array}\\ r_{\mathrm{ij}}=\sqrt{3\times <br><br>}<br><br>\{\begin{array}{ccc}+1& & 1/6\\ 0& \mathrm{with}<br><br><br><br>\mathrm{probability}& 2/3\\ -1& & 1/6\end{array}\end{array}$

where $T=\frac{1}{\sqrt{k}}<br><br>\mathrm{AR}$

and

embedding from d dimensionality to k dimensionality (ƒ

;

^d→

^k) maps an i^th row of A to an i^th row of T

with probability at least 1−

n<sup>−

β</sup>

, for all u,v ε

P $\left(1-\mathrm{\varepsilon <br><br>}\right)<br><br><br><br>{<br><br>u-v<br><br>}^2\le <br><br>{<br><br>f<br><br><br><br>\left(u\right)-f<br><br><br><br>\left(v\right)<br><br>}^2\le <br><br>\left(1+\mathrm{\varepsilon <br><br>}\right)<br><br><br><br>{<br><br>u-v<br><br>}^2.$

10. A computer readable medium having computer usable components for a transformation component comprising:

a receive matrix component that receives a high dimensional point set; and

,

a transformation component that reduces dimensionality of the pointset via employment of a projection matrix having entries of at least one of +1, 0, −

1, while maintaining integrity of a pairwise distance property.

11. A system that dimensionally transforms a pointset, comprising:

a projection matrix generator that receives an input matrix and generates a projection matrix based thereon, the projection matrix having entries of a set of possible values of at least one of +1, 0 and −

1; and

a transformation engine that reduces dimensionality of the pointset via employment of the projection matrix while maintaining a pairwise distance property.

12. The system of claim 11, the set of possible values comprising +1, 0 and −

1.

13. The system of claim 11, the set of possible values comprising +1 and −

1.

14. The system of claim 11, further comprising a receive matrix component that receives a high dimensional pointset and converts the high dimensional pointset into the input matrix.

15. The system of claim 11 further comprising:

a random generator that randomly provides entries for the projection matrix to the projection matrix generator as entries for the projection matrix according to a probability distribution; and

a probability distribution that provides the probability distribution to the random generator.

16. The system of claim 15, the probability distribution providing equal probabilities of 1/2 to entries of +1 and −

1.

17. The system of claim 15, the probability distribution providing probabilities of 1/6, 2/3, and 1/6 to entries of +1, 0 and −

1, respectively.

18. The system of claim 11, the transformation engine outputting the reduced dimensionality pointset and the preserved pairwise distance property to a requesting algorithm.

19. The system of claim 18, the requesting algorithm being at least one of an ε

-approximate nearest neighbor problem, where given an arbitrary point x, for every point $z\in <br><br>P,<br><br>x-z<br><br>\ge <br><br>\left(1-\mathrm{\varepsilon <br><br>}\right)<br><br><br><br>x-y<br><br>,$

a point y ε

P is found, an approximation algorithm for a version of clustering where the sum of the squares of intra cluster distances is sought to be minimized, and data-stream computations, where a limited memory exists and only single pass over the data (stream) is facilitated.

20. A data compression method for transforming n points in d dimensionality, represented as an n×

d input matrix, to k dimensionality thereby producing a n×

k transformed matrix while mitigating variations in a distance property between pairs of the points, comprising the following computer executable acts;

multiplying the n×

d input matrix by a d×

k projection matrix having entries populated from a set of {+1, 0, −

1};

for respective entries in the transformed matrix, discarding calculations wherein multiplication would be by 0;

for respective entries in the transformed matrix, producing a first sum wherein multiplication would be by +1;

for respective entries in the transformed matrix, producing a second sum wherein multiplication would be by −

1; and

subtracting respective first and second sums to obtain each entry in the transformed matrix.

21. The method of claim 20, the entries within the projection matrix being randomly populated with values of +1 and −

1 according to equal probabilities of 1/2.

22. The method of claim 20, the entries within the projection matrix being randomly populated with values of +1, 0 and −

1 according to respective probabilities of 1/6, 2/3, and 1/6.

23. A computer executable hardware system for transforming n points in d dimensionality, represented as an n×

d input matrix, to k dimensionality thereby producing a n×

k transformed matrix while mitigating variations in a distance property between pairs of the points, comprising;

computer implemented means for multiplying the n×

d input matrix by a d×

k projection matrix having entries populated with at least one of +1, 0, or −

1;

computer implemented means for discarding calculations wherein multiplication would be by 0 for each entry in the transformed matrix;

computer implemented means for producing a first sum wherein multiplication would be by +1 for each entry in the transformed matrix;

computer implemented means for producing a second sum wherein multiplication would be by −

1 for each entry in the transformed matrix; and

computer implemented means for subtracting respective first and second sums to obtain each entry in the transformed matrix.