Privacy preserving method for querying a remote public service

• US 8,666,992 B2
• Filed: 06/15/2012
• Issued: 03/04/2014
• Est. Priority Date: 06/15/2012
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Perronnin, Florent, Devin, Vincent, Serrano, Jose Antonio Rodriguez
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): Pham, Tuan A
• Application Number:
  US13/524,469
• Publication Number:
  US 20130339386A1
• Time in Patent Office: 627 Days
• Field of Search: None
• US Class Current: 707/748
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 21/6263 during internet communication, e.g. revealing personal data from cookies

Abstract

A system and a method of querying a remote service without revealing a private document to the remote service are provided. The method includes receiving a signature of a user'"'"'s private document, and querying an intermediate database with the signature of the private document to generate an intermediate result set comprising intermediate database documents, based on a computation of similarity of the signatures of the intermediate database documents to the signature of the private document. The remote service is queried, based on the intermediate result set and a final result set is received from the remote service based on the query, which can be output to the user or further processed.

Claims

1. A method of querying a remote service without revealing a private document to the remote service, comprising:

at a main computer, receiving from a client a signature generated from a user'"'"'s private document, without receiving the document;

querying an intermediate database with the signature of the private document to generate an intermediate result set comprising intermediate database documents, based on a computation of similarity of the signatures of the intermediate database documents to the signature of the private document;

computing a relevance factor for each document of the intermediate result set;

computing a reconstruction error based on the relevance factors of all the documents in the intermediate result set and determining a confidence in the intermediate result set based on the reconstruction error;

querying the remote service with a query which is based on the intermediate result set, whereby the user'"'"'s private document and the signature of the private document are not revealed to the remote service;

receiving a final result set from the remote service based on the query; and

weighting the final result set based on the relevance factors.

2. The method of claim 1, wherein the private document comprises at least one of an image, a sound recording, and text.

3. The method of claim 1, wherein each signature is a statistical representation of features extracted from the respective document.

4. The method of claim 3, wherein the documents comprise images and the features are extracted from patches of an image of the respective document.

5. The method of claim 3, wherein each signature comprises a Fisher vector.

6. The method of claim 1, wherein the remote service provides a similar document search and the final result set comprises a set of documents retrieved from a public database, based on their similarity to the documents in intermediate result set.

7. The method of claim 1, wherein the remote service provides a category of document search and the final result set comprises category labels for the documents in intermediate result set.

8. The method of claim 1, further comprising warning a user when a confidence in the intermediate result set is not above a threshold confidence.

9. The method of claim 1, wherein the computation of the relevance factors is based on coefficients that minimize the reconstruction error between the signatures of the documents of the intermediate result set and the signature of the private document.

10. The method of claim 1, further comprising the client computing the private document signature.

11. The method of claim 1, wherein the final result set comprises a set of documents.

12. The method of claim 1, further comprising, caching a result set for each document in the intermediate database by submitting the respective intermediate database document to the remote service and wherein querying the remote service based on the intermediate result set comprises retrieving the cached result set for each document in the intermediate result set and generating the final result set based on the retrieved cached result sets.

13. The method of claim 1, wherein the querying of the remote service based on the intermediate result set comprises generating a query with each document in the intermediate result set and submitting the queries to the remote service.

14. The method of claim 1, wherein the querying of the intermediate database with the signature is performed with a computer processor.

15. A computer program product comprising a non-transitory recording medium which stores instructions, which when executed by a computer, perform the method of claim 1.

16. A system comprising memory which stores instructions for performing the method of claim 1, and a processor in communication with the memory, for executing the instructions.

17. A computer implemented querying system comprising:

a signature generator, located on a client, for generating a signature for a user'"'"'s private document;

a similarity service, located on a server, which receives the generated signature of the private document, without receiving the private document, and queries an intermediate database with the generated signature to produce an intermediate result set comprising documents, the similarity service computing a relevance factor for each document of the intermediate result set, a reconstruction error based on the relevance factors of the documents in the intermediate result set, and a confidence in the intermediate result set based on the reconstruction error;

a submitting component which submits the intermediate result set to an associated remote service for producing a final result set based on the intermediate result set, the submitting component weighting the final result set based on the relevance factors; and

at least one processor which implements the signature generator and similarity service.

18. The system of claim 17, wherein the final result set comprises a set of documents retrieved from a public database, based on the documents in the intermediate result set.

19. A method of querying a remote service for results similar to results which would be produced by querying the remote service with a private document without revealing the private document to the remote service comprising:

querying a similarity service with the private document, the similarity service querying an intermediate database with a signature generated from the private document which is compared to signatures of documents stored in the intermediate database to produce an intermediate result set comprising documents, the intermediate result set being ranked by the similarity of the signature of each document of the intermediate result set to the signature of the private document;

receiving the ranked intermediate result set from the similarity service;

computing a relevance factor for each document of the intermediate result set;

computing a reconstruction error based on the relevance factors of all the documents in the intermediate result set and a confidence in the intermediate result set based on the reconstruction error;

querying the remote service with a query set derived from the intermediate result set;

receiving a final result set of documents; and

outputting the final result set of documents, the final result set being weighted based on the relevance factors.

20. The method of claim 19, wherein the documents of the final result set are ordered based on the rankings of the intermediate result set.

21. The method of claim 20, wherein the computation of similarity of signatures is performed on the same computing device as computation of the private document signature.