Synopsis of a search log that respects user privacy

• US 8,601,024 B2
• Filed: 06/16/2009
• Issued: 12/03/2013
• Est. Priority Date: 06/16/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kenthapadi, Krishnaram, Korolova, Aleksandra, Mishra, Nina, Ntoulas, Alexandros
• Primary Examiner(s): HASAN, SYED HAROON
• Application Number:
  US12/485,058
• Publication Number:
  US 20100318546A1
• Time in Patent Office: 1,631 Days
• Field of Search: None
• US Class Current: 707/776
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Described is releasing output data representing a search log, in which the data is suitable for most data mining/analysis applications, but is safe to publish by preserving user privacy. The search log is processed such that a query is only included if a sufficient count of that query is present; noise may be added. User contributions that are considered may be limited to a maximum number of queries. The output may indicate how often (possibly plus noise) that each query appeared. Other output may comprise a query-action graph, a query-inaction graph and/or a query-reformulation graph, with nodes representing queries and nodes representing actions, inactions or reformulations (e.g., clicked URLs, skipped URLs, or selected related queries), and edges between nodes representing action, skip or selection counts (possibly plus noise). The output may correspond to the top results/related queries returned from a search.

Claims

1. In a computing environment, a method comprising:

processing a search log, including determining which queries from the search log correspond to information that is safe to publish; and

for each of the queries having information that is safe to publish, publishing the information as output data, wherein determining which queries from the search log correspond to information that is safe to publish comprises limiting how many queries in the search log each user can contribute to a set of queries for processing, wherein publishing the information as output data comprises outputting a query-action graph having nodes representing queries and nodes representing actions taken, with each edge between a query node and an action node having a weight that indicates how many times that action was taken following that query, wherein the weight has zero noise, a negative noise or a positive noise added thereto, or outputting a query-inaction graph having nodes representing queries and nodes representing actions skipped, with each edge between a query node and an inaction node having a weight that indicates how many times that action was not taken following that query, and wherein the weight has zero noise, a negative noise or a positive noise added thereto.

2. The method of claim 1 wherein publishing the information as the output data comprises outputting at least one of:

a query-action graph having nodes representing queries and nodes representing actions taken, wherein the actions taken comprise returned uniform resource locators, or

a query reformulation graph having nodes representing queries and nodes representing reformulated queries, wherein the reformulated queries comprise those that are returned as the top reformulated queries for each query with respect to a search performed with the each query.

3. The method of claim 1 wherein determining which queries from the search log correspond to information that is safe to publish comprises, for each query, determining a count based upon how many times that query appears in the search log or a subset of the queries for processing, and comparing the count to a threshold frequency count.

4. The method of claim 3 wherein the count is a noisy count based on an approximate number of times that the query appears in the search log or a subset of the queries for processing plus a noise value.

5. The method of claim 1 wherein publishing the information as output data comprises outputting a count value for each query that is safe to publish, where this count value corresponds to an approximate number of times that the query appears in the search log or a subset of queries for processing, plus a noise value.

6. The method of claim 1 wherein the actions taken comprise returned uniform resource locators that are clicked following each query, and further comprising, limiting the uniform resource locators to those that are returned as the top uniform resource locators with respect to a search performed with that query.

7. The method of claim 1 wherein publishing the information as output data comprises outputting a query reformulation graph having nodes representing queries and nodes representing reformulated queries, with each edge between a query node and reformulated query node having a weight that indicates how many times that reformulated query was clicked on following that query, wherein the weight has zero noise, a negative noise or a positive noise added thereto.

8. The method of claim 7 further comprising, limiting the reformulated queries to those that are returned as the top reformulated queries for each query with respect to a search performed with that query.

9. The method of claim 1 further comprising, receiving parameters that establish the information that is safe to publish and noise information.

10. In a computing environment, a system comprising:

at least one processing unit;

a transformation mechanism, implemented on the at least one processing unit, configured to process a search log, including by determining which queries from the search log correspond to information that is safe to publish, and for each of the queries having information that is safe to publish, configured to publish the information as output data, wherein determining which queries from the search log correspond to information that is safe to publish comprises limiting how many queries in the search log each user can contribute to a set of queries for processing, wherein publishing the information as output data comprises outputting a query-action graph having nodes representing queries and nodes representing actions taken, with each edge between a query node and an action node having a weight that indicates how many times that action was taken following that query, wherein the weight has zero noise, a negative noise or a positive noise added thereto, or outputting a query-inaction graph having nodes representing queries and nodes representing actions skipped, with each edge between a query node and an inaction node having a weight that indicates how many times that action was not taken following that query, and wherein the weight has zero noise, a negative noise or a positive noise added thereto.

11. The system of claim 10 wherein the transformation mechanism is further configured to output at least one of:

a query-action graph having nodes representing queries and nodes representing actions taken, wherein the actions taken comprise returned uniform resource locators, or

a query reformulation graph having nodes representing queries and nodes representing reformulated queries, wherein the reformulated queries comprise those that are returned as the top reformulated queries for each query with respect to a search performed with the each query.

12. The system of claim 10 wherein the transformation mechanism is further configured to determine, for each query, a count based upon how many times that query appears in the search log or a subset of the queries for processing, and configured to compare the count to a threshold frequency count when determining which queries from the search log correspond to information that is safe to publish.

13. The system of claim 12 wherein the count is a noisy count based on an approximate number of times that the query appears in the search log or a subset of the queries for processing plus a noise value.

14. The system of claim 10 wherein the transformation mechanism is further configured to output a count value for each query that is safe to publish, and wherein the count value corresponds to an approximate number of times that the query appears in the search log or a subset of queries for processing, plus a noise value.

15. The system of claim 10 wherein the actions taken comprise returned uniform resource locators that are clicked following each query, and wherein the transformation mechanism is further configured to limit the uniform resource locators to those that are returned as the top uniform resource locators with respect to a search performed with that query.

16. The system of claim 10 wherein the transformation mechanism is further configured to output a query reformulation graph having nodes representing queries and nodes representing reformulated queries, with each edge between a query node and reformulated query node having a weight that indicates how many times that reformulated query was clicked on following that query, wherein the weight has zero noise, a negative noise or a positive noise added thereto.

17. The system of claim 16 wherein the transformation mechanism is further configured to limit the reformulated queries to those that are returned as the top reformulated queries for each query with respect to a search performed with that query.

18. One or more computer storage devices storing computer executable instructions, which in response to execution by a computer, cause the computer to perform steps comprising:

processing a search log, including determining which queries from the search log correspond to information that is safe to publish; and

for each of the queries having information that is safe to publish, publishing the information as output data, wherein determining which queries from the search log correspond to information that is safe to publish comprises limiting how many queries in the search log each user can contribute to a set of queries for processing, wherein publishing the information as output data comprises outputting a query-action graph having nodes representing queries and nodes representing actions taken, with each edge between a query node and an action node having a weight that indicates how many times that action was taken following that query, wherein the weight has zero noise, a negative noise or a positive noise added thereto, or outputting a query-inaction graph having nodes representing queries and nodes representing actions skipped, with each edge between a query node and an inaction node having a weight that indicates how many times that action was not taken following that query, and wherein the weight has zero noise, a negative noise or a positive noise added thereto.

19. The one or more computer storage devices of claim 18 wherein the actions taken comprise returned uniform resource locators that are clicked following each query, and further comprising, limiting the uniform resource locators to those that are returned as the top uniform resource locators with respect to a search performed with that query.