Patent ID: 7769782

Claim:
A method for providing a summary of data from multiple parties while maintaining confidentiality of the data from each party, comprising: receiving N array sketches of data from the multiple parties; constructing a vector sum A of the N array sketches; in a computer, constructing a wavelet representation R of the vector sum A using a B-term wavelet expansion; and providing the wavelet representation R of the vector sum as a summary of the data of multiple parties, while maintaining confidentiality of the data from the multiple parties; wherein the representation R has the following properties: error is at most ∥A−R∥ 2 and less than or equal to (1+ε)∥A−R opt ∥ 2 , where R opt is an optimum representation, and the term ε is a user-defined parameter, processing time is polynomial in B and log N/ε, and working space is polynomial in B and log N/ε.