SYSTEM, METHOD AND COMPUTER-READABLE MEDIUM FOR PROVIDING PATTERN MATCHING

• US 20080275908A1
• Filed: 07/11/2008
• Published: 11/06/2008
• Est. Priority Date: 08/21/2001
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Muthukrishnan, Shanmugavelayutham, Indyk, Piotr, Koudas, Nikolaos
• Granted Patent: US 7,627,602 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system, method and computer-readable medium are disclosed for identifying representative data using sketches. The method embodiment comprises generating a plurality of vectors from a data set, modifying each of the vectors of the plurality of vectors and selecting one of the plurality of generated vectors according to a comparison of a summed distance between a modified vector associated with the selected generated vector and remaining modified vectors. Modifying the generated vectors may involve reduced each generated vector to a lower dimensional vector. The summed distance then represents a summed distance between the lower dimensional vector and remaining lower dimensional vectors.

Claims

1. A method of generating a lower dimensional vector that represents a higher dimensional vector, the method comprising:

choosing a dimension associated with the lower dimensional vector;

generating a subvector from the higher dimensional vector;

generating a random vector; and

calculating the lower dimensional vector based on the subvector and the random vector.

2. The method of claim 1, further comprising:

normalizing the random vector.

3. The method of claim 1, wherein calculating the lower dimensional vector further comprises calculating the dot product between the subvector and the random vector.

4. The method of claim 1, wherein calculating the lower dimensional vector further comprises projecting the subvector onto the random vector.

5. The method of claim 1, wherein calculating the lower dimensional vector further comprises using a polynomial convolution between the subvector and the random vector.

6. The method of claim 1, wherein the subvector is generated by partitioning data in the higher dimensional vector.

7. The method of claim 1, wherein the random vector has the same dimension as the subvector.

8. A tangible computer-readable medium storing instructions for controlling a computing device to generate a lower dimensional vector that represents a higher dimensional vector, the instructions comprising:

choosing a dimension associated with the lower dimensional vector;

generating a subvector from the higher dimensional vector;

generating a random vector; and

calculating the lower dimensional vector based on the subvector and the random vector.

9. The computer-readable medium of claim 8, the instructions further comprising:

normalizing the random vector.

10. The computer-readable medium of claim 8, wherein calculating the lower dimensional vector further comprises calculating the dot product between the subvector and the random vector.

11. The computer-readable medium of claim 8, wherein calculating the lower dimensional vector further comprises projecting the subvector onto the random vector.

12. The computer-readable medium of claim 8, wherein calculating the lower dimensional vector further comprises using a polynomial convolution between the subvector and the random vector.

13. The computer-readable medium of claim 8, wherein the subvector is generated by partitioning data in the higher dimensional vector.

14. The computer-readable medium of claim 8, wherein the random vector has the same dimension as the subvector.

15. A system for generating a lower dimensional vector that represents a higher dimensional vector, the system comprising:

a module configured to choose a dimension associated with the lower dimensional vector;

a module configured to generate a subvector from the higher dimensional vector;

a module configured to generate a random vector; and

a module configured to calculate the lower dimensional vector based on the subvector and the random vector.

16. The system of claim 15, wherein the random vector has the same dimension as the subvector.

17. The system of claim 15, further comprising:

a module configured to normalize the random vector.

18. The system of claim 15, wherein the module configured to calculate the lower dimensional vector further calculates the dot product between the subvector and the random vector.

19. The system of claim 15, wherein the module configured to calculate the lower dimensional vector further projects the subvector onto the random vector.

20. The system of claim 15, wherein the module configured to calculate the lower dimensional vector further uses a polynomial convolution between the subvector and the random vector.

21. The system of claim 15, wherein the module configured to generate the subvector further partitions data in the higher dimensional vector.

22. The system of claim 15, wherein the random vector has the same dimension as the subvector.