System and method adapted to facilitate dimensional transform

Details System and method adapted to facilitate dimensional transform System and method adapted to facilitate dimensional transform

2005-10-24

2010-11-16

Ngo, Chuong D (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

07836115

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.

REFERENCES:
patent: 5647058 (1997-07-01), Agrawal et al.
patent: 5832044 (1998-11-01), Sousa et al.
patent: 6032146 (2000-02-01), Chadha et al.
patent: 6122628 (2000-09-01), Castelli et al.
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6134555 (2000-10-01), Chadha et al.
patent: 6360019 (2002-03-01), Chaddha
patent: 6505207 (2003-01-01), Aggarwal et al.
patent: 6987959 (2006-01-01), Correia et al.
patent: 7318078 (2008-01-01), Achlioptas
Dimitris Achlioptas, Database-Friendly Random Projections, Journal of Computer and Syststems Science, Jun. 2003, 671-687, vol. 66 Issue 4.
Wolfram Research, Euclidean Space, http://mathworld.wolfram.com/EuclideanSpace.html, last viewed on May 11, 2005.
Johnson, et al., “Extensions of Lipschitz mappings into a Hilbert space,” Contemporary Mathematics, 1984, pp. 189-206, vol. 26.
P. Frankl, et al., “The Johnson-Lindenstrauss Lemma and Sphericity of Some Graphs,” Journal of Combinatorial Theory, 1988, pp. 355-362, Series B 44.
Sanjeev Arora, et al:, “Learning Mixtures of Arbitrary Gaussians,” 2001, pp. 247-257.
Sanjoy Dasgupta, “Learning Mixtures of Gaussians,” 1999.
Sanjoy Dasgupta, et al., “An elementary proof of the Johnson-Lindenstrauss Lemma,” Mar. 1999, pp. 1-5.
Piotr Indyk, “Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation,” 2000, pp. 1-9.
Piotr Indyk, et al., “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,” 1998, pp. 604-613.
Jon M. Kleinberg, “Two Algorithms for Nearest-Neighbor Search in High Dimensions,” 1997, pp. 599-608.
Nathan Linial, et al., “The geometry of graphs and some of its algorithmic applications,” 1995, pp. 1-26.
Christos H. Papadimitriou, et al., “Latent Semantic Indexing: A Probabilistic Analysis,” Nov. 14, 1997, pp. 1-15.
Leonard J. Schulman, “Clustering for edge-Cost Minimization,” 2000, pp. 1-31.
Santosh Vempala, “A Random Sampling based Algorithm for Learning the Intersection of Half-spaces,” 1997.
Alan Frieze, et al., “Fast Monte-Carlo Algorithms for finding low-rank approximations,” Oct. 22, 1998.
Samuel Kaski, “Dimensionality Reduction by Random Mapping: Fast Similarity Computation for Clustering,” May 4, 1998, pp. 413-418.

Affiliated with

Also associated with

Rating

System and method adapted to facilitate dimensional transform does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System and method adapted to facilitate dimensional transform, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method adapted to facilitate dimensional transform will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4244122