Scalable system and method for weighted similarity estimation in massive datasets revealed in a streaming fashion
View Patent ↗A method is used to data mine input vectors. A data source receives input vectors. A sketch feature generator converts the input vectors into corresponding sketch feature vectors, where each sketch feature vectors has a number of dimensions that is less than a number of dimensions of the corresponding input vector. A similarity comparator compares each sketch feature vectors against a set of parameters. A decision loop determines results of similarities based upon comparison of each sketch feature vectors against the set of parameters.
1. A method for data mining, comprising:
receiving, by a data source, a plurality of input vectors;
converting, by a sketch feature generator, the plurality of input vectors into a corresponding plurality of sketch feature vectors, wherein each of the plurality of sketch feature vectors has a number of output dimensions that is less than a number of dimensions of a corresponding one of the input vectors;
comparing, by a similarity comparator, each of the plurality of sketch feature vectors against a set of parameters; and
generating, by a decision loop, results of similarities based upon a comparison of each of the plurality of sketch feature vectors against the set of parameters,
wherein an estimate of cosine similarity or Pearson correlation of the input vectors is obtained based on estimates of an inner product of two of the input vectors and a 2-norm vector of one of the input vectors, the estimates being obtained using respective hash tables for each of the input vectors having a number of entries up to the number of output dimensions of the sketch feature vectors, and
wherein the estimate of cosine similarity or Pearson correlation is used to make a recommendation to a user in a recommender system.
2. The method according to claim 1 , wherein the converting by the sketch feature generator further converts the plurality of input vectors into a corresponding plurality of normal vectors.
3. The method according to claim 2 , wherein the corresponding plurality of normal vectors include a plurality of 2-norm vectors.
4. The method according to claim 1 , wherein the plurality of input vectors is received by the data source as a stream of the input vectors in real time.
5. The method according to claim 4 , wherein the sketch feature generator converts the stream of the input vectors into the corresponding plurality of sketch feature vectors in an order corresponding to an order of the stream of the input vectors.
6. The method according to claim 5 , further comprising storing, by a memory, the corresponding plurality of sketch feature vectors that are converted by the sketch feature generator from the plurality of input vectors.
7. The method according to claim 6 , wherein the memory further stores a corresponding plurality of normal vectors that are converted by the sketch feature generator from the plurality of input vectors.
8. The method according to claim 7 , wherein the corresponding plurality of normal vectors include a plurality of 2-norm vectors.
9. The method according to claim 1 , wherein, fora new entry update for one of the input vectors, a hashing function is used to determine which one of the entries of the hash table is used to reflect a value of the new entry update.
10. A system for data mining, comprising:
a data source configured to receive a plurality of input vectors;
a sketch feature generator configured to convert the plurality of input vectors into a corresponding plurality of sketch feature vectors, wherein each of the plurality of sketch feature vectors has a number of output dimensions that is less than a number of dimensions of a corresponding one of the input vectors;
a similarity comparator configured to compare each of the plurality of sketch feature vectors against a set of parameters; and
a decision loop configured to generate results of similarities based upon a comparison of each of the plurality of sketch feature vectors against the set of parameters,
wherein an estimate of cosine similarity or Pearson correlation of the input vectors is obtained based on estimates of an inner product of two of the input vectors and a 2-norm vector of one of the input vectors, the estimates being obtained using respective hash tables for each of the input vectors having a number of entries up to the number of output dimensions of the sketch feature vectors, and
wherein the estimate of cosine similarity or Pearson correlation is used to make a recommendation to a user in a recommender system.
11. The system according to claim 10 , wherein the sketch feature generator is configured to convert the plurality of input vectors into a corresponding plurality of normal vectors.
12. The system according to claim 11 , wherein the corresponding plurality of normal vectors include a plurality of 2-norm vectors.
13. The system according to claim 10 , wherein the data source is configured to receive the plurality of input vectors as a stream of the input vectors in real time.
14. The system according to claim 13 , wherein the sketch feature generator converts the stream of the input vectors into the corresponding plurality of sketch feature vectors in an order corresponding to an order of the stream of the input vectors.
15. The system according to claim 14 , further comprising a memory configured to store the corresponding plurality of sketch feature vectors that are converted by the sketch feature generator from the plurality of input vectors.
16. The system according to claim 15 , wherein the memory is configured to store a corresponding plurality of normal vectors that are converted by the sketch feature generator from the plurality of input vectors.