System, method and computer-readable medium for providing pattern matching

• US 7,415,464 B1
• Filed: 07/20/2005
• Issued: 08/19/2008
• Est. Priority Date: 08/21/2001
• Status: Expired due to Fees

• 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
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US11/185,091
• Time in Patent Office: 1,126 Days
• Field of Search: 707/1, 707/2, 707/6, 341/87, 382/225, 709/224
• US Class Current: 1/1
• 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 computer-implemented pattern-matching method comprising:

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.

2. The method of claim 1, wherein modifying each of the vectors further comprises reducing each generated vector to a lower dimensional vector.

3. The method of claim 2, further comprising, for each lower dimensional vector, summing distances between the lower dimensional vector and remaining lower dimensional vectors.

4. The method of claim 3, wherein selecting the one of the plurality of generated vectors further comprises selecting the generated vector corresponding to the lower dimensional vector having a lowest summed distance.

5. The method of claim 4, wherein the selected one of the plurality of generated vectors is representative of the data set.

6. The method of claim 1, further comprising:

outputting the selected generated vector as the representative of the data set.

7. The method of claim 6, wherein outputting the selected generated vector further comprises outputing the generated vector to at least one of a graphical display, storage device and transmitter.

8. A computer-readable medium storing instructions for controlling a computing device to perform pattern-matching, the instructions comprising:

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.

9. The computer-readable medium of claim 8, wherein modifying each of the vectors further comprises reducing each generated vector to a lower dimensional vector.

10. The computer-readable medium of claim 9, further comprising, for each lower dimensional vector, summing distances between the lower dimensional vector and remaining lower dimensional vectors.

11. The computer-readable medium of claim 10, wherein selecting the one of the plurality of generated vectors further comprises selecting the generated vector corresponding to the lower dimensional vector having a lowest summed distance.

12. The computer-readable medium of claim 11, wherein the selected one of the plurality of generated vectors is representative of the data set.

13. The computer-readable medium of claim 8, further comprising:

outputting the selected generated vector as the representative of the data set.

14. A system for pattern-matching, the system comprising:

a module configured to generate a plurality of vectors from a data set;

a module configured to modify each of the vectors of the plurality of vectors; and

a module configured to select 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.

15. The system of claim 14, wherein the module configured to modify each of the vectors further reduces each generated vector to a lower dimensional vector.

16. The system of claim 15, further comprising a module configured to sum distances between the lower dimensional vector and remaining lower dimensional vectors for each lower dimensional vector.

17. The system of claim 16, wherein the module configured to select the one of the plurality of generated vectors further selects the generated vector corresponding to the lower dimensional vector having a lowest summed distance.

18. The system of claim 17, wherein the selected one of the plurality of generated vectors is representative of the data set.

19. The system of claim 14, further comprising:

a module configured to output the selected generated vector as the representative of the data set.

20. The system of claim 19, wherein the module configured to output the selected generated vector further outputs the generated vector to at least one of a graphical display, storage device and transmitter.