Synopsis of a search log that respects user privacy

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.

BACKGROUND

A search log contains valuable information about the searches and corresponding actions performed by users as they interact with a search engine. For example, a web search log collects queries and clicks of users issued to an Internet search engine. Alternatively, a search log may contain queries issued by users and actions performed on the displayed results (e.g., logs for enterprise search, mobile search, database search, product catalog search/transactions, and so forth).

A search log can be very useful for providing access to customer services. For example, accessing a search log can help a company improve existing products and services (e.g., keyword advertising) and build new products and services.

Moreover search logs are very valuable data sources that are currently not available to the research community. For example, in many instances an Internet search log is more useful than a web crawl or document repositories as the search log may be used to understand the behavior of users posing queries, and obtain algorithms for problems such as computing related searches, making spelling corrections, expanding acronyms, determining query distributions, query classification, and/or tracking the change of query popularity over time. Advertisers can use such a log to better understand how users navigate to their web pages, gain a better understanding of their competitors, and improve keyword advertising campaigns.

However a search log contains a considerable amount of private information about individuals, and thus a search company cannot simply release such data. Indeed, user searches provide an electronic trail of confidential thoughts and identifiable information. For example, users may enter their own name or the names of their friends, home address, and their medical history as well as of their family and friends. In the case of web search logs, users may enter their credit card number and/or social security number as a search query, just to find out what information is present on the web.

In sum, releasing a search log is beneficial for various data-mining tasks, however doing so risks compromising user privacy. Previous attempts to release search logs while maintaining privacy have failed; one attempt replaced usernames with random identifiers, however the searches were easy to match to an individually identifiable person based on the rest of the data. Other ad-hoc techniques, such as tokenizing each search query and securely hashing the token into an identifier, have been explored in the literature and are shown not to protect privacy.

SUMMARY

Briefly, various aspects of the subject matter described herein are directed towards a technology by which a search log is processed into information that represents the search log contents (e.g., suitable for most mining/analysis applications), but is safe to publish with respect to preserving user privacy. In one aspect, a query is only included in the output information if the number of times the query is present in the search log or a subset of the search log exceeds a sufficient threshold. Noise may be added to the count. The subset may be generated by limiting how many queries and/or query clicks of each user are included in the data to be processed. Parameters may control privacy versus utility, e.g., the threshold value, the maximum number of queries a user can contribute, the noise values (which may be Laplacian distributions and thus vary for each addition), and so forth.

In one aspect, the output data may comprise query counts, that is, for each query, a count of how many times (plus zero, positive or negative noise) that query appeared in the search log or subset. Other output data may comprise a query-action graph, with nodes representing queries and nodes representing actions, and edges between the query nodes and action nodes indicating how many times (plus zero, positive or negative noise) the action (e.g., a click on a URL, advertisement, image, video, news article and the like) was taken following the query. Note that a query-inaction graph or the like, e.g., that indicates how many times a URL, advertisement, image, video, news article and the like was skipped, may be similarly released. The actions may, for example, correspond to the top URLs returned from a search that was made with the associated query. Still other output data may comprise a query-reformulation graph, with nodes representing queries and nodes representing reformulations (e.g., suggested/related queries), and edges between the query nodes and reformulation nodes indicating how many times (plus zero, positive or negative noise) the reformulation (e.g., a selection of a related query) was taken following the query. The reformulations may, for example, correspond to the top related queries returned from a search that was made with the associated query.

DETAILED DESCRIPTION

Various aspects of the technology described herein are generally directed towards publicly releasing information of a search log in a way that preserves the log's utility for various data-mining tasks, while at the same time protecting user privacy. As will be understood, this is accomplished by publishing certain data obtained from the search log in a transformed output. The transformation is such that most of the utility of the original data set is preserved, that is, most data mining tasks on a search log can be performed over the published data. At the same time, a rigorous definition of user privacy (that is, differential privacy) is defined, with a transformation mechanism/algorithm configured to preserve the privacy of the published data.

It should be understood that any of the examples herein, such as the type of search logs that may be processed, and the form of the output data, are non-limiting examples. As such, the present invention is not limited to any particular embodiments, aspects, concepts, structures, functionalities or examples described herein. Rather, any of the embodiments, aspects, concepts, structures, functionalities or examples described herein are non-limiting, and the present invention may be used various ways that provide benefits and advantages in computing and data mining in general.

Turning toFIG. 1, there is shown general block diagram representing a search log102being processed by a transformation mechanism/algorithm104into output data. As used herein, a “search log” includes any log that records queries issued by users and actions (e.g. click or purchase) performed on the displayed results. For example, one suitable search log may be a web search log in which each result is a URL and each action is a click. Another suitable search log may comprise a product or service catalog search and transaction log, in which each result is a product or service result, and each action is a purchase. Thus, the technology is not limited to releasing data of web search logs, but can be used to publish any logs where users issue queries and perform actions (such as click or purchase) on some of the displayed results (e.g., logs for enterprise search, mobile search, database search, product catalog search/transactions, library search, and so forth). Further, as can be readily appreciated, not all of the exemplified types of output data need to be released to be of use in data mining; e.g., only counts of queries and click actions may be needed for a given mining/analysis application, depending on the information being sought.

In the example ofFIG. 1, the output data includes query counts106(e.g., comprising query, query count pairs), and two synapses A and B. The query counts represent an approximate number of times that each query that is safe to publish (as described below) occurs in the log102.

In this example, the output data also includes one synopsis A, in the form of a privacy-preserving query-action graph107, comprising a graph over the set of queries and the set of results, where there is an edge connecting a query to a result with weight equal to the number of actions on the result for the query. The query-action graph may be based on the top results for each query, e.g., the graph may represent the approximate query-result action counts for the top results for each query.

Another synopsis B is in the form of a privacy-preserving query-reformulation graph108, comprising a directed graph over the set of queries, where there is an edge from one query to another query with weight equal to the number of times the first query is reformulated to the second query. The query-reformulation graph may be based on the top reformulations (related/suggested queries that are returned) for each query that are clicked, that is, the graph may represent the query-result reformulation counts for the top related queries returned with the response for each query.

Another synopsis C is in the form of a privacy-preserving query-inaction graph109. As described below, this reflects for queries and URLs the number of times that a URL was provided in response to a query but no action was taken, e.g., the URL was not clicked, that is, was skipped.

In one embodiment, a concrete, rigorous definition of privacy is adopted, referred to as differential privacy, with the mechanism/algorithm designed to provably satisfy this definition. As will be understood, the mechanism/algorithm is based in part on parameters which can be controlled to achieve a desired level of privacy and utility. Note that while certain parameters are described as examples herein, different parameters may be chosen.

Differential privacy captures a desired notion of privacy, namely that the risk to one's privacy does not substantially increase as a result of participating in the dataset (e.g., as a result of using a search engine). This is accomplished by guaranteeing that any released dataset is almost just as likely to contain the same information whether or not any given individual participates in the dataset. Differential privacy also does not make any assumptions about an adversary's computational power or ability to access additional data beyond that released.

In one implementation, the following variant of differential privacy definition is used:

(ε, δ)-differential privacy: A randomized algorithm A is (ε, δ)-differentially private if for all data sets D1and D2differing in at most one element and all D′Range(A), Pr[A(D1)εD′]≦exp(ε)·Pr[A(D2)εD′]+δ.

For computation and release of functions such as histograms on the data set, this privacy definition can be further satisfied by adding noise as part of the algorithm. In one implementation, the noise is chosen according to Laplacian distribution, with other parameters that depend on desired privacy parameters (ε, δ) and sensitivity of the function (that is, by how much the value of the function can change for inputs differing in one entry).

To further guarantee that any released dataset is almost just as likely whether or not a user uses the search engine to pose queries, the number of queries any user can pose is limited. This protects against any one user having too much influence on the results. In one algorithm, this limit, d is set as a parameter. As the value of d gets larger, more noise is added to guarantee the same level of privacy. It is also feasible to count the same query from the same user only once (or some other limited number); this prevents a user from pushing an infrequent (tail) query to a frequent query (the head) by simply entering the same query over and over.

In general, the mechanism that produces the output data (e.g., counts, privacy-preserving query-action graph and privacy-preserving query-reformulation graph) evaluates a number of input data. In one implementation, to determine which queries to publish (release), if the frequency of the query plus noise exceeds some threshold, the query is published, otherwise it is not. This can be intuitively described as “throwing away tail queries.” Note that for each of the queries to be published, the corresponding query counts that are published are noisy counts, i.e. the number of time the query was posed plus noise.

Note that for the query action graph, given the queries that are safe to publish, the top results that surfaced are also safe to publish when interacting with a publicly available engine such as a search engine, library database, or commercial search engine since anyone can pose a query to such a search engine and see those top results. To publish the number of users that perform action on a result, the actual number is computed, and noise added. For the query-reformulation graph, given the queries that are safe to publish, the top related queries shown are also safe to publish, because anyone can pose a query to a search engine and see the top related queries. To publish the number of users that reformulate to a related query shown, the actual number is computed, and noise added. Similarly, related images, videos, advertisements, new stories and products may be published.

FIGS. 2 and 3represent example steps performed by the transformation mechanism, beginning at step202where the search log and parameters are input. The input includes the search log102, referred to in the following equations as D; a parameter d that sets the limit on how many queries of any user can be included; a frequency/count threshold, K; and parameters b1, b2and b3that indicate the amount of noise to be used in each step.

With respect to releasing queries, for every user whose activity is recorded in the search log, step204removes the queries except the first d queries of the user from D. Note that in general, any set of d queries of the user can be retained, such as a random selection or pattern that limits the number to d; further, a limit may not be mandatory. Thus, further processing may take place on the search log itself, or on a subset of the queries for processing, e.g., on the block110.

Then, for every query q that remains in D, (represented inFIG. 1by the block110), starting with a first query at step206, the occurrence count is obtained, that is, let M(q,D) denote the number of occurrences of q in D. The first noise Lap(b1) is added to the count at step210. Note that instead of Laplacian distribution, other ways to generate the noise may be used, e.g., adding/subtracting a randomly generated number or noise from a different distribution (such as a normal distribution).

Via steps212and213, the query q is evaluated against the threshold frequency count K, and released (to an output set112ofFIG. 1for further processing as described below with reference toFIG. 3) if and only if the count plus the noise exceeds the threshold frequency count K. In other words, information about any query is published if and only if M(q,D)+Lap(b1)≧K. Note that for any or all noise values, the noise value may be positive, or may be negative such that when added, the noisy count decreases relative to the count value before adding; the noise also may be zero.

Steps214and215repeat the process that builds the output set112until all queries that remained in D have been similarly processed.

FIG. 3represents further processing the output set112. Note that inFIG. 3, steps302,314and315select each of the queries in the output set to perform the processing of that query.

To release the query counts106for every query q cleared for release, (that is, is within the output set112), step304releases its noisy count, M(q,D)+Lap(b2). Note that for privacy the second noise parameter is used in this computation.

To build and release the query-action graph, for every query q cleared for release, a search is performed at step306using an appropriate search/query engine (e.g., a web “search engine” for a “web search,” a database engine for a database query/search and so forth) to obtain the top results returned for q. Then, at step308, for each result u returned, let C(q,u) denote the number of times an action (such as click) was performed on result u whenever q was issued in D and release the noisy count, C(q,u)+Lap(b3) as the weight of the edge (q,u) in the query-action graph. A query-inaction graph may be similarly output (step309).

To build and release the query-reformulation graph, a search is performed at step310using a search engine to obtain the top related queries returned for q. Note that the search of step306may obtain both the top results and the top related queries; in other words, only one search need be performed (step310is performed as part of step306).

At step312, for each related query, q′ returned, let R(q,q′) denote the number of times the related query q′ was issued just after query q was issued in D, and release the noisy count, R(q,q′)+Lap(b3) as the weight of the edge (q,q′) in the query-reformulation graph. Note that a different weight from that used in the query-action graph may be used, e.g., b4instead of b3.

The algorithm (ALG) achieves (ε, δ)-differential privacy with the privacy

As noted above, in other embodiments, the parameters in our algorithm (such as the amount or the type of noise to be added) may be chosen in a different manner. For instance, the noise added could be drawn from the Gaussian distribution. Further each user's activity does not have to be limited to only d queries.

Exemplary Operating Environment

With reference toFIG. 4, an exemplary system for implementing various aspects of the invention may include a general purpose computing device in the form of a computer410. Components of the computer410may include, but are not limited to, a processing unit420, a system memory430, and a system bus421that couples various system components including the system memory to the processing unit420. The system bus421may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

The system memory430includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM)431and random access memory (RAM)432. A basic input/output system433(BIOS), containing the basic routines that help to transfer information between elements within computer410, such as during start-up, is typically stored in ROM431. RAM432typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit420. By way of example, and not limitation,FIG. 4illustrates operating system434, application programs435, other program modules436and program data437.

The computer410may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only,FIG. 4illustrates a hard disk drive441that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive451that reads from or writes to a removable, nonvolatile magnetic disk452, and an optical disk drive455that reads from or writes to a removable, nonvolatile optical disk456such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive441is typically connected to the system bus421through a non-removable memory interface such as interface440, and magnetic disk drive451and optical disk drive455are typically connected to the system bus421by a removable memory interface, such as interface450.

The drives and their associated computer storage media, described above and illustrated inFIG. 4, provide storage of computer-readable instructions, data structures, program modules and other data for the computer410. InFIG. 4, for example, hard disk drive441is illustrated as storing operating system444, application programs445, other program modules446and program data447. Note that these components can either be the same as or different from operating system434, application programs435, other program modules436, and program data437. Operating system444, application programs445, other program modules446, and program data447are given different numbers herein to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer410through input devices such as a tablet, or electronic digitizer,464, a microphone463, a keyboard462and pointing device461, commonly referred to as mouse, trackball or touch pad. Other input devices not shown inFIG. 4may include a joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit420through a user input interface460that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor491or other type of display device is also connected to the system bus421via an interface, such as a video interface490. The monitor491may also be integrated with a touch-screen panel or the like. Note that the monitor and/or touch screen panel can be physically coupled to a housing in which the computing device410is incorporated, such as in a tablet-type personal computer. In addition, computers such as the computing device410may also include other peripheral output devices such as speakers495and printer496, which may be connected through an output peripheral interface494or the like.

The computer410may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer480. The remote computer480may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer410, although only a memory storage device481has been illustrated inFIG. 4. The logical connections depicted inFIG. 4include one or more local area networks (LAN)471and one or more wide area networks (WAN)473, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

When used in a LAN networking environment, the computer410is connected to the LAN471through a network interface or adapter470. When used in a WAN networking environment, the computer410typically includes a modem472or other means for establishing communications over the WAN473, such as the Internet. The modem472, which may be internal or external, may be connected to the system bus421via the user input interface460or other appropriate mechanism. A wireless networking component474such as comprising an interface and antenna may be coupled through a suitable device such as an access point or peer computer to a WAN or LAN. In a networked environment, program modules depicted relative to the computer410, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation,FIG. 4illustrates remote application programs485as residing on memory device481. It may be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

An auxiliary subsystem499(e.g., for auxiliary display of content) may be connected via the user interface460to allow data such as program content, system status and event notifications to be provided to the user, even if the main portions of the computer system are in a low power state. The auxiliary subsystem499may be connected to the modem472and/or network interface470to allow communication between these systems while the main processing unit420is in a low power state.

CONCLUSION