Identifying a sketching matrix used by a linear sketch

• US 9,262,485 B2
• Filed: 08/13/2013
• Issued: 02/16/2016
• Est. Priority Date: 08/13/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hardt, Moritz, Woodruff, David P.
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US13/965,253
• Publication Number:
  US 20150052172A1
• Time in Patent Office: 917 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/2468 Fuzzy queries

Abstract

Embodiments relate to identifying a sketching matrix used by a linear sketch. Aspects include receiving an initial output of the linear sketch, generating a query vector and inputting the query vector into the linear sketch. Aspects further include receiving an revised output of the linear sketch based on inputting the query vector and iteratively repeating the steps of generating the query vector, inputting the query vector into the linear sketch, and receiving an revised output of the linear sketch based on inputting the query vector until the sketching matrix used by the linear sketch can be identified.

Claims

1. A computer implemented method for identifying a sketching matrix used by a linear sketch comprising:

receiving, by a processor, an initial output of the linear sketch;

generating, by the processor, a query vector;

inputting, by the processor, the query vector into the linear sketch;

receiving, by the processor, an revised output of the linear sketch based on inputting the query vector;

iteratively repeating the steps of generating the query vector, inputting the query vector into the linear sketch, and receiving an revised output of the linear sketch based on inputting the query vector until the sketching matrix used by the linear sketch can be identified.

2. The method of claim 1, wherein inputting the query vector into the linear sketch is based on the revised output of the linear sketch received during a prior iteration.

3. The method of claim 1, wherein the sketching matrix has a form of r×

n, where r<

<

n.

4. The method of claim 3, wherein the number of iterations required until the sketching matrix used by a linear sketch can be identified is a function of n that can be represented as first degree polynomial.

5. The method of claim 1, wherein the query vector is selected from a query distribution that is a Gaussian distribution having a varying covariance structure.

6. The method of claim 5, wherein an amount of Gaussian noise is added to the query distribution to reduce an approximation error.

7. The method of claim 1, wherein the query vector is selected from a multivariate normal distribution N(0,τ

I_n), where τ

I_n is a covariance matrix, which is a scalar τ

times the identity matrix I_n.

8. A computer program product for identifying a sketching matrix used by a linear sketch, the computer program product comprising:

a non-transitory computer readable storage medium having program code embodied therewith, the program code executable by a processor to;

receiving an initial output of the linear sketch;

generating a query vector;

inputting the query vector into the linear sketch;

receiving an revised output of the linear sketch based on inputting the query vector;

iteratively repeating the steps of generating the query vector, inputting the query vector into the linear sketch, and receiving an revised output of the linear sketch based on inputting the query vector until the sketching matrix used by the linear sketch can be identified.

9. The computer program product of claim 8, wherein inputting the query vector into the linear sketch is based on the revised output of the linear sketch received during a prior iteration.

10. The computer program product of claim 8, wherein the sketching matrix has a form of r×

n, where r<

<

n.

11. The computer program product of claim 10, wherein the number of iterations required until the sketching matrix used by a linear sketch can be identified is a function of n that can be represented as first degree polynomial.

12. The computer program product of claim 8, wherein the query vector is selected from a query distribution that is a Gaussian distribution having a varying covariance structure.

13. The computer program product of claim 12, wherein an amount of Gaussian noise is added to the query distribution to reduce an approximation error.

14. The computer program product of claim 8, wherein the query vector is selected from a multivariate normal distribution N(0, τ

I_n), where τ

I_n is a covariance matrix, which is a scalar τ

times the identity matrix I_n.

15. A computing system for identifying a sketching matrix used by a linear sketch system, the system comprising a processor configured to:

receive an initial output of the linear sketch;

generate a query vector;

input the query vector into the linear sketch;

receive an revised output of the linear sketch based on inputting the query vector;

iteratively repeat the steps of generating the query vector, inputting the query vector into the linear sketch, and receiving an revised output of the linear sketch based on inputting the query vector until the sketching matrix used by the linear sketch can be identified.

16. The computing system of claim 15, wherein inputting the query vector into the linear sketch is based on the revised output of the linear sketch received during a prior iteration.

17. The computing system of claim 15, wherein the sketching matrix has a form of r×

n, where r<

<

n.

18. The computing system of claim 17, wherein the number of iterations required until the sketching matrix used by a linear sketch can be identified is a function of n that can be represented as first degree polynomial.

19. The computing system of claim 15, wherein the query vector is selected from a query distribution that is a Gaussian distribution having a varying covariance structure.

20. The computing system of claim 19, wherein an amount of Gaussian noise is added to the query distribution to reduce an approximation error.